1 #include <stdio.h>
2 #include <stdlib.h>
3 //*****二叉樹的二叉鏈表存儲表示*****//
4 typedef struct BiNode
5 {
6 char data;
7 struct BiNode *lchild, *rchild;
8 }BiNode, *BiTree;
9
10 //*****按先序次序輸入二叉樹中結點的值(一個字符)，空格字符表示空樹構造二叉鏈表表示的二叉樹T*****//
11 void CreateBiTree(BiTree &T)
12 {
13 char ch;
14 scanf("%c", &ch);
15 if(ch == ' ')
16 {
17 T = NULL;
18 }
19 else
20 {
21 if(!(T = (BiNode *)malloc(sizeof(BiNode))))
22 {
23 return;
24 }
25 T->data = ch; //生成根結點
26 CreateBiTree(T->lchild); //構造左子樹
27 CreateBiTree(T->rchild); //構造右子樹
28 }
29
30 return;
31 }
32
33 //*****先序遍歷二叉樹*****//
34 void PreOrderTraverse(BiTree T)
35 {
36 if(!T)
37 {
38 return; //若T為空樹，則直接返回
39 }
40 printf("%c ", T->data); //訪問根結點
41 PreOrderTraverse(T->lchild); //先序遍歷左子樹
42 PreOrderTraverse(T->rchild); //先序遍歷右子樹
43
44 return;
45 }
46
47 //*****中序遍歷二叉樹*****//
48 void InOrderTraverse(BiTree T)
49 {
50 if(!T)
51 {
52 return; //若T為空樹，則直接返回
53 }
54 InOrderTraverse(T->lchild); //中序遍歷左子樹
55 printf("%c ", T->data); //訪問根結點
56 InOrderTraverse(T->rchild); //中序遍歷右子樹
57
58 return;
59 }
60
61 //*****後序遍歷二叉樹*****//
62 void PostOrderTraverse(BiTree T)
63 {
64 if(!T)
65 {
66 return; //若T為空樹，則直接返回
67 }
68 PostOrderTraverse(T->lchild); //後序遍歷左子樹
69 PostOrderTraverse(T->rchild); //後序遍歷右子樹
70 printf("%c ", T->data); //訪問根結點
71
72 return;
73 }
74
75 int main(void)
76 {
77 BiTree T;
78 printf("請按先序次序輸入二叉樹中結點的值(字符)，空格字符表示空樹:\n");
79 CreateBiTree(T);
80
81 printf("先序遍歷結果為:");
82 PreOrderTraverse(T);
83 printf("\n\n");
84
85 printf("中序遍歷結果為:");
86 InOrderTraverse(T);
87 printf("\n\n");
88
89 printf("後序遍歷結果為:");
90 PostOrderTraverse(T);
91 printf("\n\n");
92
93 return 0;
94 }
以如下二叉樹為例，給出按先序次序輸入二叉樹中結點的值（字符），從而按照本文給出的算法構造二叉樹。
輸入字符的順序是：-+a空格空格*b空格空格-c空格空格d空格空格/e空格空格f空格空格，即可驗證本文提供的遍歷算法。
