二叉树的递归遍历

【先序遍历】

遍历的过程为：

访问“根结点”；
“先序”遍历其“左子树”；
“先序”遍历其“右子树”；

1 void PreOrderTraversal( BinTree BT )
2 {
3     if( BT )
4     {
5         printf(“%d”, BT->Data);
6         PreOrderTraversal( BT->Left );
7         PreOrderTraversal( BT->Right );
8     }
9 }

访问过程：

第1次遇到结点即访问：A （B D F E）（C G H I）

【中序遍历】

遍历过程为：

“中序”遍历其“左子树”；
访问“根结点”；
“中序”遍历其“右子树”；

1 void InOrderTraversal( BinTree BT )
2 {
3     if( BT ) 
4     {
5         InOrderTraversal( BT->Left );
6         printf(“%d”, BT->Data);
7         InOrderTraversal( BT->Right );
8     }
9 }

访问过程：

第2次遇到结点才访问：（D B E F） A （G H C I）

【后序遍历】

遍历过程为：

“后序”遍历其“左子树”；
“后序”遍历其“右子树”；
访问“根结点”；

1 void PostOrderTraversal( BinTree BT )
2 {
3     if( BT ) 
4     {
5         PostOrderTraversal( BT->Left );
6         PostOrderTraversal( BT->Right);
7         printf(“%d”, BT->Data);
8     }
9 }

访问过程：

第3次遇到结点才访问：（D E F B）（H G I C） A

先序、中序和后序遍历过程中，经过结点的路线一样，只是访问各结点的时机不同：先序遍历第1次遇到结点就进行访问；中序遍历第2次遇到结点才进行访问；后序遍历则第3次遇到结点才访问。

无论前中后，叶子的顺序一样？从左到右？

前：A B D F E C G H I

中：D B E F A G H C I

后：D E F B H G I C A

测试代码：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef int ElementType;
  5 
  6 //struct TreeNode;
  7 
  8 //typedef struct TreeNode *BinTree;
  9 //typedef struct BinTree Position;
 10 
 11 typedef struct TreeNode {
 12     ElementType Data;
 13     struct TreeNode *Left;
 14     struct TreeNode *Right;
 15 }*BinTree, *Position;
 16 
 17 Position createBinNode(ElementType data)
 18 {
 19     Position T;
 20 
 21     T = (Position)malloc(sizeof(struct TreeNode));
 22     if(T == NULL)
 23     {
 24         return NULL;
 25     }
 26     T->Left  = NULL;
 27     T->Right = NULL;
 28     T->Data  = data;
 29 
 30     return T;
 31 }
 32 
 33 void PreOrderTraversal(BinTree Bt)
 34 {
 35     if(Bt)
 36     {
 37         printf("%c ", Bt->Data);
 38         PreOrderTraversal(Bt->Left);
 39         PreOrderTraversal(Bt->Right);
 40     }
 41 }
 42 
 43 void PreOrderTraversal_R2L(BinTree Bt)
 44 {
 45     if(Bt)
 46     {
 47         printf("%c ", Bt->Data);
 48         PreOrderTraversal_R2L(Bt->Right);
 49         PreOrderTraversal_R2L(Bt->Left);
 50     }
 51 }
 52 
 53 void InOrderTraversal(BinTree Bt)
 54 {
 55     if(Bt)
 56     {
 57         InOrderTraversal(Bt->Left);
 58         printf("%c ", Bt->Data);
 59         InOrderTraversal(Bt->Right);
 60     }
 61 }
 62 
 63 void PostOrderTraversal(BinTree Bt)
 64 {
 65     if(Bt)
 66     {
 67         PostOrderTraversal(Bt->Left);
 68         PostOrderTraversal(Bt->Right);
 69         printf("%c ", Bt->Data);
 70     }
 71 }
 72 
 73 int main(void)
 74 {
 75     Position T1;
 76     Position T21, T22;
 77     Position T31, T32, T33, T34;
 78     Position T41, T42, T43, T44, T45, T46, T47, T48;
 79 
 80     T1  = createBinNode('A');
 81     T21 = createBinNode('B');
 82     T22 = createBinNode('C');
 83     T31 = createBinNode('D');
 84     T32 = createBinNode('F');
 85     T33 = createBinNode('G');
 86     T34 = createBinNode('I');
 87     T43 = createBinNode('E');
 88     T46 = createBinNode('H');
 89 
 90     
 91     T1->Left   = T21;
 92     T1->Right  = T22;
 93 
 94     T21->Left  = T31;
 95     T21->Right = T32;
 96 
 97     T22->Left  = T33;
 98     T22->Right = T34;
 99 
100     T32->Left  = T43;
101 
102     T33->Right = T46;
103     
104     printf("PreOrderTraversal:
");
105     PreOrderTraversal(T1);
106 
107     printf("
");
108     printf("PreOrderTraversal R->L:
");
109     PreOrderTraversal_R2L(T1);
110 
111     printf("
");
112     printf("InOrderTraversal:
");
113     InOrderTraversal(T1);
114 
115     printf("
");
116     printf("PostOrderTraversal:
");
117     PostOrderTraversal(T1);
118 
119     printf("
");
120 
121     return 0;
122 }