二叉树及其实现(基础版)

2022-02-20 20:37:39

前言：常见的数据结构都有指针和数组两种实现方式，这篇先介绍指针实现，而数组实现在后续文章里会讲到。

（长文预警！）

说完了一般的树，我们再来看看二叉树，这是一种很典型的树，它的所有节点度数都不超过2，最多只有两个孩子。这是一种特例，但是后面我们会看到在保证有序性和有根性之后，它却足以描述所有的树。每个节点的出度最多为2，在之前对所有节点按照深度划分的等价类，从规模上看就构成了一个公比为2的等比数列，相应地，深度为k（第k层）的节点，最多有2^k个。那么对于含n个节点、高度为h的二叉树中（这里再多说一句，高度指的是：除了根节点，下面有几层高度就是几，回想一下，空树高度是-1，一个根节点高度为0。），满足这样一个条件：

h<n<2^h+1。

这个性质很好证明。对于上界的情况，树的每一层都是满的，所以从根到第n层累加，总数=1+2+4+…+2^n=2^(n+1)-1，也就是右半部分。而下界情况，根据定义每层至少有一个节点，所以一共h+1个，这种情况下，树就退化为一条单链。

具体来说一下上界的情况，在这个时候节点个数n=2^h-1，是一颗满树，那每一层（每一个等价类）都会到达饱和状态。它的横向上的宽度与在纵向上的高度是呈指数关系的——h=log(W)，高度会增长的很慢。

二叉树及其实现(基础版)

相关实现

讨论了二叉树的基本信息后，就该进入正题了，Talk is cheap,show me the code。现在来谈谈怎么在计算机中实现一棵二叉树。谈一个东西的实现不能脱离实际背景，不然就成了空中楼阁，二叉树也有很多种，比如最大堆，最小堆，优先队列，搜索树，这里给出一个其中一个二叉树的具体例子。首先需要知道的是，二叉树的一个重要应用是他们在查找（搜索）中的使用，那为什么查找往往要依靠树形结构呢？这是很自然的一个问题，前面的文章中我们说过，树结构对静态和动态操作的支持都是十分迅速的，因此是这种高效性使得树结构成为了搜索的“天选之人”。这也告诉我们，如果自身很强，那么遇到机会时才有可能把握住，机会是留给有准备的人（突然鸡汤2333）。

假设树中的每个节点内部存了一个值，任何复杂的值都可以，不过这里为了简单起见，让它们都是int型，同时假设他们是互异的，以后我们再处理有重复值的情形。我们要进行一些操作的前提是：知道规则，有了规则，操作的步骤就一目了然了，这是老师在课上反复强调的。那搜索树的规则就是——对于每个节点X（作为根），左子树中存的所有值都小于X存的值；右子树的所有值都大于X的值。也就是从小到大依次是左-根-右，就像这样：

二叉树及其实现(基础版)

这个性质要引起注意，这意味着树中的所有元素可以用统一的方式排序。为什么要这样说？因为树是递归构造的，其中每一棵子树中都满足这个性质，那我们的排序过程就可以逐步分解到最小的子树中，每个被分解的部分和原来的总体都是“性质相同的子问题”这样一种关系，所以可以用统一的方法，从最小的子问题推而广之，直至解决整个问题。

现在具体说说怎么实现他们，由于树是递归定义的，所以通常递归地编写操作函数，前面说了，二叉树的平均深度是多少来着？忘的话往上翻翻。由于平均深度增长地很慢，所以我们不必担心栈空间被用尽（emmm这怎么突然提到栈了，忘了的话去前面讲栈的文章里翻翻）。先给出一般性的结点声明

1 struct BinNode;
2 typedef struct BinNode *Position;         //只需要拿到某个单结点时用它表示
3 typedef struct BinNode *SearchTree;       //对整棵树操作时，用它表示返回类型
4 
5 struct BinNode{
6     int Value;
7     SearchTree Left,Right;
8 };

