二叉樹的遍歷一般分為三種遍歷方法，即先序遍歷、中序遍歷和後序遍歷。
在中序遍歷中,一個節點的前驅,是其左子樹的最右下角結點,後繼,是其右子樹的最左下角結點。
在後序遍歷中,
• 若結點是根結點,則其後繼為空;
• 若結點是雙親的右子樹,或是左子樹但雙親無右子樹,則其後繼為雙親結點;
• 若結點是雙親的左子樹且雙親有右子樹,則其後繼為右子樹按後序遍歷的第一個結點
二叉樹的遍歷實現如下：
1 #include <stack>
2 #include <queue>
3
4 /*
5 *@struct
6 *@brief 二叉樹結點
7 */
8 typedef struct binary_tree_node_t
9 {
10 binary_tree_node_t *lchild; /* 左孩子 */
11 binary_tree_node_t *rchild; /* 右孩子 */
12 void* data; /* 結點的數據 */
13 }binary_tree_node_t;
14
15 /**
16 * @brief 先序遍歷,遞歸.
17 * @param[in] root 根結點
18 * @param[in] visit 訪問數據元素的函數指針
19 * @return 無
20 */
21 void pre_order_r(const binary_tree_node_t *root, int (*visit)(void*))
22 {
23 if(root != NULL)
24 {
25 (void)visit(root->data);
26 pre_order_r(root->lchild, visit);
27 pre_order_r(root->rchild, visit);
28 }
29 }
30
31 /**
32 * @brief 中序遍歷,遞歸.
33 */
34 void in_order_r(const binary_tree_node_t *root, int (*visit)(void*))
35 {
36 if(root != NULL)
37 {
38 pre_order_r(root->lchild, visit);
39 (void)visit(root->data);
40 pre_order_r(root->rchild, visit);
41 }
42 }
43
44 /**
45 * @brief 後序遍歷,遞歸.
46 */
47 void post_order_r(const binary_tree_node_t *root, int (*visit)(void*))
48 {
49 if(root != NULL)
50 {
51 pre_order_r(root->lchild, visit);
52 pre_order_r(root->rchild, visit);
53 (void)visit(root->data);
54 }
55 }
56
57 /**
58 * @brief 先序遍歷,非遞歸.
59 */
60 void pre_order(const binary_tree_node_t *root, int (*visit)(void*))
61 {
62 const binary_tree_node_t *p;
63 std::stack<const binary_tree_node_t *> s;
64 p = root;
65 if(p != NULL)
66 {
67 s.push(p);
68 }
69
70 while(!s.empty())
71 {
72 p = s.top();
73 s.pop();
74 visit(p->data);
75 if(p->rchild != NULL)
76 {
77 s.push(p->rchild);
78 }
79 if(p->lchild != NULL)
80 {
81 s.push(p->lchild);
82 }
83 }
84 }
85
86 /**
87 * @brief 中序遍歷,非遞歸.
88 */
89 void in_order(const binary_tree_node_t *root, int (*visit)(void*))
90 {
91 const binary_tree_node_t *p;
92 std::stack<const binary_tree_node_t *> s;
93 p = root;
94 while(!s.empty() || p!=NULL)
95 {
96 if(p != NULL)
97 {
98 s.push(p);
99 p = p->lchild;
100 }
101 else
102 {
103 p = s.top();
104 s.pop();
105 visit(p->data);
106 p = p->rchild;
107 }
108 }
109 }
110
111 /**
112 * @brief 後序遍歷,非遞歸.
113 */
114 void post_order(const binary_tree_node_t *root, int (*visit)(void*))
115 {
116 /* p,正在訪問的結點,q,剛剛訪問過的結點 */
117 const binary_tree_node_t *p, *q;
118 std::stack<const binary_tree_node_t *> s;
119 p = root;
120 do {
121 while(p != NULL)
122 {
123 /* 往左下走 */
124 s.push(p);
125 p = p->lchild;
126 }
127 q = NULL;
128 while(!s.empty())
129 {
130 p = s.top();
131 s.pop();
132 /* 右孩子不存在或已被訪問,訪問之 */
133 if(p->rchild == q)
134 {
135 visit(p->data);
136 q = p; /* 保存剛訪問過的結點 */
137 }
138 else
139 {
140 /* 當前結點不能訪問,需第二次進棧 */
141 s.push(p);
142 /* 先處理右子樹 */
143 p = p->rchild;
144 break;
145 }
146 }
147 }while(!s.empty());
148 }
149
150 /**
151 * @brief 層次遍歷,也即 BFS.
152 *
153 * 跟先序遍歷一模一樣,唯一的不同是棧換成了隊列
154 */
155 void level_order(const binary_tree_node_t *root, int (*visit)(void*))
156 {
157 const binary_tree_node_t *p;
158 std::queue<const binary_tree_node_t *> q;
159 p = root;
160 if(p != NULL)
161 {
162 q.push(p);
163 }
164 while(!q.empty())
165 {
166 p = q.front();
167 q.pop();
168 visit(p->data);
169 if(p->lchild != NULL)
170 {
171 /* 先左後右或先右後左無所謂 */
172 q.push(p->lchild);
173 }
174 if(p->rchild != NULL)
175 {
176 q.push(p->rchild);
177 }
178 }
179 }
