C语言版二叉树构造&&遍历_二叉查找树的构造与遍历c语言
赞
踩
二叉树构造&&遍历
基于二分搜索的启发，将查找的复杂度由朴素的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
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
三种遍历非递归版＋层序遍历堆栈版
从代码中不难发现，只有层序遍历是不依赖于递归的，但实际上，我们可以将前三种遍历使用堆栈来统统改成非递归实现，并且，原本使用队列的层序遍历，也可用堆栈实现。
因为Ｃ语言无自带的堆栈，故手动实现一个
// 再实现一个栈(依旧很粗糙) 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
先序&&中序
然后便是先序和中序的非递归实现，(后序遍历稍复杂，稍后再补上)
// 先序遍历(非递归) 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; } } }
- 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
不难发现，这两种遍历方式其实仅仅是打印字符的位置不一样，思路都是一样的。
以中序遍历为例，仔细思考，其实本质和dfs相似，即不断地访问－回溯－访问－回溯－……堆栈的作用就是存储之前访问过的节点，即“留后路”，在当前无法继续探索的时候(左子树为空)，可以回溯到父亲节点，从而再探寻父亲节点的右子树。在这个父亲－左儿子－父亲－右儿子的过程中，若第一次访问父亲时输出，则为先序遍历，若在第二次时输出，则为中序遍历，但是我们悲催地发现，父亲并没有第三次遍历的机会，因为所谓第一次访问是其进栈时，第二次访问是其弹栈时，不存在第三种机会，故后序遍历需要其他变量来记录某节点第三次遍历时的情况。
后序
经过大量寻找，在不改变二叉树结构体的情况下，得到了如下算法
// 后序遍历非递归版 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(); } } } }
- 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
算法的思想核心是这样的，为了解决如何判定此节点是否为第三次遍历的问题，我们在先序、中序算法的基础上作出改进。即在回溯阶段，不立即将节点出栈，而是判断其右子树是否遍历过或者右子树是否为空，若满足这两个条件，则弹栈，若不满足，则处理右子树。
但是！仍然存在问题：如何判断右子树已经遍历过？此算法是引入一个新的变量( p )，用来标注发动回溯的节点位置，然后若标记节点是回溯后的节点的右儿子 或者 回溯后节点的右儿子为空，则弹栈，否则，进入右子树继续处理。当然，处理过右子树时，又发生相同的情况，此时条件满足，弹栈，继续回溯处理。
层序
这个实在是令我摸不着头脑，这样把队列换成栈有意义吗？甚至牛客网上还有一道题专门问这个。
但是我还是好奇的搜索着答案，在Mooc评论区里找到了一种做法：准备两个栈s1和s2，s1用于存放当前层次的节点，s2用于存放此节点产生的左右儿子，s1产生的先暂存于s2中，待s1处理完毕后，再将s2中的"倒入"s1，继续处理，且务必保证右儿子先入栈。
后续随缘更新
