《数据布局（C语言版）第二版》第五章-树和二叉树（5.4-5.5.1）

5.4 二叉树的性子和存储布局

5.5 遍历二叉树和线索二叉树

5.5.1 遍历二叉树

先序、中序、后序遍历的递归算法

1. //算法5.1 先序、中序、后序遍历的递归算法
2. #include <stdio.h>
3. #include  <stdlib.h>
5. typedef char TElemType;
7. typedef struct BiTNode
8. {
9.    
10.    
11.         TElemType data;
12.         struct BiTNode* lchild;
13.         struct BiTNode* rchild;
14. }BiTNode, * BiTree;
16. void InitBiTree(BiTree& T);
17. void CreateBiTree(BiTree& T);
18. void preOrderTraverse(BiTree& T);
19. void InOrderTraverse(BiTree& T);
20. void posOrderTraverse(BiTree& T);
22. //ABC##DE#G##F###
24. int main()
25. {
26.    
27.    
28.         BiTree Tree = NULL;
30.         InitBiTree(Tree);
31.         printf("请输入要用二叉链表表示的字符序列： ");
32.         CreateBiTree(Tree);
34.         printf("\n二叉链表的先序序列为： ");
35.         preOrderTraverse(Tree);
37.         printf("\n二叉链表的中序序列为： ");
38.         InOrderTraverse(Tree);
40.         printf("\n二叉链表的后序序列为： ");
41.         posOrderTraverse(Tree);
43.         return 0;
44. }
46. //初始化二叉树
47. void InitBiTree(BiTree& T)
48. {
49.    
50.    
51.         T = NULL;
52. }
54. //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
55. //由于先序遍历的顺序是“根节点-左子树-右子树”，因此仅有先序可以正确创建二叉树，当根结点为空时，令其整个二叉树为空，而不用管左右子树
56. void CreateBiTree(BiTree& T)
57. {
58.    
59.    
60.         TElemType ch = '\0';
61.        
62.         ch = getchar();  
63.         /* getchar从键盘获取且只能获取一个字符。
64.           接收空格和制表符（空格或制表符会被算作一个正常字符读入一次），
65.           不接收回车，遇到回车即认为本次输入结束。
66.           但末尾输入的回车会被留在缓存流中，在下一次被getchar读取到（吃掉回车），并将该回车作为本次输入的结束。
67.         */
69.         //scanf_s(" %c", &ch); //用scanf_s会将整个字符序列写进ch中，无法进行递归创建二叉树
70.         /*scanf_s在输入的末尾遇到空白符（空格符、回车符(\n)和制表符(\t)等） 时，都会认为本次输入结束。
72.           对于参数%d：会忽略缓冲区开头的空白符（空格、回车、制表符等）（无论有几个），只从数字开始读取。
73.           但对输入末尾的非数字字符，包括空白符，则可能进入无限循环程序，使得无法进行下一次输入；
75.           对于参数%c：会直接读取缓冲区的第一个字符（无论这个字符是什么）。
76.           所以一般需要在%c前面加一个空格，利用格式化的输入方式，使得遇到空格的scanf_s认为本次输入已结束，
77.           直接等待下一次输入，而放弃缓冲区内的所有字符，来跳过上一次输入末尾的换行符。
78.         */
80.         if (ch == '#')
81.         {
82.    
83.    
84.                 T = NULL;
85.         }
86.         else
87.         {
88.    
89.    
90.                 T = (BiTree)malloc(sizeof(BiTNode));
91.                 T->data = ch;
92.                 CreateBiTree(T->lchild);
93.                 CreateBiTree(T->rchild);
94.         }
95. }
97. //先序遍历二叉树
98. void preOrderTraverse(BiTree& T)
99. {
100.    
101.    
102.         if (T)  //只有当T不为空时才访问它的成员
103.         {
104.    
105.    
106.                 printf(" %c", T->data);
107.                 preOrderTraverse(T->lchild);
108.                 preOrderTraverse(T->rchild);
109.         }
110. }
112. //中序遍历二叉树
113. void InOrderTraverse(BiTree& T)
114. {
115.    
116.    
117.         if (T)
118.         {
119.    
120.    
121.                 InOrderTraverse(T->lchild);
122.                 printf(" %c", T->data);
123.                 InOrderTraverse(T->rchild);
124.         }
125. }
127. //后序遍历二叉树
128. void posOrderTraverse(BiTree& T)
129. {
130.    
131.    
132.         if (T)
133.         {
134.    
135.    
136.                 posOrderTraverse(T->lchild);
137.                 posOrderTraverse(T->rchild);
138.                 printf(" %c", T->data);
139.         }
140. }

