遍歷二叉樹（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);