【图解数据结构】树和二叉树全面总结

作者：知心宝贝

2022 年 3 月 17 日
本文字数：3412 字
阅读完需：约 11 分钟

一、前言

学习目标 1：掌握树和二叉树的基本概念、五大性质、判断完全二叉树、满二叉树。
学习目标 2：记住二叉树的四大遍历、要求写出遍历顺序和相应的递归代码。搞懂二叉树和树的相互转换流程
重点：二叉树的遍历、性质、二叉树和树的相互转换

二、概念及定义

1.树

什么叫树？是下面这个？

抽象很到位，但经历过数据结构的人，下面这张图更加到位哦：

请理清一下上面这张图的人物关系：

上面这张图只有一个根节点，祖父作为根可以叫做大根堆，而你作为根只能叫做小根堆。向下发散出不同的结点，一个结点下面连着几个线叫做度，而下面没有了结点就称为叶子。

同一层的叫兄弟结点，下一层的叫孩子节点。有几代人就有几个层次，层次最大值叫做这个家族的高度，生的孩子数目最多的叫做这个家族的度。

2.二叉树

二叉树，二叉树字面意思就是一个树只能分两个叉。左面的叉叫做左孩子，右面的叉叫做右孩子。

官方术语：满足每个结点度不大于 2，孩子结点次序确定的树。

3.满二叉树

满二叉树就是满的，意思是每一层都是最大的结点，不能有空。

4.完全二叉树

结点按照编号从左到右依次构建二叉树，不存在无左孩子、却有右孩子的情况（有就不是）
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

三、二叉树的性质

俗话说：性质学得好，弯路少走一半！

1.层结点

在二叉树的第 i 层上最多有 2^{i-1}个结点(i>=1)

2.总结点

深度为 k 的二叉树最多有 2^{k}-1 个结点(k>=1)

3.深度

向下取整，比如 4.5 向下取整为 4

4.结点数

对于任意一棵二叉树，度为 0 的结点数等于度为 2 的结点数+1。

5.孩子结点

结点为 i 双亲结点为 i/2 向下取整，左孩子 2* i，右孩子 2*i+1

上面的性质我就不推导了，其实就是实在不想写了。

四、二叉树的遍历

1.先序遍历

算法讲解

遍历顺序：根结点->左子树->右子树
动态图解：和上面的动态图一样，先序遍历就像一个小人从根结点开始，围绕二叉树的外圈开始跑（遇到缝隙就钻进去），按照跑的顺序，依次输出序列

递归代码

void  PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/{  if (root!=NULL)  {    Visit(root ->data);  /*访问根结点*/    PreOrder(root ->LChild);  /*先序遍历左子树*/    PreOrder(root ->RChild);  /*先序遍历右子树*/  }}

复制代码

2.中序遍历

算法讲解

遍历顺序：左子树->根结点->右子树
动态图解：中序遍历就像投影仪一样，将二叉树从最左侧到最右侧依次投影到同一水平线上面，得到的从左到右的相关序列就是二叉树的中序遍历

递归代码

void  InOrder(BiTree root)  /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/{  if (root!=NULL)  {    InOrder(root ->LChild);   /*中序遍历左子树*/    Visit(root ->data);        /*访问根结点*/    InOrder(root ->RChild);   /*中序遍历右子树*/  }}

复制代码

3.后序遍历

看后序遍历的动态图图之前，还记不记得先序遍历的动态图？不会忘了吧。

后序遍历就是在先序遍历的基础之上，进行像剪葡萄一样的操作，如下图：

算法讲解

遍历顺序：左子树->右子树->根结点
动态图解：后序遍历也是按照先序遍历的顺序输出，不过后序遍历就像剪葡萄，只能一个个剪，不能让超过 1 个的葡萄一起掉下来，那就错了。例如上图中的 B，剪去 B 后面的 D、E、H、I、J 都会掉下来（达咩），而 H 剪去只会掉下 H，规律就是这个规律

递归代码

void  PostOrder(BiTree root)  /*后序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/{  if (root!=NULL)  {    PostOrder(root ->LChild);   /*后序遍历左子树*/    PostOrder(root ->RChild);   /*后序遍历右子树*/      Visit(root ->data);        /*访问根结点*/     }

复制代码

4.层次遍历

算法讲解 就是一层一层的从左至右输出，算法不要求掌握

拓展

树的先根遍历==二叉树的先序遍历
树的中根遍历==二叉树的后序遍历
树的后根遍历==二叉树的中序遍历

五、遍历算法的简单应用

1.建立二叉链表存储的二叉树

void CreateBiTree(BiTree *bt)   //按“扩展先序遍历序列”建立二叉树的二叉链表的算法{    char ch;    ch = getchar();    if(ch==‘.’) *bt=NULL;  // 输入时以点号“. ”表示空结点。    else   {        *bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点            (*bt)->data=ch;          CreateBiTree(&((*bt)->LChild)); //生成左子树          CreateBiTree(&((*bt)->RChild)); //生成右子树  }}

复制代码

2.输出叶子结点

void  PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树根结点的指针*/{  if (root!=NULL)  {    if (root ->LChild==NULL && root ->RChild==NULL)      printf("%c  ",root ->data);  /*输出叶子结点*/    PreOrder(root ->LChild);  /*先序遍历左子树*/    PreOrder(root ->RChild);  /*先序遍历右子树*/  }}

复制代码

3.统计二叉树叶子结点数目

