二叉树构造&&遍历
基于二分搜索的启发，将查找的复杂度由朴素的O(n) 降低至 O(log n),故产生此数据结构 : 二叉树。
二叉树有两种构造方式，一种是顺序存储格式，也就是用数组来存储；另一种是链表。 他们的优缺点和线性表中几乎一样：
数组支持随机存取，实现简单，结构直观，缺点是添加删除不便，而且空间固定，不易修改，要么不足，要么浪费。 链式的结构复杂，遍历需要算法，C语言指针可能会造成各种非预期的结果，而且调试困难，但是灵活，不拘泥于固定的大小，插入删除方便。 —
顺序遍历方法
若根结点的下标为１，则有
对于结点 i ，其父节点是i/2，其左儿子为 i*2，右儿子为 i*2+1，（亦可写作 i<<1 和 i<<1|1，逼格满满)
因此对于满二叉树，这个是比较简单且划算的，没有空间的浪费，(满二叉树是在完全二叉树的基础上要求叶子处在同一深度)
链式遍历方法
三种遍历递归版＋层序遍历队列版
// 二叉树 构造&&遍历 ,参照浙大MOOC上的资料实现
#include <stdio.h>
#include <stdlib.h>
// 以后多提前声明,就能减少很多麻烦
struct TreeNode;
typedef char ElemType;
typedef struct TreeNode *BinTree;
typedef BinTree Position;
// 真正的定义
struct TreeNode {
ElemType Data;
BinTree Left;
BinTree Right;
};
// 简单实现一个队列(虽说应该构建一个动态的,但这里不是重点,不要喧宾夺主)
BinTree queue[100];
int first = 0, last = 1, len = 100;
// 队列插入
void QuePush(BinTree elem);
// 队列删除
BinTree QuePop(void);
// 构建一棵树,仍然是采用递归的思想
BinTree CreatTree();
// 先序遍历
void PreOrderTraversal(BinTree BT);
// 中序遍历
void InOrderTraversal(BinTree BT);
// 后序遍历
void PostOrderTraversal(BinTree BT);
// 层序遍历
void LeverlOrderTraversal(BinTree BT);
int main() {
BinTree T;
T = CreatTree();
printf("先序遍历: \n");
PreOrderTraversal(T);
printf("中序遍历: \n");
InOrderTraversal(T);
printf("后序遍历: \n");
PostOrderTraversal(T);
printf("层序遍历: \n");
LeverlOrderTraversal(T);
return 0;
}
void PreOrderTraversal(BinTree BT) {
if (BT) {
printf("%c\n", BT->Data);
PreOrderTraversal(BT->Left);
PreOrderTraversal(BT->Right);
}
}
void InOrderTraversal(BinTree BT) {
if (BT) {
InOrderTraversal(BT->Left);
printf("%c\n", BT->Data);
InOrderTraversal(BT->Right);
}
}
void PostOrderTraversal(BinTree BT) {
if (BT) {
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%c\n", BT->Data);
}
}
// 非常有趣,是用队列实现的
void LeverlOrderTraversal(BinTree BT) {
printf("%c\n", BT->Data);
QuePush(BT->Left);
QuePush(BT->Right);
BinTree tmp = QuePop();
while (tmp != NULL) {
printf("%c\n", tmp->Data);
if (tmp->Left)
QuePush(tmp->Left);
if (tmp->Right)
QuePush(tmp->Right);
tmp = QuePop();
}
}
void QuePush(BinTree elem) {
if (first == last) {
printf("Cannot PUSH!\n");
return;
}
queue[last] = elem;
last = (last + 1) % len;
}
BinTree QuePop(void) {
if ((first + 1) % len == last) {
// printf("Cann.ot POP\n");
return NULL;
}
BinTree tmp = queue[first + 1];
first = (first + 1) % len;
return tmp;
}
BinTree CreatTree() {
char ch;
BinTree t;
ch = (char) getchar();
if (ch == ' ') {
t = NULL;
} else {
t = (BinTree) malloc(sizeof(struct TreeNode));
t->Data = ch;
t->Left = CreatTree();
t->Right = CreatTree();
}
return t;
}
三种遍历非递归版＋层序遍历堆栈版
从代码中不难发现，只有层序遍历是不依赖于递归的，但实际上，我们可以将前三种遍历使用堆栈来统统改成非递归实现，并且，原本使用队列的层序遍历，也可用堆栈实现。
因为Ｃ语言无自带的堆栈，故手动实现一个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 再实现一个栈(依旧很粗糙)
BinTree stack[100];
int top = 0, stacklen = 99;
// 清空栈
void StaClear() {
top = 0;
}
// 判断栈是否为空(C99前版本无布尔型)
int StaIsEmpty() {
if (top == 0)
return 1;
return 0;
}
// 压栈
void StaPush(BinTree elem) {
if (top == 99) {
printf("Stack is FULL!\n");
return;
}
top++;
stack[top] = elem;
}
// 弹栈
BinTree StaPop() {
if (top == 0) {
printf("Empty Stack!\n");
return NULL;
}
BinTree tmp = stack[top];
top--;
return tmp;
}
// 取栈顶元素
BinTree StaTop() {
if (!StaIsEmpty()) {
return stack[top];
}
return NULL;
}
先序&&中序
然后便是先序和中序的非递归实现，(后序遍历稍复杂，稍后再补上)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 先序遍历(非递归)
void New_pre(BinTree BT) {
BinTree T = BT;
StaClear();
while (T || !StaIsEmpty()) {
while (T) {
printf("%c\n", T->Data);
StaPush(T);
T = T->Left;
}
if (!StaIsEmpty()) {
T = StaPop();
T = T->Right;
}
}
}
// 中序遍历(非递归)
void New_InOrder(BinTree BT) {
BinTree T = BT;
StaClear();
while (T || !StaIsEmpty()) {
while (T) {
StaPush(T);
T = T->Left;
}
if (!StaIsEmpty()) {
T = StaPop();
printf("%c\n", T->Data);
T = T->Right;
}
}
}
不难发现，这两种遍历方式其实仅仅是打印字符的位置不一样，思路都是一样的。
以中序遍历为例，仔细思考，其实本质和dfs相似，即不断地访问－回溯－访问－回溯－……堆栈的作用就是存储之前访问过的节点，即“留后路”，在当前无法继续探索的时候(左子树为空)，可以回溯到父亲节点，从而再探寻父亲节点的右子树。在这个父亲－左儿子－父亲－右儿子的过程中，若第一次访问父亲时输出，则为先序遍历，若在第二次时输出，则为中序遍历，但是我们悲催地发现，父亲并没有第三次遍历的机会，因为所谓第一次访问是其进栈时，第二次访问是其弹栈时，不存在第三种机会，故后序遍历需要其他变量来记录某节点第三次遍历时的情况。
后序
经过大量寻找，在不改变二叉树结构体的情况下，得到了如下算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 后序遍历非递归版
void New_Post(BinTree BT) {
BinTree T = BT; // 当前节点
BinTree p = BT; // position 位置
StaClear();
while (T || !StaIsEmpty()) {
// 尽可能地往左子树走
while (T) {
StaPush(T);
T = T->Left;
}
// 无法向左走，开始回溯
if (!StaIsEmpty()) {
BinTree top = StaTop();
if (top->Right && top->Right != p)
T = top->Right;
else {
printf("%c\n", top->Data);
p = top;
StaPop();
}
}
}
}
算法的思想核心是这样的，为了解决如何判定此节点是否为第三次遍历的问题，我们在先序、中序算法的基础上作出改进。即在回溯阶段，不立即将节点出栈，而是判断其右子树是否遍历过或者右子树是否为空，若满足这两个条件，则弹栈，若不满足，则处理右子树。
但是！仍然存在问题：如何判断右子树已经遍历过？此算法是引入一个新的变量( p )，用来标注发动回溯的节点位置，然后若标记节点是回溯后的节点的右儿子 或者 回溯后节点的右儿子为空，则弹栈，否则，进入右子树继续处理。当然，处理过右子树时，又发生相同的情况，此时条件满足，弹栈，继续回溯处理。
层序
这个实在是令我摸不着头脑，这样把队列换成栈有意义吗？甚至牛客网上还有一道题专门问这个。
但是我还是好奇的搜索着答案，在Mooc评论区里找到了一种做法：准备两个栈s1和s2，s1用于存放当前层次的节点，s2用于存放此节点产生的左右儿子，s1产生的先暂存于s2中，待s1处理完毕后，再将s2中的”倒入”s1，继续处理，且务必保证右儿子先入栈。
