1 //第一步：头文件
2 //第二步：宏定义，结构体定义，重命名
3 //第三步：情况 1：声明小函数，函数的具体实现放在 main 函数之后
4 //情况 2：定义并实现小函数的具体代码，所有的函数实现都在 main 函数之前
5 //第四步：实现 main 函数
6 #include
7 #include
8 typedef char ElementType;
9 typedef struct TNode * Position;
10 typedef Position BinTree; /* 二叉树类型 */
11 struct TNode{ /* 树结点定义 */
12 ElementType Data; /* 结点数据 */
13 struct TNode * Left; /* 指向左子树 */
14 BinTree Right; /* 指向右子树 */
15 };
16
17 /* 中序遍历 */
18 void MiddleTraversal( BinTree BT )
19 {
20 if( BT ) {
21 MiddleTraversal( BT->Left );
22 /* 此处假设对 BT 结点的访问就是打印数据 */
23 printf("%c ", BT->Data); /* 假设数据为整型 */
24 MiddleTraversal( BT->Right );
25 }
26 }
27
28 /* 先序遍历 */
29 void PreviousTraversal( BinTree BT )
30 {
31 if( BT ) {
32 printf("%c ", BT->Data );
33 PreviousTraversal( BT->Left );
34 PreviousTraversal( BT->Right );
35 }
36 }
37
38 /* 后序遍历 */
39 void BehindTraversal( BinTree BT )
40 {
41 if( BT ) {
42 BehindTraversal( BT->Left );
43 BehindTraversal( BT->Right );
44 printf("%c ", BT->Data);
45 }
46 }
47
48 BinTree CreateBTree() {
49 //自己构建二叉树
50 //1:用 malloc 分配空间大小
51 BinTree PA = (struct TNode*)malloc(sizeof(struct TNode));
52 BinTree PB = (Position)malloc(sizeof(struct TNode));
53 BinTree PC = (BinTree)malloc(sizeof(struct TNode));
54 BinTree PD = (struct TNode*)malloc(sizeof(struct TNode));
55 BinTree PE = (Position)malloc(sizeof(struct TNode));
56 BinTree PF = (BinTree)malloc(sizeof(struct TNode));
57 //2：每个结点数据域赋值
58 PA->Data = 'A';
59 PB->Data = 'B';
60 PC->Data = 'C';
61 PD->Data = 'D';
62 PE->Data = 'E';
63 PF->Data = 'F';
64 //3：每个结点指针域赋值
65 PA->Left = PB;
66 PA->Right = PC;
67 PB->Left = PD;
68 PB->Right = NULL;
69 PC->Left = PE;
70 PC->Right = PF;
71 PD->Left = PD->Right = NULL;
72 PE->Left = PE->Right = NULL;
73 PF->Left = PF->Right = NULL;
74 //4：返回根节点
75 return PA;
76 }
77
78 int main(){
79 BinTree pT=CreateBTree();
80 printf("前序遍历：");
81 PreviousTraversal(pT);
82 printf("\n");
83 printf("中序遍历：");
84 MiddleTraversal(pT);
85 printf("\n");
86 printf("后序遍历：");
87 BehindTraversal(pT);
88 printf("\n");
89 return 0;
90 }