这里又遇到和链表那里一样，用两个typedef替换同一个类型的情况了，稍后我们会看到如此逻辑分层的优势，它便于我们在大脑中构建一个清晰的搜索树ADT模型。现在只要知道他们表示的都是一个指向二叉树节点的指针就好了，只是所指示的侧重有细微的不同。按照惯例，先说初始化的操作，然后说查找元素，最后就是重头戏——插入和删除了。每种结构都按这个顺序来讲解看似单调乏味，但这的确是我们从0搭建一个结构的必由之路，从简到繁，自下而上这也符合人类的认知规律。

1 SearchTree MakeEmpty(SearchTree T){
2     if (T){
3         MakeEmpty(T->Left);
4         MakeEmpty(T->Right);
5         free(T);
6     }
7     return NULL;
8 }

给这个函数输入一个节点作为根，然后在它不为空的情况下，逐层递归地销毁它以下的所有子树。注意到了吧，这里用的是“SearchTree”来标识，因为置空后要返回的是一个根节点，实际上从整体理解，是以返回值为根的一整棵树（当然这里是空树）。

再说查找，它要返回的是一个指针，指向我们所查的值所在的结点（既然只返回一个单一结点指针，自然用Position做返回类型更清晰），没有的话就NULL。树的结构使得这种操作很简单，我们先分析一下大体策略：如果T是NULL，也就是走到某一个叶子结点仍然没有找到，那就返回NULL；如果T中存的值是要查找的X，那么返回T的地址；如果既没找到，但也没走到末尾（叶结点）时，就按照X和根节点的大小关系来逐层递归左或右子树：如果比根小，左边，否则右边，这就很类似二分查找的思想。

1 Position Find(int X,SearchTree T){
2     if(T == NULL) return NULL;      //如果走到叶子还没找到，返回空
3     if (X < T->Value)  return Find(X, T->Left); //如果给定值比根小，往左边找
4     else if(X > T->Value) return Find(X , T->Right);//比根大就往右找
5     else return T;  //这种情况就是某时X==T->Value，正好命中的情况
6 }

接着来说两种Find的具体情况，分别是找最小最大值，这种递归写法是很自然的，以至于深受喜爱，不过递归调用过多的话会占用大量资源，这是一个弊端，所以迭代和递归两种方法都要熟稔于心。因此，我们用两种方法编写，FindMin（递归）和FindMax（迭代）。

1 Position FindMin(SearchTree T){
2     if(T == NULL) return NULL;         //同上
3     else if (T->Left==NULL) return  T;   //左子树空，意味着没有比它更小的值了，直接返回地址
4     else return FindMin(T->Left); //如果上面两个情况都不符合，接着往左找
5 }

1 Position FindMax(SearchTree T) {
2     if (T!=NULL)         //没有走到叶结点时寻找
3         while (T->Right!=NULL)    //右边还有子树时一直往右走
4             T=T->Right;
5     return T;             //这个return包含了两种情形，如果传入的是叶子，自动返回NULL，如果找到最右边了，返回对应地址
6 }

同理，查找最小值的如果用迭代来写，就是完全对称的。

1 SearchTree FindMinByLoop(SearchTree T) {
2     if(T)
3         while (T->Left)
4             T=T->Left;
5     return  T;
6 }

这里要注意时如何处理空树这种退化情形的，一定要小心。

接着就是两大重头戏——插入和删除，我们慢慢讨论，对于插入一个数X来讲，从概念上很好理解：先用find查一下，看是不是已经存在，有的话就不用做什么了（或者做一些修改）。如果没有，就把X插到遍历路径的末尾。

比如对于这样一棵树

二叉树及其实现(基础版)

我们要插入66这个数，那么就应该按下面这个路径放置。

二叉树及其实现(基础版)

 1 SearchTree Insert(SearchTree T,int X) {
 2     if(!T){             //这是应对初始情况,空树
 3         T=(SearchTree)malloc(sizeof(struct BinNode));
 4         T->Value=X;
 5         T->Left=T->Right=NULL;  //底部封口
 6     }
 7     //在一棵现成的树里插入，二分查找
 8     else if (X < T->Value) T->Left=Insert(T->Left, X);
 9     else if (X > T->Value) T->Right=Insert(T->Right, X);
10     //X==T->Value的情况什么也不用做
11     return T;
12 }

