写点什么

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

作者:知心宝贝
  • 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
用户头像

知心宝贝

关注

还未添加个人签名 2022.03.07 加入

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

评论 (1 条评论)

发布
用户头像
3月更文,我来啦
2022 年 03 月 17 日 19:34
回复
没有更多了
【图解数据结构】树和二叉树全面总结_二叉树_知心宝贝_InfoQ写作平台