复制代码

先序、中序、后序遍历的非递归算法

1. //先序、中序、后序遍历二叉树的非递归算法
3. #include <stdio.h>
4. #include  <stdlib.h>
6. typedef char TElemType;
8. typedef struct BiTNode
9. {
10.    
11.    
12.         TElemType data;
13.         struct BiTNode* lchild;
14.         struct BiTNode* rchild;
15. }BiTNode, * BiTree;
17. //链栈的数据结构
18. typedef struct StackNode
19. {
20.    
21.    
22.         BiTree TNodeptr;
23.         struct StackNode* next;
24. }StackNode, * LinkStack;
26. void InitStack(LinkStack& S);
27. void Push(LinkStack& S, BiTree p);
28. BiTree Pop(LinkStack& S);
29. BiTree GetTop(LinkStack& S);
30. int EmptyStack(LinkStack& S);
31. void InitBiTree(BiTree& T);
32. void CreateBiTree(BiTree& T);
33. void preOrderTraverse(BiTree& T);
34. void InOrderTraverse(BiTree& T);
35. void posOrderTraverse(BiTree& T);
37. /* 按先序次序输入二叉树中结点的值：(输入的结尾一定是两个#号)
38.         ABC##DE#G##F###
39.         -*a##b##c##
40.         ABD##E##C##        */
42. int main()
43. {
44.    
45.    
46.         BiTree Tree = NULL;
47.         InitBiTree(Tree);
49.         char choice = '\0';
51.         while (1)
52.         {
53.    
54.    
55.                 printf("请输入要用二叉链表表示的字符先序序列： ");
56.                 CreateBiTree(Tree);
58.                 printf("\n二叉链表的先序序列为： ");
59.                 preOrderTraverse(Tree);
61.                 printf("\n二叉链表的中序序列为： ");
62.                 InOrderTraverse(Tree);
64.                 printf("\n二叉链表的后序序列为： ");
65.                 posOrderTraverse(Tree);
67.                 printf("\n是否继续？(y/n)：");
68.                 scanf_s(" %c", &choice);
69.                 getchar();
70.                 if (choice != 'y' && choice != 'Y')
71.                 {
72.    
73.    
74.                         break;
75.                 }
77.                 printf("\n\n");
78.         }
80.         return 0;
81. }
83. //初始化栈
84. void InitStack(LinkStack& S)
85. {
86.    
87.    
88.         S = NULL;
89. }
91. //元素进栈
92. void Push(LinkStack& S, BiTree p)
93. {
94.    
95.    
96.         struct StackNode* r = NULL;
97.         r = (struct StackNode*)malloc(sizeof(struct StackNode));
99.         if (!r)
100.         {
101.    
102.    
103.                 printf("创建新结点时，内存分配失败。");
104.                 return;
105.         }
107.         r->TNodeptr = p;
108.         r->next = S;
109.         S = r;
110. }
112. //栈顶元素出栈
113. BiTree Pop(LinkStack& S)
114. {
115.    
116.    
117.         if (!S)
118.         {
119.    
120.    
121.                 printf("弹出栈顶元素时，栈不存在。");
122.                 return NULL;
123.         }
125.         struct StackNode* r = S;
126.         BiTree a = S->TNodeptr;
127.         S = S->next;
128.         free(r);
129.         return a;
130. }
132. //获取栈顶元素
133. BiTree GetTop(LinkStack& S)
134. {
135.    
136.    
137.         if (!S)
138.         {
139.    
140.    
141.                 printf("获取栈顶元素时，栈不存在。");
142.                 return NULL;
143.         }
145.         return S->TNodeptr;
146. }
148. //判断栈是否为空
149. int EmptyStack(LinkStack& S)
150. {
151.    
152.    
153.         if (!S)
154.         {
155.    
156.    
157.                 return 1;
158.         }
159.         else
160.         {
161.    
162.    
163.                 return 0;
164.         }
165. }
167. //初始化二叉树
168. void InitBiTree(BiTree& T)
169. {
170.    
171.    
172.         T = NULL;
173. }
175. //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
176. void CreateBiTree(BiTree& T)
177. {
178.    
179.    
180.         TElemType ch = '\0';
182.         ch = getchar();
184.         if (ch == '#')
185.         {
186.    
187.    
188.                 T = NULL;
189.         }
190.         else
191.         {
192.    
193.    
194.                 T = (BiTree)malloc(sizeof(BiTNode));
195.                 T->data = ch;
196.                 CreateBiTree(T->lchild);
197.                 CreateBiTree(T->rchild);
198.         }

复制代码