而正如许多数据结构一样，最困难的是删除，因为这会涉及到好多种情况，我们都需要将其考虑在内。

节点是一片叶子
节点有一个儿子
节点有两个儿子

分类讨论，1.叶子的话就直接删除。

2.只有一个儿子的话，就可以在它的父节点调整指针时绕过该节点后被删除。

二叉树及其实现(基础版)

这棵树中，删除4

二叉树及其实现(基础版)

从父节点直接绕过去，bypass

二叉树及其实现(基础版)

而有两个儿子的话情况就复杂了，一般来说是用它右子树下最小的数据来代替该节点数据并递归删除。因为右子树下面最小的节点不可能有左儿子，所以第二次delete就更容易了。

//好像插入不了视频……所以请点击这里查看删除演示。如果你们知道怎么弄，请在评论里告诉我，我试过插入源代码，还是不行Orz

总结起来就是：

search for v

if v is a leaf

delete leaf v

else if v has 1 child

bypass v

else replace v with successor

代码如下

 1 SearchTree Delete(int X,SearchTree T) {
 2     Position TempCell;
 3     if (T==NULL)
 4          printf("Element not found\n");
 5     //search for Value
 6     
 7     else if(X<T->Value) T->Left=Delete(X, T->Left);
 8     else if(X>T->Value) T->Right=Delete(X, T->Right);
 9     //找到给定的X了，开始分类讨论
10     else if(T->Left && T->Right){   //有两个儿子的情况
11         TempCell=FindMin(T->Right);     //找到右子树下最小的数据
12         T->Value=TempCell->Value;   //Replace
13         T->Right=Delete(T->Value, T->Right);  //递归删除
14     }
15     else{       //1个儿子or叶子的情况,可以统一起来，操作逻辑是一致的
16         TempCell=T;
17         if (T->Left==NULL)  T=T->Right;       //只有右孩子，就把父节点直接连到右边
18         else if (T->Right==NULL) T=T->Left;  //只有左孩子，就把父节点直接连到左边
19     free(TempCell);
20     }
21     return T;
22 }

这里0 or 1 children的情况在实现的时候统一写了，不用再讨论他们的差别了。因为即使是叶子，进入分支后也就相当于原来的T=T->Right效果变成了T=NULL，同样达到了目的。如果我们一开始来写，可能会多写一条分支判断是否为叶子，这样代码就显得冗余了，也正因此我们需要慢慢品味上面这种写法的精妙之处。

小零件我们都写好了，下面就需要把他们粘合起来，形成一个有机的系统了。怎么粘合才能让他们各个部分有序而协调地运转呢？先走谁后走谁的问题就涉及到了遍历规则了，所以下面我们来讨论树的遍历。

遍历

树的主要遍历方式有四种：Pre/In/Post order和Level order,前者对应着深搜，后者对应广搜。层序遍历是按照离根节点的距离由远及近地访问。与层序不同，其他三种都是根据对根节点的访问次序来划分的。如果是先于左右子树，那就是Preorder,如果是介于左右子树之间，就是Inorder，如果是位于左右子树遍历之后，就是Postorder。

二叉树及其实现(基础版)

通过这张图我们来对比记忆，下面详细说明每种方法。

二叉树及其实现(基础版)

这是层序遍历，结果是ADBFHCEG。它的思想是用一个队列来维护，对于每个节点进行如下操作：

1.将这个节点入队

2.打印后出队

3.接着把该节点所有孩子按顺序入队

然后对所有孩子重复第2，3步，很显然，这是用递归轻松解决的。

二叉树及其实现(基础版)

这是先序遍历，而这条红色的线有一个名字叫Euler tour，preorder的结果就是GDBFAHEIC。

postorder的话，就是FBDEIHCAG，inorder的结果是：DFBGEHIAC。

1 void PreOrder(SearchTree T) {
2     if(T){                  //如果这颗子树非空，就打印，否则把控制权还给上级
3     printf("%d ",T->Value);
4     PreOrder(T->Left);
5     PreOrder(T->Right);
6     }
7 }