/* LeafCount保存叶子结点的数目的全局变量,调用之前初始化值为0 */ 方法一：void leaf_a(BiTree root){  if(root!=NULL)  {    leaf_a(root->LChild);              leaf_a(root->RChild);    if (root ->LChild==NULL && root ->RChild==NULL)      LeafCount++;  }}

复制代码

4.求二叉树高度

int PostTreeDepth(BiTree bt)   /* 后序遍历求二叉树的高度递归算法 */{  int hl,hr,max;  if(bt!=NULL)  {    hl=PostTreeDepth(bt->LChild);  /* 求左子树的深度 */    hr=PostTreeDepth(bt->RChild);  /* 求右子树的深度 */    max=hl>hr?hl:hr;              /* 得到左、右子树深度较大者*/    return(max+1);               /* 返回树的深度 */  }  else return(0);             /* 如果是空树，则返回0 */}

复制代码

5.按树状打印二叉树

void PrintTree(BiTree bt,int nLayer)  /* 按竖向树状打印的二叉树 */{  if(bt == NULL) return;  PrintTree(bt->RChild,nLayer+1);  for(int i=0;i<nLayer;i++)    printf("  ");  printf("%c\n",bt->data);  PrintTree(bt->LChild,nLayer+1);}

复制代码

六、线索二叉树

1.基本概念

前驱和后继：在二叉树先序、中序、后序、层次遍历之后得到的序列，前一个是前驱，后一个是后继。就像排队一样，排在我前面的叫做我的前驱，排在我后面的叫做后继。思考一下：什么时候是没有前驱和后继的？
线索：指向前驱或后继结点的一个指针
线索化：对二叉树进行某种遍历，使之变成线索二叉树的一个过程
线索二叉树：加上线索的一个二叉链表

2.基本结构

孩子指针域：LChild 指向左孩子，RChild 指向右孩子
标志域 Ltag：Ltag==1,表示 LChild 指向左孩子，Ltag==0 则表示 LChild 指向前驱
标志域 Rtag：Rtag==1,表示 RChild 指向左孩子，Rtag==0 则表示 RChild 指向前驱
选择题表示结点 p 为叶子结点的是：p->Ltag==1&&p->Rtag==1

3.结构体

typedef  struct node{    int  data;     int ltag, rtag;     struct node *lchild, *rchild;}JD;

复制代码

4.建立中序线索化二叉树

动态图：

这个动态演示图有点长，其实只要看懂前面两个建立的过程之后，后面的也自然而然理解了。不要求熟练掌握，但要对这个过程要熟悉一下。

算法讲解：

LTag=0, LChild 指向根结点
RTag=1, RChild 指向遍历序列中最后一个结点（这个性质常常用来考填空题，要牢记啊！）
遍历序列中第一个结点的 LChild 域和最后一个结点的 RChild 域都指向根结点

代码：

void  Inthread(BiTree root)/* 对root所指的二叉树进行中序线索化，其中pre始终指向刚访问过的结点，其初值为NULL*/{  if (root!=NULL)  {     Inthread(root->LChild);  /* 线索化左子树 */    if (root->LChild==NULL)    {      root->Ltag=1;       root->LChild=pre;  /*置前驱线索 */    }    if (pre!=NULL&& pre->RChild==NULL)  /* 置后继线索 */    {      pre->RChild=root;      pre->Rtag=1;    }          pre=root;         Inthread(root->RChild);  /*线索化右子树*/  }}

复制代码

七、树和二叉树转换

1.树 -> 二叉树

讲解

连接所有兄弟结点
对树中的每一个结点，只保留与第一个结点的连线，其它删除
整棵树顺时针旋转 90 度

2.二叉树 -> 树

讲解

将左孩子的右孩子、右孩子的右孩子......全部连接起来
所有双亲结点删除与右孩子的连线
调整一定的角度

3.森林 -> 二叉树

讲解

先将森林中每棵树转换成二叉树
将二叉树根节点视为兄弟连接起来
调整一定的角度

读到这里就全部结束了，其实说是全面总结，但一点都不全面（后面有时间再补充吧）。本意只是想通过这些动态演示图帮助大家更好的理解算法、那样学起来可能会轻松一点。

发布于: 2022 年 03 月 17 日阅读数: 57

原文链接:【http://xie.infoq.cn/article/0fd1b52ebda426775ed111fca】。文章转载请联系作者。

知心宝贝

关注

还未添加个人签名 2022.03.07 加入

生于尘埃溺于人海死于理想高台

评论 (1 条评论)

发布

知心宝贝

3月更文，我来啦

2022 年 03 月 17 日 19:34

 0 回复

没有更多了

创作场景

【图解数据结构】树和二叉树全面总结

一、前言

二、概念及定义

1.树

2.二叉树

3.满二叉树

4.完全二叉树

三、二叉树的性质

1.层结点

2.总结点

3.深度

4.结点数

5.孩子结点

四、二叉树的遍历

1.先序遍历

2.中序遍历

3.后序遍历

4.层次遍历

五、遍历算法的简单应用

1.建立二叉链表存储的二叉树

2.输出叶子结点

3.统计二叉树叶子结点数目

4.求二叉树高度

5.按树状打印二叉树

六、线索二叉树

1.基本概念

2.基本结构

3.结构体

4.建立中序线索化二叉树

七、树和二叉树转换

1.树 -> 二叉树

2.二叉树 -> 树

3.森林 -> 二叉树

知心宝贝

评论 (1 条评论)