目录
.树形结构.概念(了解).概念(重要).树的表示形式.树的应用.二叉树(BinaryT重点).概念.二叉树的5种基本形态.两种特殊的二叉树..斜树..满二叉树..完全二叉树.二叉树的性质..第i层结点个数..树的所有最大点个数..叶子结点和非叶子结点数量关系..根据结点求树深度..5父子结点编号关系..6小练兵.5二叉树的存储.5.顺序存储.5..完全二叉树的形式存储.5..一般树的形式存储.5.链式存储.二叉树由浅入深解析.遍历二叉树..二叉树遍历原理..二叉树遍历方法...前序遍历...中序遍历...后序遍历...层序遍历..二叉树遍历算法...前序遍历算法根左右...中序遍历算法左根右...后序遍历算法左右根...层序遍历算法上至下,左至右.二叉树建立问题..前序中序构建二叉树..中序后序构建二叉树..根据二叉树创建字符串..前序遍历字符串构建二叉树..5合并二叉树..6递增二叉树.经典题目解析..结点个数..叶子结点个数..第k层结点个数..查找val所在结点..5相同的树..6另一棵树子树..7二叉树最大深度..8平衡二叉树..9对称二叉树..0二叉树的完全性检验..二叉树最近公公祖先..二叉树最大宽度..特殊的二叉树问题..搜索二叉树..赫夫曼树及其应用...赫夫曼树...赫夫曼树定义与原理..赫夫曼编码..线索二叉树.总结回顾5.结束语
.树形结构
.概念(了解)
树不再是顺序表,链表,栈,队列那样一对一的线性结构.而树则是一种一对多的数据结构,由n(n=0)个互不相交有限节点组层有层次关系的集合.特点如下:
有一个特殊的节点,称为根节点,根节点没有前驱节点除根节点外,其余节点被分成M(M0)个互不相交的集合T,T,…,Tm，其中每一个集合=m)又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继树是递归定义的[树的定义中用到了树的概念]
错误的二叉树D和E不应该相交,I节点有两个父节点
正确的树:
.概念(重要)
用的是上图中正确的二叉树来解释概念
节点的度:一个节点含有的子树的个数称为该节点的度[A的度就是]
非终端节点或分支节点:度不为0的节点[A,B,C,D,E]
树的度:一棵树中，最大的节点的度称为树的度;如上图:树的度为
叶子节点或终端节点:度为0的节点称为叶节点;如上图:G、H、I、J节点为叶节点
双亲节点或父节点:若一个节点含有子节点，则这个节点称为其子节点的父节点;如上图:A是B的父节点
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;如上图:B是A的孩子节点
兄弟节点:具有相同父节点的节点互称为兄弟节点[B和C,E和F,G,H和I]
堂兄弟节点:双亲在同一层的节点互称为堂兄弟节点[D和E,D和F]
节点的祖先:从根到该节点的所有分支经历所有节点[A]
根结点:一棵树中，没有双亲结点的结点;如上图:A
森林:由m(m=0)棵互不相交的树的集合称为森林
节点的层次:从根开始定义起，根为第层，根的子节点为第层，以此类推
树的高度或深度:树中节点的最大层次;如上图:树的高度为
.树的表示形式
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如:双亲表示法、孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法
classNod{intvalu;//树中存储的数据Nodchild;//第一个孩子引用Nodbrothr;//下一个兄弟引用}
.树的应用
文件系统管理(目录和文件)
.二叉树(BinaryT重点)
.概念
我们从经典的猜数字游戏开始,由浅入深介绍二叉树.在00以内猜数字,最多几次可以猜对呢?答案是:7下面是根据每次猜的大小来构建二叉树我们发现利用这个大小关系来查找指定范围内某个数字,效率不是高的一丁半点.因此对于这种具有对立关系的情况:0和,真与假,上与下,正与反,对与错都适合用树来建模.这种特殊的树状结构称为二叉树
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。特点:
每个节点最多有颗子树,即不存在度大于的节点二叉树有左右子树之分,次序不能颠倒,因此二叉树也是一颗有序树.二叉树的5种基本形态
空二叉树只有一个根节点根节点只有左子树根节点只有右子树根节点即有左子树又有右子树
.两种特殊的二叉树
..斜树
顾名思义,斜树一定要是斜的,往哪儿斜也是有讲究的.所有的节点都只有左子树叫做左斜树;所有的节点都只有右子树叫做右斜树左斜树:右斜树:
斜树有明显特点:每一层都只有一个节点,结点个数和树的深度相同.
有些同学就奇怪了:这也能叫树吗,这不是我们熟悉的线性表吗?解释:对的,线性表结构可以理解为树的一种极其特殊的表现形式
..满二叉树
在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子节点都在同一层上,这样的二叉树称为满二叉树它的样子看得很美,很匀称
满二叉树特点:
叶子结点只能出现在最下一层,出现在其它层就不可能达到平衡非叶子结点的度一定是,否贼就是"缺胳膊少腿"在同样深度的二叉树中,满二叉树结点个数最多,叶子结点最多..完全二叉树
把一颗具有n个节点的二叉树按层序编号,编号i(=i=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中所在位置完全相同这是一种有些难以理解的特殊二叉树首先从字面上理解区分,"满"和"完全"的差异:满二叉树一定是一颗完全二叉树,但是完全二叉树不一定是一颗满二叉树什么是按层序编号?上图中就是按照从上到下,从左到右一次按照,,,…,n的序号
完全二叉树特点:
叶子结点只能出现在最下两层最下层的叶子结点一定集中在左部连续位置倒数第二层,如果有叶子结点,一定都在右部连续位置如果结点的度为,则该节点只有左孩子,即不存在只有右子树的情况同样结点数的二叉树,完全二叉树的深度最小从上面的列子中,也给了我们一个判断某二叉树是否为完全二叉树的办法:看着二叉树的示意图,心中默默给每个节点按照满二叉树的结构逐层顺序编号,如果编号出现了空档,就说明不是完全二叉树否则就是完全二叉树
.二叉树的性质
..第i层结点个数
若规定根节点的层数为，则一棵非空二叉树的第i层上最多有^(i-)(i0)个结点
..树的所有最大点个数
若规定根节点的层数为，则深度为K的二叉树最大节点数是^k-(k0)个结点
..叶子结点和非叶子结点数量关系
对任何一棵二叉树,如果其叶结点个数为n0,度为的非叶结点个数为n,则有n0=n+[最下一层的叶子结点个数=上面的所有非叶子结点个数+]
..根据结点求树深度
具有n个节点的二叉树的深度K为log^(n+)向上取整
..5父子结点编号关系
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有:
若i0，双亲序号:(i-)/;若i=0，i为根节点编号，无双亲节点若i+n，左孩子序号:i+，否则无左孩子若i+n，右孩子序号:i+，否则无右孩子这个规律很重要,涉及到堆排,二叉搜索树需要用到这个规律
..6小练兵
设一棵完全二叉树中总共有个节点,则该二叉树中个叶子节点,个非叶子节点,个节点只有左孩子,0个只有右孩子.
个叶子结点计算步骤
叶子结点总个数=第0层叶子结点个数+第9层叶子结点个数有同学会想:为何第9层会有叶子结点呢?解释:因为我们发现此树共有个结点,而满二叉树的话会有^0-个结点,所以说明第0层没满,第9层一定有叶子结点
有了这个理解后再做进一步的计算
第0层全是叶子结点个数:树的总结点个数-9层及以上所有结点个数因为是一颗完全二叉树,所以可以保证第9层一定是满二叉树算式:-(^9-)–-5=89
现在我们还差第9层的叶子结点个数
第9层叶子结点个数:第9层结点个数-第0层父节点个数算式:^(9-)-第0层父节点个数
最后的问题就是求第0层父节点个数
第0层父节点个数求法如果结点个数n是偶数,则其父结点个数为n/如果结点个数n是奇数,则其父结点个数n/+在第一步中我们求得了第0层父节点个数,求第0层父节点个数就是:89/+–5现在可以计算第步得出第9层叶子结点个数:^(9-)-5–56-5=现在可以计算第步中的所有整棵树的叶子结点;第0层结点数+第9叶子结点数:89+=有了叶子结点个数,很容易知道非叶子节点总结点个数-叶子结点个数:-由于完全二叉树第0层结点个数为89,为奇数,所以一定有个节点只有左孩子,有0个节点只有右子树
将一颗有00个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根节点编号为，则编号为98的节点的父节点编号为:(98-)/=8
设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是:中序遍历
将一棵二叉树的根结点放入队列，然后递归的执行如下操作，将出队结点所有子结点加入队。以上操作可以实现层序遍历.
n个节点的完全二叉树，最多可以有多少层:log(n+)上取整
.5二叉树的存储
.5.顺序存储
二叉树的顺序存储就使用一维数组存储二叉树中的节点并且存储的位置应该要能体现节点之间的逻辑关系,比如孩子双亲,左右兄弟节点
.5..完全二叉树的形式存储
将这颗二叉树存储数组中,相应的下标对应其相等的位置这下看出完全二叉树的优越性了吧,由于它定义的严格,所以顺序结构也能表现出二叉树的结构来
.5..一般树的形式存储
对于一般二叉树而言,层序编号不能反映逻辑关系,但是可以按照完全二叉树编号,只不过把不存在的结点设施为‘^’而已.浅色节点代表不存在考虑一下极端情况:又斜树
一颗深度为k的右斜树,只有k个节点,却需要分配^k-个存储单元,这显然是对存储空间的浪费.所以顺序存储只适用于完全二叉树
.5.链式存储
既然顺序存储适应性不强,我们就要考虑链式存储结构.二叉树每个节点最多有两个孩子,所以设计一个数据域和两个指针域比较理想.这就是二叉链表孩子表示法
classNod{intval;//数据域Nodlft;//左孩子的引用，常常代表左孩子为根的整棵左子树Nodright;//右孩子的引用，常常代表右孩子为根的整棵右子树}
孩子双亲表示法主要用在在平衡树，本文采用孩子表示法来构建二叉树,大多数的在线OJ题目也都采用的这种方法来构建二叉树.
.二叉树由浅入深解析
.遍历二叉树
..二叉树遍历原理
导言:假设有0张00元的和张元的奖券,同时撒向了空中,大家比赛看谁最中间的最多.
相信同学都会说:先捡00元的.道理非常简单,因为捡张00元的等于捡00张元的,效率好的不是一点点?.
所以得出这样的结论:同样是捡奖券,在有限时间内,要达到最高效率,次序非常重要.对于二叉树的遍历来讲,次序同样显得也很重要.
二叉树的遍历(travrsingbinaryt):是指从根结点出发,按照某种次序依次访问二叉树中的所有节点,使得每一个节点被访问一次且仅仅被访问一次
这里有两个关键词:依次和访问.不同于线性结构,最多也就是从头至尾,循环,双向等简单的遍历方式.树的节点之间不存在唯一的前驱和后继关系,在访问一个节点后,下一个被访问的节点面临着不同的选择.就像你人生的道路上,高考填报志愿要面临哪个城市,哪所大学,具体专业等.选择方式不同,遍历的次序就完全不同
..二叉树遍历方法
...前序遍历
若二叉树为空,则返回空操作否则先访问根节点,然后前序遍历左子树再前序遍历右子树最终访问的结果就是:ABDGHCEIF如下图就是根左右的顺序访问二叉树示意图
...中序遍历
树空,则返回空操作否则就从根结点开始(注意并不是先访问根节点)中序遍历根节点的左子树然后访问根节点最后中序遍历右子树最终访问结果就是:GDHBAEICF如下图就是左根右的顺序访问二叉树示意图
...后序遍历
树空,则返回空操作否先从左到右线叶子结点后节点的方式遍历访问左右子树,最后访问根节点最终访问结果是:GHDBIEFCA如下图就是左右根的顺序访问二叉树示意图
...层序遍历
若树为空,返回空操作否则从树的第一层,也就是根节点开始访问从上而下逐层遍历在同一层中,按左到右的顺序对节点逐个访问最终访问结果就是:ABCDEFGHI
..二叉树遍历算法
假设我们有以下一颗二叉树T,用链表结构存储
...前序遍历算法根左右
OJ题目链接递归前序遍历
privatstaticvoidpOrdrTravrsal(BinaryTNodroot){if(root==null){turn;}ls{Systm.out.print(root.val+"");pOrdr(root.lft);pOrdr(root.right);}}privatstaticListStringpOrdrTravrsal(BinaryTNodroot){ListStringsult=nwArrayList();if(root==null){turnsult;}ls{sult.add(root.val);sult.addAll(pOrdrTravrsal(root.lft));sult.addAll(pOrdrTravrsal(root.right));turnsult;}}ABDHKECFIGJ
演示递归前序遍历步骤
调用pOrdrTravrsal(BinaryTNodroot),root根节点不为空,所以执行Systm.out.print(root.val+"");打印字母A调用pOrdrTravrsal(root.lft),访问了A节点的左孩子,不为null,执行Systm.out.print(root.val+"");打印字母B再次递归调用pOrdrTravrsal(root.lft),访问了B节点的左孩子,不为null,执行Systm.out.print(root.val+"");打印字母D再次递归调用pOrdrTravrsal(root.lft),访问了D节点的左孩子,不为null,执行Systm.out.print(root.val+"");打印字母H再次递归调用pOrdrTravrsal(root.lft),访问H节点的左孩子,此时因为H节点无左孩子,所以root==null返回此函,此时递归调用pOrdrTravrsal(root.right);访问了H节点的右孩子,执行Systm.out.print(root.val+"");打印字母K再次递归调用pOrdrTravrsal(root.lft),访问K节点的左孩子,返回调用pOrdrTravrsal(root.right),访问了K节点的右孩子,也是null,返回.于是函数执行完毕.返回到上一级递归的函数(即打印H节点时的函数),也执行完毕.[根左右都已经遍历完,所以执行完毕]返回打印D节点时的函数,调用pOrdrTravrsal(root.right)访问D节点的右孩子,不存在返回到B节点,调用pOrdrTravrsal(root.right),访问B节点的右孩子,打印字母E由于节点E没有左右孩子,返回打印节点B时的递归函数,递归执行完毕.返回到最初的pOrdrTravrsal(root),调用pOrdrTravrsal(root.right),访问A节点的右孩子,打印字母C之后类似前面的递归调用,一次继续打印F,I,G,j
知道了递归的代码如何运行,那我们再看看非递归实现前序遍历
/*非递归.先创建一个栈.根节点放进栈里.循环取栈顶元素.出栈并访问这个元素值域5.把当前元素的右子树入栈,再左子树入栈*/privatstaticvoidpOrdrTravrsalNo(BinaryTNodroot){if(root==null){turn;}ls{StackBinaryTNodstack=nwStack();stack.push(root);whil(!stack.mpty()){BinaryTNodtop=stack.pop();Systm.out.print(top.val+"");if(top.right!=null){stack.push(top.right);}if(top.lft!=null){stack.push(top.lft);}}}}ABDHKECFIGJ
演示迭代前序遍历步骤
非递归思路很巧妙的利用了栈的先进后出特性进行前序遍历
...中序遍历算法左根右
OJ题目链接递归中序遍历
privatstaticvoidinOrdrTravrsal(BinaryTNodroot){if(root==null){turn;}ls{pOrdr(root.lft);Systm.out.print(root.val+"");pOrdr(root.right);}}HKDBEAIFCGJ
演示递归中序遍历步骤
调用inOrdrTravrsal(BinaryTNodroot),root的根节点A不为null,于是调用inOrdrTravrsal(root.lft),访问节点B;B不为空,继续调用inOrdrTravrsal(root.lft),访问节点D;D不为空,继续调用inOrdrTravrsal(root.lft),访问节点H;H不为空,继续调用inOrdrTravrsal(root.lft),访问节点H的左孩子;为空,返回.打印当前节点H然后调用inOrdrTravrsal(root.right),访问H节点的右节点K.因为K无左孩子,所以打印K因为K没有右节点,所以返回.打印H节点的函数执行完毕,返回.打印字母D节点D没有右孩子,所以返回.打印B调用inOrdrTravrsal(root.right),访问B节点的右节点E,因为E没有左孩子,所以打印E节点E无右孩子,返沪.打印B的函数执行完毕,返回到了我们最初执行inOrdrTravrsal(root)的地方,打印字母A调用inOrdrTravrsal(root.right),访问A节点的右孩子C,再递归访问C的左孩子F,F的左孩子I,因为I无右孩子,所以打印I.之后分别打印F,C,G,J
迭代中序遍历
/*.先创建一个栈.根节点入栈.循环取栈顶元素.左子树集体入栈后再入右子树5.最外层whil循环判断需要留意.因为cur=cur.right会导致cur==nulll,因此在加入一个!stack.mpty()的判断*/privatstaticvoidinOrdrTravrsalNo(BinaryTNodroot){if(root==null){turn;}ls{StackBinaryTNodstack=nwStack();BinaryTNodcur=root;whil(cur!=null
!stack.mpty()){whil(cur!=null){stack.push(cur);cur=cur.lft;}cur=stack.pop();Systm.out.print(cur.val+"");cur=cur.right;}}}HKDBEAIFCGJ
演示迭代中序遍历步骤
...后序遍历算法左右根
OJ题目链接递归后序遍历
/*OJ:通过*/classSolution{ListIntgrlist=nwArrayList();publicListIntgrpostordrTravrsal(TNodroot){if(root==null){turnlist;}ls{postordrTravrsal(root.lft);postordrTravrsal(root.right);list.add(root.val);turnlist;}}}
privatstaticvoidpostOrdrTravrsal(BinaryTNodroot){if(root==null){turn;}ls{postOrdrTravrsal(root.lft);postOrdrTravrsal(root.right);Systm.out.print(root.val+"");}}
演示递归后序遍历步骤
后序遍历先递归左子树,由根节点A-B-D-H,节点H无左孩子,再查看H的右孩子K,因为节点K无左右孩子,所以打印K.K打印执行完之后返回到执行打印H的程序Systm.out.print(root.val+"");,打印H节点后续的分析步骤和都是看返回的节点有无左右子树是否遍历完了:遍历完了就输出根节点,否则就继续遍历
迭代后序遍历
/*和中序遍历类似.外层循环依旧需要加上!stack.mpty()来带动循环.被打印完的节点置为null,并且判断该节点是否被打印过.判断超时*/privatstaticvoidpostOrdrTravrsalNo(BinaryTNodroot){if(root==null){turn;}ls{StackBinaryTNodstack=nwStack();BinaryTNodcur=root;BinaryTNodpv=null;whil(cur!=null
!stack.mpty()){whil(cur!=null){stack.push(cur);cur=cur.lft;}cur=stack.pk();if(cur.right==null
cur.right==pv){stack.pop();Systm.out.print(cur.val+"");pv=cur;cur=null;}ls{cur=cur.right;}}}}KHDEBIFJGCA
演示迭代后序遍历步骤
...层序遍历算法上至下,左至右
OJ题目链接
classSolution{publicListListIntgrlvlOrdr(TNodroot){ //.返回空盒子ListListIntgrlist=nwArrayList();if(root==null){turnlist;}ls{ //.队列村粗QuuTNodquu=nwLinkdList();quu.offr(root);whil(!quu.isEmpty()){intsiz=quu.siz();ListIntgrtmp=nwArrayList();whil(siz--0){TNodtop=quu.poll();tmp.add(top.val);if(top.lft!=null){quu.offr(top.lft);}if(top.right!=null){quu.offr(top.right);}}list.add(tmp);}turnlist;}}}[[A],[B,C],[D,E,F,G],[H,I,J],[K]]
演示OJ练习题中的代码执行步骤
正常的层序输出
/*.先创建一个队列.把根节点放在队列.循环取队列元素全部.内部list添加当前元素.再把当前元素的左子树入队列，再入右子树5.大的t添加每次新添元素后的list*/privatstaticvoidlvlOrdr(BinaryTNodroot){if(root==null){turn;}ls{QuuBinaryTNodquu=nwLinkdList();quu.offr(root);whil(!quu.isEmpty()){BinaryTNodtop=quu.poll();Systm.out.print(top.val+"");if(top.lft!=null){quu.offr(top.lft);}if(top.right!=null){quu.offr(top.right);}}}}ABCDEFGHIJK
.二叉树建立问题
..前序中序构建二叉树
OJ题目链接
classSolution{privatintfindInordrIndx(int[]inordr,intinbgin,intinnd,intky){for(inti=inbgin;i=innd;++i){if(inordr==ky){turni;}}turn-;}privatTNodbuildTChild(int[]pordr,int[]inordr,intinbgin,intinnd){if(inbgininnd){turnnull;}ls{TNodroot=nwTNod(pordr[pIndx++]);introotIndx=findInordrIndx(inordr,inbgin,innd,root.val);root.lft=buildTChild(pordr,inordr,inbgin,rootIndx-);root.right=buildTChild(pordr,inordr,rootIndx+,innd);turnroot;}}privatintpIndx=0;publicTNodbuildT(int[]pordr,int[]inordr){if(pordr==null
inordr==null){turnnull;}ls{turnbuildTChild(pordr,inordr,0,inordr.lngth-);}}}
其时建立二叉树也是利用了递归的原理.只不过在当初打印节点的代码换成了生成节点,给节点赋值的操作而已.前序遍历的第一个节点一定是根节点,所以我们在中序遍历中划分根节点的左右子树,然后递归找根节点再划分左右子树,递归的终止条件是区间的左一定要大于区间的右代码思路:
判断前序或中序是否有一个为null利用buildTChild函数返回根节点先构造根节点,再递归构建左子树和右子树所有递归完之后返回最后的root就是树的根节点演示图
第一查找的是pordr[pIndx]的根节点由于第二次划分的时候,新的innd是rootIndx-所以导致的if(inbgininnd)turn;程序返回执行root.right=buildTChild(pordr,inordr,rootIndx+,innd);第三次划分综合
..中序后序构建二叉树
OJ题目链接
classSolution{privatintpostIndx=0;privatintfindInordrIndx(int[]inordr,intinbgin,intinnd,intky){for(inti=inbgin;i=innd;++i){if(inordr==ky){turni;}}turn-;}privatTNodbuildTChild(int[]inordr,int[]postordr,intinbgin,intinnd){if(inbgininnd){turnnull;}ls{TNodroot=nwTNod(postordr[postIndx--]);introotIndx=findInordrIndx(inordr,inbgin,innd,root.val);root.right=buildTChild(inordr,postordr,rootIndx+,innd);root.lft=buildTChild(inordr,postordr,inbgin,rootIndx-);turnroot;}}publicTNodbuildT(int[]inordr,int[]postordr){if(inordr==null
postordr==null){turnnull;}ls{postIndx=postordr.lngth-;turnbuildTChild(inordr,postordr,0,postIndx);}}}
后序遍历和前序变一样想法一样,但是应该注意顺序
演示图因为从后往前看的话,根节点过来就是右节点,所以先构建右子树在构建左子树.遍历递归思路和上述一样,这里就不多述总结出一个二叉树的性质
已知前序遍历和中序遍历,可以确定唯一的一颗二叉树已知中序遍历和后序遍历,可以确定唯一的一颗二叉树
思考:已知前序遍历和后序遍历能否构建唯一的一颗二叉树
不能,原因很简单.比如一棵二叉树前序遍历是ABC后序遍历是CBA我们可以确定根节点是A但不能确定A的左右子树.这棵树就有如下的四种可能
..根据二叉树创建字符串
OJ题目链接
解法
先处理左子树,再处理右子树按照题目要求进行一个一个添加括号
classSolution{privatvoidtstrChild(TNodroot,StringBuffrstringBuffr){if(root==null){turn;}ls{stringBuffr.appnd(root.val);//.处理左子树if(root.lft==null){if(root.right==null){turn;}ls{stringBuffr.appnd("()");}}ls{stringBuffr.appnd("(");tstrChild(root.lft,stringBuffr);stringBuffr.appnd(")");}//.处理右子树if(root.right==null){turn;}ls{stringBuffr.appnd("(");tstrChild(root.right,stringBuffr);stringBuffr.appnd(")");}}}publicStringtstr(TNodroot){if(root==null){turn"";}ls{StringBuffrstringBuffr=nwStringBuffr();tstrChild(root,stringBuffr);turnstringBuffr.toString();}}}
解法代码少,容易理解,但运行效率低
递归前序遍历的形式添加括号添加完毕之后再删除第一个和最后一个括号即可
classSolution{privatStringBuffrstringBuffr=null;privatvoidtstrChild(TNodroot){if(root==null){turn;}ls{stringBuffr.appnd("("+root.val);tstrChild(root.lft);if(root.lft==nullroot.right!=null){stringBuffr.appnd("()");}tstrChild(root.right);stringBuffr.appnd(")");}}publicStringtstr(TNodroot){if(root==null){turn"";}ls{stringBuffr=nwStringBuffr();tstrChild(root);stringBuffr.dltCharAt(0);stringBuffr.dltCharAt(stringBuffr.lngth()-);turnstringBuffr.toString();}}}
..前序遍历字符串构建二叉树
OJ题目链接
importjava.util.Scannr;importjava.util.Stack;classTNod{charval;TNodlft;TNodright;TNod(charval){this.val=val;}}publicclassMain{ //.采用的是迭代的方式进行中序遍历privatstaticvoidinOrdrTravrsal(TNodroot){if(root==null){turn;}ls{StackTNodstack=nwStack();TNodcur=root;whil(cur!=null
!stack.mpty()){ //.左子树集体入栈whil(cur!=null){stack.push(cur);cur=cur.lft;}cur=stack.pop();Systm.out.print(cur.val+"");cur=cur.right;}}}privatstaticintindx=0;//记录打印的字符串下标,因为是递归,所以应该使用全局变量而不是局部变量privatstaticTNodcatT(Stringstr){if(str==null){turnnull;}ls{TNodroot=null;//.越过空节点if(str.charAt(indx)==#){++indx;}ls{//.按照前序根左右的形式递归构建二叉树root=nwTNod(str.charAt(indx++));root.lft=catT(str);root.right=catT(str);}turnroot;}}publicstaticvoidmain(String[]args){Scannrscannr=nwScannr(Systm.in);whil(scannr.hasNxt()){Stringstr=scannr.nxt();TNodroot=catT(str);inOrdrTravrsal(root);Systm.out.println();}}}
..5合并二叉树
OJ题目练习
classSolution{publicTNodmrgTs(TNodroot,TNodroot){ //.如果某个节点为null,则返回另一个节点if(root==null){turnroot;}lsif(root==null){turnroot;}ls{ //.如果两个节点都不为null,则开始合并二叉树TNodroot=nwTNod(root.val+root.val);root.lft=mrgTs(root.lft,root.lft);root.right=mrgTs(root.right,root.right);turnroot;}}}
..6递增二叉树
OJ练习题目
classSolution{privatTNodcur=null;privatvoidinOrdrTravrsal(TNodroot){if(root==null){turn;}ls{//.左inOrdrTravrsal(root.lft);//.根cur.right=root;root.lft=//.右inOrdrTravrsal(root.right);}}publicTNodincasingBST(TNodroot){if(root==null){turnnull;}ls{//.傀儡节点用来保存cur节点的位置用于返回TNodnwRoot=nwTNod(-);//.移动节点cur=nwRoot;inOrdrTravrsal(root);turnnwRoot.right;}}}
.经典题目解析
..结点个数
/*求结点个数遍历思路:递归每次遍历就自增[在线OJ可能会翻车:先拿一个小树调用grSiz方法,然后再拿一个大的树来调用gtSiz]子问题思路:turn+func()...自带返回值*/privatstaticintsiz=0;privatstaticvoidgtSiz(BinaryTNodroot){if(root==null){turn;}ls{++siz;gtSiz(root.lft);gtSiz(root.right);}}privatstaticintgtSiz(BinaryTNodroot){if(root==null){turn0;}ls{turn+gtSiz(root.lft)+gtSiz(root.right);}}
..叶子结点个数
/*求叶子结点个数遍历思路:递归遍历子问题思路:turn+func()...*/privatstaticintlaftSiz=0;privatstaticvoidgtLafSiz(BinaryTNodroot){if(root==null){turn;}ls{if(root.lft==nullroot.right==null){++laftSiz;}ls{gtLafSiz(root.lft);gtLafSiz(root.right);}}}privatstaticintgtLafSiz(BinaryTNodroot){if(root==null){turn0;}ls{if(root.lft==nullroot.right==null){turn;}ls{turngtLafSiz(root.lft)+gtLafSiz(root.right);}}}
..第k层结点个数
privatstaticintgtKLvlSiz(BinaryTNodroot,intk){if(root==null
k){turn0;}ls{if(k==){turn;}ls{turngtKLvlSiz(root.lft,k-)+gtKLvlSiz(root.right,k-);}}}
..查找val所在结点
privatstaticBinaryTNodfind(BinaryTNodroot,Stringval){if(root==null){turnnull;}ls{if(root.val.quals(val)){turnroot;}ls{BinaryTNodt=find(root.lft,val);if(t!=nullt.val.quals(val)){turnt;}t=find(root.right,val);if(t!=nullt.val.quals(val)){turnt;}turnnull;}}}
..5相同的树
OJ题目练习
classSolution{publicboolanisSamT(TNodp,TNodq){//.都为null：说明之前的节点和节点值相等,所以相等;或者两个空节点也是相等的if(p==nullq==null){turntru;//.某个节点遍历完了但另一个节点不为null,所以是fals}lsif(p==null
q==null){turnfals;}ls{//节点值不相等就falsif(p.val!=q.val){turnfals;}ls{//.递归进行下一次比较turnisSamT(p.lft,q.lft)isSamT(p.right,q.right);}}}
..6另一棵树子树
OJ题目练习
classSolution{publicboolanisSamT(TNodp,TNodq){//.都为null：说明之前的节点和节点值相等,所以相等;或者两个空节点也是相等的if(p==nullq==null){turntru;//.某个节点遍历完了但另一个节点不为null,所以是fals}lsif(p==null
q==null){turnfals;}ls{//节点值不相等就falsif(p.val!=q.val){turnfals;}ls{//.递归进行下一次比较turnisSamT(p.lft,q.lft)isSamT(p.right,q.right);}}}publicboolanisSubt(TNodroot,TNodsubRoot){//.两个nullnull则是子树;遍历到了叶子结点的子树,说明之前遍历的都是相等的if(root==nullsubRoot==null){turntru;}lsif(root==nullsubRoot!=null
root!=nullsubRoot==null){turnfals;}ls{//.如果两个节点不为空,且相等,则是子树if(isSamT(root,subRoot)){turntru;//.递归判断是否为子树}lsif(isSubt(root.lft,subRoot)){turntru;}lsif(isSubt(root.right,subRoot)){turntru;}ls{turnfals;}}}}
..7二叉树最大深度
OJ练习题目
classSolution{publicintmaxDpth(TNodroot){if(root==null){turn0;}ls{ //.计算左子树的高度intlft=maxDpth(root.lft)+;//.计算右子树的高度intright=maxDpth(root.right)+;if(lftright){turnlft;}ls{turnright;}}}}
..8平衡二叉树
OJ练习题目
classSolution{privatintmaxDpth(TNodroot){if(root==null){turn0;}ls{intlft=+maxDpth(root.lft);intright=+maxDpth(root.right);turnlftright?lft:right;}}publicboolanisBalancd(TNodroot){if(root==null){turntru;}ls{intlft=maxDpth(root.lft);intright=maxDpth(root.right);if(Math.abs(lft-right)){turnfals;}ls{turnisBalancd(root.lft)isBalancd(root.right);}}}}
//.优化后的代码:边求高度边计算左右子树高度差,不用递归两次classSolution{privatintmaxDpth(TNodroot){if(root==null){turn0;}ls{intlft=maxDpth(root.lft);intright=maxDpth(root.right);if(lft=0right=0Math.abs(lft-right)=){turnMath.max(lft,right)+;}ls{turn-;}}}publicboolanisBalancd(TNodroot){turnmaxDpth(root)-;}}
..9对称二叉树
OJ练习题目
classSolution{privatboolanisSamT(TNodlftT,TNodrightT){if(lftT==nullrightT==null){turntru;}lsif(lftT!=nullrightT==null
lftT==nullrightT!=null){turnfals;}ls{if(lftT.val!=rightT.val){turnfals;}ls{/*.之前的判断步骤和比较二叉树是否相同有点类似.之后应该比较左树的左和右树的右;左树的右和右树的左是否相同*/turnisSamT(lftT.lft,rightT.right)isSamT(lftT.right,rightT.lft);}}}publicboolanisSymmtric(TNodroot){if(root==null){turntru;}ls{turnisSamT(root.lft,root.right);}}}
..0二叉树的完全性检验
OJ题目练习
利用队列特性进行全部入队列(包含null节点)再进行出队列判断
/*.当遇到null节点时候说明已经遍历所有完全二叉树就退出.在队列末尾慢慢弹出元素,如果弹出了不为null则说明不是一个完全二叉树*/classSolution{publicboolanisCompltT(TNodroot){if(root==null){turntru;}ls{QuuTNodquu=nwLinkdList();quu.offr(root);//.直到遇到null节点就停止入队列whil(!quu.isEmpty()){TNodtop=quu.poll();if(top!=null){quu.offr(top.lft);//程序走到叶子结点,则会把null节点也带入队列,后续的pkpk探测的时候如果遇到了不为null的节点的话就代表在遇到null节点之后还有其它叶子结点,此时一定不是完全二叉树quu.offr(top.right);}ls{bak;}}//程序执行到这儿,说明队列中已经存储所有的节点//.节点出队列,pk探测元素是否为nullwhil(!quu.isEmpty()){TNodtop=quu.pk();if(top!=null){turnfals;}ls{quu.poll();//出队列}}turntru;}}}
优化:简单高效的通过对比节点数和下标数判断
classSolution{privatintn=0,p=0;privatboolandfs(TNodroot,intk){if(root==null){turntru;//.节点遍历完毕}lsif(k00){turnfals;//.题目提示:树中将会有到00个结点}ls{++n;//.每遍历一次,结点个数就自增一,记录当前节点下标p=Math.max(p,k);//.因为有左右子树,所以每次应该选取最大下标才可turndfs(root.lft,*k)dfs(root.right,*k+);}}publicboolanisCompltT(TNodroot){if(root==null){turntru;}ls{if(!dfs(root,)){turnfals;//.超过00节点就返回fals}ls{turnn==p;//.未超过00节点,判断节点数和最大下标数是否相等}}}}
..二叉树最近公公祖先
OJ题目练习
/*lft==null,right==null:turnnulllft!=null,right!=null:turnrootlft==null,right!=null:turnrightlft!=null,right==null:turnlft*/classSolution{publicTNodlowstCommonAncstor(TNodroot,TNodp,TNodq){if(root==null
root==p
root==q){turnroot;}ls{TNodlft=lowstCommonAncstor(root.lft,p,q);TNodright=lowstCommonAncstor(root.right,p,q);if(lft==nullright==null){turnnull;}lsif(lft!=nullright==null){turnlft;}lsif(lft==nullright!=null){turnright;}ls{turnroot;}}}}
..二叉树最大宽度
OJ题目练习
classSolution{publicintwidthOfBinaryT(TNodroot){if(root==null){turn0;}ls{LinkdListTNodquu=nwLinkdList();quu.offr(root);intmax_width=0;whil(!quu.isEmpty()){intcur_width=quu.gtLast().val-quu.gtFirst().val+;//.利用结点的值域记录当前队列宽度//.头节点的左右子树入队列,为下一次宽度计算做准备intcount=quu.siz();//.队列大小时刻变化着的,我们应该保留入队列之前的队列大小for(inti=0;icount;++i){TNodtop=quu.poll();//.出队列元素且保留,为后续左右子树入队列做铺垫if(top.lft!=null){quu.offr(top.lft);top.lft.val=top.val;//5.依据的是二叉树的性质5--左孩子:*i根:i右孩子:*i+}if(top.right!=null){quu.offr(top.right);top.right.val=(top.val)+;}}if(max_widthcur_width){max_width=cur_width;}}turnmax_width;}}}
其它语言要考虑下方提示:整形溢出问题
..特殊的二叉树问题
..搜索二叉树
staticclassBinaryTNod{//键值对的形式存储intky;intvalu;BinaryTNodlft;BinaryTNodright;publicBinaryTNod(intky,intvalu){this.ky=ky;this.valu=valu;}}//root:表示树的根节点,空树就是用null来表示privatBinaryTNodroot=null;//查找:根据Ky找ValuprivatIntgrsarch(intky){BinaryTNodcur=root;whil(cur!=null){if(kycur.ky){cur=cur.lft;}lsif(kycur.ky){cur=cur.right;}ls{turnky;}}turnnull;}//插入privatvoidinsrt(intky,intvalu){if(root==null){root=nwBinaryTNod(ky,valu);}ls{BinaryTNodcur=root;BinaryTNodpand=null;whil(cur!=null){pand=cur;if(kycur.ky){cur=cur.lft;}lsif(kycur.ky){cur=cur.right;}ls{turn;//二叉搜索树不存在相等,如果相等也没必要赋值}}//程序执行到这儿,说明pant已经是cur的父节点,修改父节点即可if(kypand.ky){pand.lft=nwBinaryTNod(ky,valu);}ls{pand.right=nwBinaryTNod(ky,valu);}}}//删除:按照ky删除privatvoidmov(intky){//.先查找ky对应的位置BinaryTNodcur=root;BinaryTNodpant=null;whil(cur!=null){pant=cur;if(kycur.ky){cur=cur.lft;}lsif(kycur.ky){cur=cur.right;}ls{/*.核心删除考虑当前cur.lft为空是否为根节点root是:链接右子树否:接着判断当前删除的子节点cur是其父节点pant节点的左右子树关系考虑当前cur.right为空紧接cur.lft根节点判断一样的思路考虑当前cur.right和cur.lft都不为空移形换影删除*/if(cur.lft==null){if(cur==root){root=cur.right;}lsif(cur==pant.lft){pant.lft=cur.right;}lsif(cur==pant.right){pant.right=cur.right;}}lsif(cur.right==null){if(cur==root){root=cur.lft;}lsif(cur==pant.lft){pant.lft=cur.lft;}lsif(cur==pant.right){pant.right=cur.lft;}}ls{//具体移形换影步骤//.右子树找最小值,并记录其父节点BinaryTNodtargtPant=cur;BinaryTNodtargt=cur.right;whil(targt.lft!=null){//最小值特点是:左子树为空targtPant=targt;targt=targt.lft;}//.程序执行到这儿:targtPant是targt父节点;targt是右子树中最小值//.就把替罪羊targt节点的值赋值给删除节点cur.ky=targt.ky;cur.valu=targt.valu;//.断开末尾最小值节点的关系,建立新的关系if(targt==targtPant.lft){targtPant.lft=targt.right;//最小值左节点为null}lsif(targt==targtPant.right){targtPant.right=targt.right;}}}}}
..赫夫曼树及其应用
...赫夫曼树
什么是哈夫曼树哈夫曼树的目的是为了字符串的压缩,我们经常用的zip,tar,ara…等等压缩都是基于哈夫曼树的原理
举个中小学通用的评分标准
if(a60){b="不及格";}lsif(a70){b="及格";}lsif(a80){b="中等";}lsif(a90){b="良好";}ls{b="优秀";}
粗看没什么问题,结果是对的.一张好的试卷应该让学生成绩大部分处于中等或良好范围，优秀和不及格应该很少才对.而上面的程序,就需要让所有的成绩判断是否及格,再逐级而上得到结果.数据量大的时候,算法效率很低下
实际生活中学生成绩分布规律如下表
那么70分以上大约占总数80%的成绩都需要经过次以上的判断才可以得到结果,这显然不合理.
仔细观察发现:中等成绩(70~79)比例最高,其次是良好成绩,不及格所占比例最少.对上述的二叉树重新分配如下(有点像搜索二叉树,其实并不是的,仔细往后面的文章看):
...赫夫曼树定义与原理
把两颗二叉树简化成叶子结点带权的二叉树从树中一个节点到另一个节点之间的分支结构狗曾两个鸡诶但之间的路径,路径上的分支树木称作路径长度
二叉树a中根节点到D节点路径长度就是,二叉树b中根节点到D节点长度就是二叉树a总长度:+++++++=0二叉树b总长度:+++++++=6
如果考虑带权的节点:该节点到树根之间的路径长度与节点上权的乘积.树的带权路径长度作为作为树中所有叶子结点的带权路径长度的之和,用WPL来表示.其中最小的WPL的树称为赫夫曼树.
二叉树aWPL:5*+5*+0*+0*+0*==5二叉树bWPL:5*+5*+0*+0*+0*=0
这样的结果意味着如果有_0个学生的百分制数据计算五级分制成绩,二叉树a需要计算次比较,二叉树b需要00次比较.差不多少了/的量,性能上提高不是一点点
该如何构建赫夫曼树呢?
先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列[A5,E0,B5,D0,C0]取头两个最小全值的节点作为一个新节点N的两个字节点,A是N左子树,E是N右子树.注意左右子树大小关系将N替换A与E,插入有序序列中,保持从小到大排列[N5,B5,D0,C0]重复步骤.将N与B作为一个新节点N的两个字节点重复步骤的序列替换序列最小值,再重复步骤生成新的节点…最终效果：WPL=0*+0*+5*+0*+5*=05,比搜索二叉树还少了5,因此这才是最优的赫夫曼树
..赫夫曼编码
赫夫曼树更大作用是为解决当年远距离通信(主要是电报)的数据传输的最优化问题.比如有一段文字内容为“BADCADFEED”要网络传输给别人,显然用二进制的数据(0和)来表示是很自然的想法,这段文字有6个字母ABCDEF.相应的二进制数据表示就是:
这样真正传输的就是编码后的“”,对方接受可以按照位一分来译码.如果文章内容很长,这样的二进制串也很可怕.此时就应该使用赫夫曼树.
假设6个字母的频率：A:7,B:8,C:5,D:5,E:0,F:5合起来正好是00%.左图构造赫夫曼树的过程权值显示;右图是将权值左子树改为0,右子树分制改为后的赫夫曼树此时我们对6个字母重新编码
原编码:[0个字符]新编码:00[5个字符]少了5个字符,也就是大约7%[5/0=0.67]的成本.字符愈多,这种压缩效果更明显
问题来了:收到了赫夫曼编码又该如何解析呢?编码中非0即,长短不等的话其实很容易混淆的,所以要设计长短不等的编码:任一字符的编码都不是另一个字符编码的前缀,这种比那吗称为前缀编码[0,00,0,00,,都是不同长短长度,因此不容易混淆]
这样并不足以,我们去方便的解码,因此在解码的时候接收方和发送方都必须要约定好相同的赫夫曼编码规则
当收到00时,约定好的赫夫曼编码规则可知00得到第一个字母是B,接下来的诶0意味着第二个字母A…一般地，设需要编码的字符集为{d,d,…,dn},各个字符在电文中出现的次数或频率集合为{w,w,…,wn},以d,d,…,dn作为叶子结点，以w,w,…,wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0,右分支代表,则从根结点到叶子结点所经过的路径分支组成的0和的序列便为该结点对应字符的编码，这就是赫夫曼编码。
..线索二叉树
^:表示空指针,图中二叉树有许多空指针,发现这些空间都没有利用.这其实不是一个好现象,应该合理利用起来.
首先那我们来看看有多少个多少个空指针呢?对于一个有n个节点的二叉树有n个指针,而n个节点的二叉树一共有n-条分支线数,也就是说存在n-(n-)=n+个空指针域.对应到题目中就有个空指针的浪费.另一方面,我们中序遍历二叉树得出HDIBJEAFCG,这样的字符序列,我们知道J的前驱是B后继是E,也就是说从中序遍历二叉树我们可以知道任意一个节点的前驱和后继
问题:上边找到的规律是建立在已经遍历过的基础上,在二叉链表上我们只知道每个左右孩子的地址,而不知道后继是谁,后继是谁要想知道必须要再次遍历一次
解决方案
我们在遍历的时候就创建好前驱后继.
我们把这种前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(ThaddBinaryT)
我们把这棵二叉树进行中序遍历,将所有空指针的rchild,改为指向它的后续结点.于是就可以通过指针知道H的后继是D(),I的后继是B(),J的后继是E()(E.nxt=A(),F.nxt=C(5),G.nxt=null(6)).此时共有6个空指针被利用.再看图,把这棵二叉树中的所有空指针域中的lchild,改为指向当前结点的前驱.因此H的前驱是NULL(),I的前驱是D()[J.pv=B(),F.pv=A(),G.pv=C(5)].一共有5个空指针被利用,加上上面的右子树利用后一共有个空指针被利用
实线空心箭头为前驱pv,虚线实心箭头为后继nxt
就更容易看出,线索二叉树,等于是把一棵二叉树变成了一个双向链表,这样对于我们的插入删除节点,查找某个节点都带来了方便.所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程为线索化
二叉搜索树与双向链表OJ题目练习
Java:构建代码
/**publicclassTNod{intval=0;TNodlft=null;TNodright=null;publicTNod(intval){this.val=val;}}*/publicclassSolution{privatTNodpv=null;//.用来记录前驱节点privatvoidConvrtChild(TNodroot){if(root==null){turn;}ls{//.根绝二叉搜索树性质:中序遍历就是有序结果ConvrtChild(root.lft);/*.建立前后指向节点的左子树是前驱,右子树是后继对于最左端叶子结点这种没有左右子树的结点要特殊考虑:保留的前驱节点的右子树指向当前函数调用的节点,但对于这种情况还需要判断它是否为null,否则就会空指针异常.lft=nullnull.right=;空指针异常null=;加上if判断后:.lft=null;null=;程序turn返回到6节点函数6.lft=;.right=6;=6;*/root.lft=pv;//第一次递归结束返回到root是这个节点if(pv!=null){pv.right=root;}pv=root;ConvrtChild(root.right);}}publicTNodConvrt(TNodpRootOfT){if(pRootOfT==null){turnnull;}ls{ConvrtChild(pRootOfT);whil(pRootOfT.lft!=null){pRootOfT=pRootOfT.lft;}turnpRootOfT;}}}
Java语言在定义节点类的时候只需要:数据域val,左子树lft,右子树right,在实现双向链表的时候需要额外一个pv节点来存放当前节点的前驱
C:线索二叉树结构体思路lchild:左子树,rchild:右子树
对于C语言而言,我们如何知道某一节点的lchild是指向它的左孩子还是指向前驱呢?rchild是指向右孩子还是后继呢?比如:E节点的lchild是指向它的左子树J,而rchild却是指向它的后继A.显然我们在决定lchild是指向左孩子还是前驱,rchild是指向右孩子还是后继上是需要一个区分标志的.因此我们给每个节点在增设两个标志域ltag和rtag,注意ltag和rtag只是存放0和的布尔型变量,其占用的内存空间要小于像lchild和rchild的指针变量
ltag==0时指向该节点的左孩子,为时指向该节点的后继rtag==0时指向该节点的右孩子,为时指向该节点的后继
typdfintDataTyp;//数据类型typdfnum{Link,//Link==0表示只想做还有子树指针Thad,//Thad==表示只想前驱或后继的线索}PointrTag;typdfstructBiThrNod{//二叉树存储节点结构DataTypdata;//数据域structBiThrNod*lchild,*rchild;//左右子树PointrTagLTag;//左标志PointrTagRTag;//右标志}BiThrNod,*BiThrT;
那么了解了C语言的结构体构造线索二叉树原理后我们该如何实现呢?
参考前边Java代码的实现,我们发现可以规律无非是左根右的方式处理数据.无非是中间那部分根的数据如何处理
BiThrNod*pv;//全局变量,始终指向刚刚访问过的节点voidInThading(BiThrNod*pb){if(pb){/**中序遍历线索化二叉树递归函数*///.左InThading(pb-lchild);/**.中间部分建立联系*因为中序遍历之后第一个元素就是链表的头节点,所以应该选取左节点为空的节点就是链表头节点**前驱分析:*if(!pb-lchild):表示如果某结点的左子树域为空,因为其前驱节点刚刚访问过*赋值给了pv,所以可以把pv赋值给pb-lchild,并修改pb-Ltag=Thad.完成了前驱节点的线索化*后继分析:*此时pb节点的后继还没有访问到,只能通过它的前驱节点pv的右子树rchild来判断:*if(!pv-rchild)为空,则pb就是pv的后继,于是pv-Thad,pv-rchild=pb完成后继节点的线索化*完成前驱和后继的判断后把pb给pv,便于下一次遍历*/if(!pb-lchild){//如果没有左孩子pb-LTag=Thad;//前驱线索pb-lchild=pv;//左孩子指针指向前驱}if(!pv-rchild){//如果没有右孩子pv-LTag=Thad;//后继线索pv-lchild=pb;//右孩子指针指向后继}pv=pb;//.右InThading(pb-rchild);}}
.总结回顾
二叉树每个结点最多两棵子树，有左右之分。提到了斜树，满二叉树、完全二叉树等特殊二叉树的概念我们接着谈到它的各种性质，这些性质给我们研究二叉树带来了方便。二叉树的存储结构由于其特殊性使得既可以用顺序存储结构又可以用链式存储结构表示遍历是二叉树最重要的一门学问，前序、中序、后序以及层序遍历都是需要熟练掌握的知识。要让自己要学会用计算机的运行思维去模拟递归的实现，可以加深我们对递归的理解。不过，并非二叉树遍历就一定要用到递归，只不过递归的实现比较优雅而已。这点需要明确二叉树的建立自然也是可以通过递归来实现搜索二叉树能实现查找效率较大化,如果遇到斜树则会变的很慢研究中也发现，二叉链表有很多浪费的空指针可以利用，查找某个结点的前驱和后继为什么非要每次遍历才可以得到，这就引出了如何构造一棵线索二叉树的问题。线索二叉树给二叉树的结点查找和遍历带来了高效率最后，我们知道了关于二叉树的另一个应用，赫夫曼树和赫夫曼编码，对于带权路径的二叉树做了详尽地讲述，让你初步理解数据压缩的原理，并明白其是如何做到无最后，我们提到了关于二叉树的-一个应用，赫夫曼树和赫夫曼编码，对于带权路径的二叉树做了详尽地讲述，让你初步理解数据压缩的原理，并明白其是如何做到无损编码和无错解码中间插入的一些力扣,牛克在线OJ就当练手与解析,有兴趣的可以去刷一刷.
5.结束语
二叉树相较于链表,队列,栈显然更难一层楼.路漫漫求修远兮,吾将上下而求索.勉励自己页面每一个来看我博客的人共同进步,学习更高质量的知识为目标.
,