1 #include<stdio.h>
2 #include<malloc.h>
3
4 struct BTNode{
5 char data;//数据域
6 struct BTNode * pLchild;//p是指针,L是左,child是孩子;即为左子树指针
7 struct BTNode * pRchild//右子树指针
8 }
9 //函数声明
10 struct BTNode * CreateBTree();//生成根节点地址和二叉树
11 PreTraverseBTree();//先序遍历
12 InTraverseBTree();//中序遍历
13 PostTraverseBTree();//后序遍历
14
15 int main(){
16 struct BTNode * pT = CreateBTree();//获取根节点地址
17
18 PreTraverseBTree(pT);//先序遍历
19 InTraverseBTree(pT);//中序遍历
20 PostTraverseBTree(pT);//后序遍历
21
22 return 0;
23 }
24
25 struct BTNode * CreateBTree(){
26 //静态声明结点,动态分配内存
27 struct BTNode pA = (struct BTNode *)malloc(sizeof(struct BTNode));
28 struct BTNode pB = (struct BTNode *)malloc(sizeof(struct BTNode));
29 struct BTNode pC = (struct BTNode *)malloc(sizeof(struct BTNode));
30 struct BTNode pD = (struct BTNode *)malloc(sizeof(struct BTNode));
31 struct BTNode pE = (struct BTNode *)malloc(sizeof(struct BTNode));
32
33 //各个结点数据域存值
34 pA->data = 'A';
35 pB->data = 'B';
36 pC->data = 'C';
37 pD->data = 'D';
38 pE->data = 'E';
39
40 //每个结点的左右指针域都要指向一个地址,注:为空就写NULL
41 pA->pLchild = pB;//根节点A的左指针域指向B结点的地址
42 pA->pRchild = pC;//根节点A的右指针域指向C结点的地址
43 pB->pLchild = pB->pRchild = NULL;//结点B的左右指针域都为空
44 pC->pLchild = pD;//节点C的左指针域指向D结点的地址
45 pC->pRchild = NULL;//结点C的右指针域为空
46 pD->pLchild = NULL;//结点D的左指针域为空
47 pD->pRchild = pE;//结点D的右指针域指向E结点的地址
48 pE->pLchild = pE->pRchild = NULL;//结点E的左右指针域都为空
49
50 return pA;//返回根节点A的地址
51 }
52
53 //先序遍历
54 PreTraverseBTree(struct BTNode * pT){
55 //每次递归加判断,若先遍历左子树全部为空就结束递归,才能遍历右子树
56 if(pT!=NULL){
57
58 printf("%c\n",pT->data);//先访问根节点
59
60 if(pT->pLchild!=NULL){
61 PreTraverseBTree(pT->pLchild);//pT->pLchild可以代表整个左子树
62 }//再访问左子树
63
64 if((pT->pRchild!=NULL){
65 PreTraverseBTree(pT->pRchild);//pT->pRchild可以代表整个右子树
66 }//最后访问右子树
67 }
68 }
69
70 //中序遍历
71 InTraverseBTree(struct BTNode * pT){
72 if(pT!=NULL){
73
74 if(pT->pLchild!=NULL){
75 PreTraverseBTree(pT->pLchild);//pT->pLchild可以代表整个左子树
76 }//先访问左子树
77
78 printf("%c\n",pT->data);//再访问根节点
79
80 if((pT->pRchild!=NULL){
81 PreTraverseBTree(pT->pRchild);//pT->pRchild可以代表整个右子树
82 }//最后访问右子树
83 }
84 }
85
86 //后序遍历
87 PostTraverseBTree(struct BTNode * pT){
88 if(pT!=NULL){
89
90 if(pT->pLchild!=NULL){
91 PreTraverseBTree(pT->pLchild);//pT->pLchild可以代表整个左子树
92 }//先访问左子树
93
94 if((pT->pRchild!=NULL){
95 PreTraverseBTree(pT->pRchild);//pT->pRchild可以代表整个右子树
96 }//再访问右子树
97
98 printf("%c\n",pT->data);//最后访问根节点
99 }
100 }