中序的情况类似

1 void InOrder(SearchTree T){
2     if(T){
3         InOrder(T->Left);
4         printf("%d ",T->Value);
5         InOrder(T->Right);
6     }
7 }

后序同理，只是打印顺序略有区别，这里不再赘述。不过我要说的是，后序有一个妙用，就是计算树的高度，当然其他方式也可以，不过后序最符合人的思维习惯。

1 int Height(SearchTree T){
2     //下面这两句都是根据定义得出的
3     if(!T) return -1;
4     else return 1+max(Height(T->Left), Height(T->Right));
5 }

而层序遍历就稍微复杂一些了，因为它涉及到如何判断“某个节点是否被访问”以及“如何按照远近关系来行进”，这就需要我们为其指定一个优先级，故需要队列。

 1 void LevelOrder(SearchTree r) {
 2     SearchTree current=r;     //为了不修改根节点，新建一个指针作为光标
 3     queue<SearchTree> q;
 4     q.push(current);        //把当前（根）节点入队
 5     //以下是广搜的核心
 6     while (!q.empty()) {        //队列非空时进行遍历
 7         current=q.front();
 8         printf("%d ",current->Value);
 9         q.pop();            //打印完则出队
10         if (current->Left)            //依次查看当前节点是否有后继，有的话重复上述入队过程，left,right or both
11             q.push(current->Left);
12         if (current->Right)
13             q.push(current->Right);
14     }
15 }

最后看一个具体的总实现，给出演示程序。

以这个为例，插入17，删除72

就分别变成

