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

会挽雕弓如满月，西北望，射天狼。这篇文章主要讲述图解数据结构树和二叉树全面总结相关的知识，希望能为你提供帮助。
一、前言

学习目标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，右孩子2i+1
上面的性质我就不推导了，其实就是实在不想写了。
四、二叉树的遍历 1.先序遍历

文章图片

算法讲解

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

递归代码

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

2.中序遍历

文章图片

算法讲解

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

递归代码

voidInOrder(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，规律就是这个规律

递归代码

voidPostOrder(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=https://www.songbingjia.com/android/ch; CreateBiTree(& ((*bt)-> LChild)); //生成左子树 CreateBiTree(& ((*bt)-> RChild)); //生成右子树

2.输出叶子结点

voidPreOrder(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.结构体

typedefstruct node intdata; int ltag, rtag; struct node *lchild, *rchild; JD;

4.建立中序线索化二叉树
动态图：

文章图片

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

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

代码：

voidInthread(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.树 -> 二叉树