一、前言
- 学习目标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.先序遍历
算法讲解
- 遍历顺序：根结点->左子树->右子树
- 动态图解：和上面的动态图一样，先序遍历就像一个小人从根结点开始，围绕二叉树的外圈开始跑（遇到缝隙就钻进去），按照跑的顺序，依次输出序列
递归代码
voidPreOrder(BiTreeroot) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/{ if (root!=NULL) { Visit(root->data); /*访问根结点*/PreOrder(root->LChild); /*先序遍历左子树*/PreOrder(root->RChild); /*先序遍历右子树*/ } }
2.中序遍历
算法讲解
- 遍历顺序：左子树->根结点->右子树
- 动态图解：中序遍历就像投影仪一样，将二叉树从最左侧到最右侧依次投影到同一水平线上面，得到的从左到右的相关序列就是二叉树的中序遍历
递归代码
voidInOrder(BiTreeroot) /*中序遍历二叉树, 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(BiTreeroot) /*后序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/{ if (root!=NULL) { PostOrder(root->LChild); /*后序遍历左子树*/PostOrder(root->RChild); /*后序遍历右子树*/Visit(root->data); /*访问根结点*/ }
4.层次遍历
算法讲解 就是一层一层的从左至右输出，算法不要求掌握
拓展
- 树的先根遍历==二叉树的先序遍历
- 树的中根遍历==二叉树的后序遍历
- 树的后根遍历==二叉树的中序遍历
五、遍历算法的简单应用
1.建立二叉链表存储的二叉树
voidCreateBiTree(BiTree*bt) //按“扩展先序遍历序列”建立二叉树的二叉链表的算法{ charch; ch=getchar(); if(ch==‘.’) *bt=NULL; // 输入时以点号“. ”表示空结点。else { *bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点 (*bt)->data=ch; CreateBiTree(&((*bt)->LChild)); //生成左子树CreateBiTree(&((*bt)->RChild)); //生成右子树 } }
2.输出叶子结点
voidPreOrder(BiTreeroot) /*先序遍历二叉树, root为指向二叉树根结点的指针*/{ if (root!=NULL) { if (root->LChild==NULL&&root->RChild==NULL) printf("%c ",root->data); /*输出叶子结点*/PreOrder(root->LChild); /*先序遍历左子树*/PreOrder(root->RChild); /*先序遍历右子树*/ } }
3.统计二叉树叶子结点数目
/* LeafCount保存叶子结点的数目的全局变量,调用之前初始化值为0 */方法一：voidleaf_a(BiTreeroot) { if(root!=NULL) { leaf_a(root->LChild); leaf_a(root->RChild); if (root->LChild==NULL&&root->RChild==NULL) LeafCount++; } }
4.求二叉树高度
intPostTreeDepth(BiTreebt) /* 后序遍历求二叉树的高度递归算法 */{ inthl,hr,max; if(bt!=NULL) { hl=PostTreeDepth(bt->LChild); /* 求左子树的深度 */hr=PostTreeDepth(bt->RChild); /* 求右子树的深度 */max=hl>hr?hl:hr; /* 得到左、右子树深度较大者*/return(max+1); /* 返回树的深度 */ } elsereturn(0); /* 如果是空树，则返回0 */}
5.按树状打印二叉树
voidPrintTree(BiTreebt,intnLayer) /* 按竖向树状打印的二叉树 */{ if(bt==NULL) return; PrintTree(bt->RChild,nLayer+1); for(inti=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.结构体
typedefstructnode{ intdata; intltag, rtag; structnode*lchild, *rchild; }JD;
4.建立中序线索化二叉树
算法讲解：
- LTag=0, LChild指向根结点
- RTag=1, RChild指向遍历序列中最后一个结点（这个性质常常用来考填空题，要牢记啊！）
- 遍历序列中第一个结点的LChild域和最后一个结点的RChild域都指向根结点
代码：
voidInthread(BiTreeroot) /* 对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.森林 -> 二叉树
讲解
- 先将森林中每棵树转换成二叉树
- 将二叉树根节点视为兄弟连接起来
- 调整一定的角度
读到这里就全部结束了，其实说是全面总结，但一点都不全面（后面有时间再补充吧）。
