二叉树遍历（C++实现）

用C++实现二叉树的“先根遍历”存储。

用C++实现二叉树的“先根遍历”、“中根遍历”、“后根遍历”分别输出二叉树中结点的数据。

 1 #include <iostream>
 2 using namespace std ;
 3 
 4 struct BiNode 
 5 {
 6     char data ;
 7     BiNode *lchild , *rchild ;
 8 } ;
 9 BiNode *BiTree ;
10 
11 int NodeID ;
12 
13 BiNode *CreateBiTree (char *c , int n)
14 {
15     BiNode *T ;
16     NodeID ++ ;
17     if (NodeID > n)
18     {
19         return (NULL) ;
20     }
21     if (c[NodeID] == '0')
22     {
23         return (NULL) ;
24     }
25     T = new BiNode ;
26     T -> data = c[NodeID] ;
27     T -> lchild = CreateBiTree (c , n) ;
28     T -> rchild = CreateBiTree (c , n) ;
29     return (T) ;
30 }
31 
32 void PreOrderTraverse (BiNode *T)
33 {
34     if (T)
35     {
36         cout << T -> data << " ";
37         PreOrderTraverse (T -> lchild) ;
38         PreOrderTraverse (T -> rchild) ;
39     }
40 }
41 
42 void InOrderTraverse (BiNode *T)
43 {
44     if (T)
45     {
46         InOrderTraverse (T -> lchild) ;
47         cout << T -> data << " ";
48         InOrderTraverse (T -> rchild) ;
49     }
50 }
51 
52 void PostOrderTraverse (BiNode *T)
53 {
54     if (T)
55     {
56         PostOrderTraverse (T -> lchild) ;
57         PostOrderTraverse (T -> rchild) ;
58         cout << T -> data << " ";
59     }
60 }
61 
62 int main ()
63 {
64     int i , SampleNum ;
65     char c[100] ;
66     cin >> SampleNum ;
67     for (i = 1 ; i <= SampleNum ; i ++)
68     {
69         cin >> c[i] ;
70     }
71     NodeID = 0 ;
72     BiTree = CreateBiTree (c , SampleNum) ;
73     PreOrderTraverse (BiTree) ;
74     cout << endl ;
75     InOrderTraverse (BiTree) ;
76     cout << endl ;
77     PostOrderTraverse (BiTree) ;
78     return 0 ;
79 }