6.3.1遍历二叉树

遍历二叉树（traversing binary tree）

从根结点出发，按照某种次序，依次访问二叉树中所有结点，使得每个结点被访问次仅此一次。

先序遍历：

若二叉树为空，则空操作。否则

1.访问跟结点；

2.先遍历左子树；

3.先遍历右子树。

中序遍历：

若二叉树为空，则空操作。否则

1.先遍历左子树；

2.访问跟结点；

3.先遍历右子树。

后序遍历：

若二叉树为空，则空操作。否则

1.先遍历右子树。

2.先遍历左子树；

3.访问跟结点；

下面给出一张图：

那么，他的遍历。我们来看看。

先序遍历为：ABDHIEJCFKG。

中序遍历为：HDIBEJAFKCG。

后续遍历为：HIDJEBKFGCA。

下面我们来演示代码操作。

代码是按照先序遍历的输入，然后输出他们所在的层数。

下面是代码：

#include <stdio.h>#include <stdlib.h>#include <Windows.h>typedef char Elemtype;typedef struct BiTNode{	char data;	struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;//要求用户按照前序遍历输入数据void CreateBiTree(BiTree *T){	char c;	scanf_s("%c", &c);	if ('$' == c)	{		*T = NULL;	}	else	{		*T = (BiTNode *)malloc(sizeof(BiTNode));		(*T)->data = c;		CreateBiTree(&(*T)->lchild);	//创建左子树		CreateBiTree(&(*T)->rchild);	//创建右子树	}}//访问二叉树结点操作void visit(char c, int level){	PRintf_s("%c位于第%d层/n", c, level);}//遍历二叉树void PreOrderTraverse(BiTree T, int level){	if (T)	{		visit(T->data, level);		PreOrderTraverse(T->lchild, level + 1);		PreOrderTraverse(T->rchild, level + 1);	}}int main(){	int level = 1;	BiTree T = NULL;	CreateBiTree(&T);	PreOrderTraverse(T, level); 	system("pause");	return 0;}运行结构如下：
下面来解释下。这个$，就是当某个子树他没有左孩子，或者右孩子的时候为NULL，用$代表NULL
如下图所示：
那么这个树的先序遍历为：
ABDH$$I$$E$J$$CF$K$$G$$
那么中序遍历和后续遍历呢？
只需要改变下面这个代码就可以了:
中序遍历：
		PreOrderTraverse(T->lchild, level + 1);                visit(T->data, level);		PreOrderTraverse(T->rchild, level + 1);
后续遍历：
		PreOrderTraverse(T->lchild, level + 1);		PreOrderTraverse(T->rchild, level + 1);                visit(T->data, level);