和

  1 //出于布局合理的考虑，把主函数放在中间。
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <ctime>
  5 #include <queue>
  6 using namespace std;
  7 
  8 struct BinNode;
  9 typedef struct BinNode *SearchTree;
 10 typedef struct BinNode *Position;
 11 struct BinNode{
 12     int Value;
 13     SearchTree Left,Right;
 14 };
 15 
 16 SearchTree root=NULL;
 17 
 18 // Function signature
 19 SearchTree Insert(SearchTree T,int X);
 20 SearchTree Delete(int X,SearchTree T);
 21 int Height(SearchTree T);
 22 void PreOrder(SearchTree T);
 23 void InOrder(SearchTree T);
 24 void LevelOrder(SearchTree T);
 25 void DisplayInfo(SearchTree t);
 26 Position FindMax(SearchTree T);
 27 Position FindMix(SearchTree T);
 28 //Entrance
 29 int main(){
 30     int n;
 31     printf("Could you tell me what the tree looks like?(0 to complete)\n");
 32     while (scanf("%d",&n) && n)
 33         root=Insert(root, n);
 34     printf("\n");
 35     DisplayInfo(root);
 36     printf("Which guys will be pushed?\n"); scanf("%d",&n);
 37     root=Insert(root, n); DisplayInfo(root);
 38     printf("Which value do you desire to remove?\n");  scanf("%d",&n);
 39     root=Delete(n, root);
 40     DisplayInfo(root);  printf("\n");
 41 }
 42 
 43 //接口内部一览
 44 SearchTree MakeEmpty(SearchTree T){
 45     if (T){
 46         MakeEmpty(T->Left);
 47         MakeEmpty(T->Right);
 48         free(T);
 49     }
 50     return NULL;
 51 }
 52 
 53 Position Find(int X,SearchTree T){
 54     if(T == NULL) return NULL;      //如果走到叶子还没找到，返回空
 55     if (X < T->Value)  return Find(X, T->Left); //如果给定值比根小，往左边找
 56     else if(X > T->Value) return Find(X , T->Right);//比根大就往右找
 57     else return T;  //这种情况就是某时X==T->Value，正好命中的情况
 58 }
 59 
 60 Position FindMin(SearchTree T){
 61     if(T == NULL) return NULL;         //同上
 62     else if (T->Left==NULL) return  T;   //左子树空，意味着没有比它更小的值了，直接返回地址
 63     else return FindMin(T->Left); //如果上面两个情况都不符合，接着往左找
 64 }
 65 
 66 void DisplayInfo(SearchTree t){
 67     printf("\nCurrently\nPre-order is :");
 68     PreOrder(t);   printf("\n");
 69     printf("In-order is :");
 70     InOrder(t);    printf("\n");
 71     printf("Level-order is :");
 72     LevelOrder(t); printf("\n");
 73     printf("Height is %d\n",Height(root));
 74     printf("The min is: %d\n",FindMin(root)->Value);
 75     printf("The max is: %d\n",FindMax(root)->Value);
 76 }
 77 
 78 int Height(SearchTree T){
 79     //这两句都是根据定义得出的
 80     if(!T) return -1;
 81     else return 1+max(Height(T->Left), Height(T->Right));
 82 }
 83 SearchTree FindMinByLoop(SearchTree T) {
 84     if(T)
 85         while (T->Left)
 86             T=T->Left;
 87     return  T;
 88 }
 89 
 90 Position FindMax(SearchTree T) {
 91     if (T!=NULL)         //没有走到叶结点时寻找
 92         while (T->Right!=NULL)    //右边还有子树时一直往右走
 93             T=T->Right;
 94     return T;             //这个return包含了两种情形，如果传入的是叶子，自动返回NULL，如果找到最右边了，返回对应地址
 95 }
 96 
 97 SearchTree Insert(SearchTree T,int X) {
 98     if(!T){             //这是应对初始情况,空树
 99         T=(SearchTree)malloc(sizeof(struct BinNode));
100         T->Value=X;
101         T->Left=T->Right=NULL;  //底部封口
102     }
103     //在一棵现成的树里插入，二分查找
104     else if (X < T->Value) T->Left=Insert(T->Left, X);
105     else if (X > T->Value) T->Right=Insert(T->Right, X);
106     //X==T->Value的情况什么也不用做
107     return T;
108 }
109 SearchTree Delete(int X,SearchTree T) {
110     Position TempCell;
111     if (T==NULL)
112             printf("Element not found\n");
113     //search for Value
114     
115     else if(X<T->Value) T->Left=Delete(X, T->Left);
116     else if(X>T->Value) T->Right=Delete(X, T->Right);
117     //找到给定的X了，开始分类讨论
118     else if(T->Left && T->Right){   //有两个儿子的情况
119             TempCell=FindMin(T->Right);     //找到右子树下最小的数据
120             T->Value=TempCell->Value;   //Replace
121             T->Right=Delete(T->Value, T->Right);  //递归删除
122         }
123     else{       //1个儿子or叶子的情况,可以统一起来，操作逻辑是一致的
124         TempCell=T;
125         if (T->Left==NULL)       //只有右孩子，就把父节点直接连到右边
126                 T=T->Right;
127         else if (T->Right==NULL){   //只有左孩子，就把父节点直接连到左边
128                 T=T->Left;
129             }
130         free(TempCell);
131         }
132     return T;
133 }
134 
135 
136 void PreOrder(SearchTree T) {
137     if(T){                  //如果这颗子树非空，就打印，否则把控制权还给上级
138     printf("%d ",T->Value);
139     PreOrder(T->Left);
140     PreOrder(T->Right);
141     }
142 }
143 void InOrder(SearchTree T){
144     if(T){
145         InOrder(T->Left);
146         printf("%d ",T->Value);
147         InOrder(T->Right);
148     }
149 }
150 
151 void LevelOrder(SearchTree r) {
152     SearchTree current=r;     //为了不修改根节点，新建一个指针作为光标
153     queue<SearchTree> q;
154     q.push(current);        //把当前（根）节点入队
155     //以下是广搜的核心
156     while (!q.empty()) {        //队列非空时进行遍历
157         current=q.front();
158         printf("%d ",current->Value);
159         q.pop();            //打印完则出队
160         if (current->Left)            //依次查看当前节点是否有后继，有的话重复上述入队过程，left,right or both
161             q.push(current->Left);
162         if (current->Right)
163             q.push(current->Right);
164     }
165 }

码农公寓

相关实现

遍历

相关文章