本文共 1512 字，大约阅读时间需要 5 分钟。

遍历二叉树（traversing binary tree）

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

先序遍历：

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

1.访问跟结点；

2.先遍历左子树；

3.先遍历右子树。

中序遍历：

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

1.先遍历左子树；

2.访问跟结点；

3.先遍历右子树。

后序遍历：

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

1.先遍历右子树。

2.先遍历左子树；

3.访问跟结点；

下面给出一张图：

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

先序遍历为：ABDHIEJCFKG。

中序遍历为：HDIBEJAFKCG。

后续遍历为：HIDJEBKFGCA。

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

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

下面是代码：

#include 
   
    #include 
    
     #include 
     
      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);

转载地址：https://it1995.blog.csdn.net/article/details/55826458 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！