数据结构 - 二叉树的遍历

树的结构

定义二叉树的数据结构如下：

typedef struct BiTNode  // 节点结构
{
   TElemType data;		// 节点数据
   struct BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

构成下图所示的二叉树为例：包含 A ~ I 共9个节点

遍历方式

目前基本是采用递归的方式来对树进行遍历，核心就是先递归遍历左子树，再递归遍历右子树

void Traverse(BiTree T)
{
	if(T==NULL)
		return;
	Traverse(T->lchild); /* 先遍历左子树  */
	Traverse(T->rchild); /* 再遍历右子树  */
}

运行顺序如下图所示：

前序遍历

【注】：图中的各类图形表示说明

添加对节点的输出操作后（也可以为其他操作），遍历结果如下图所示，左上角为对节点的输出操作在完整的遍历过程中所处的步骤，右下角为遍历的逻辑顺序。

【注】：逻辑顺序不代表程序实际运行的顺序，比如对于右下角5号线，树在遍历时并不能直接跳过去，而是通过左上角所示的完整运行步骤中的10~14号线依次运行过去的。

中序遍历

后序遍历

层序遍历

....有空再详写，很直观 一层一层依次往下

 

 

参考

《大话数据结构》