遍历树存在如下的方式:
前序遍历（Preorder Tree Walk）按照根节点—左子树—右子树顺序遍历中序遍历（Inoder Tree Walk）按照左子树—根节点—右子树顺序遍历后序遍历（Postorder Tree Walk）按照左子树—右子树—根节点顺序遍历使用递归的方式遍历
#include <iostream> using namespace std; const int MAX = 100000; const int NIL = -1; struct Node { int p, l, r; }; Node T[MAX]; int n; void PreParse(int u)//前序遍历 { if (u == NIL) return; cout << u << " "; PreParse(T[u].l); PreParse(T[u].r); } void InParse(int u) //中序遍历 { if (u == NIL) return; InParse(T[u].l); cout << u << " "; InParse(T[u].r); } void PostParse(int u) //后序遍历 { if (u == NIL) return; PostParse(T[u].l); PostParse(T[u].r); cout << u << " "; } int main() { int v, l, r, root = 0; cin >> n; for (int i = 0; i < n; i++) { cin >> v >> l >> r; T[v].l = l; T[v].r = r; if (l != NIL) T[l].p = v; if (r != NIL) T[r].p = v; } for (int i = 0; i < n; i++) if (T[i].p == NIL) root = i; cout << "Preorder:"; PreParse(root); cout << endl << "Inordr:"; InParse(root); cout << endl << "Postorder:"; PostParse(root); return 0; } /* input: 9 0 1 4 1 2 3 2 -1 -1 3 -1 -1 4 5 8 5 6 7 6 -1 -1 7 -1 -1 8 -1 -1 */ /* output: Preorder:0 1 2 3 4 5 6 7 8 Inordr:2 1 3 0 6 5 7 4 8 Postorder:2 3 1 6 7 5 8 4 0 */