所以树一定有至少一个节点(没有空树的概念),但是二叉树可以没有节点。虽然这个点无关紧要,但还是提一下。
首先我们假设这些点都是独立的那么明显有4x3+3x4+2x5+1x2=36个叶子,但是现在他是树,那么我们将这些独立得东西合并,显然,n个合并会减少n-1个叶子(因为合并只能替换叶子),所以36-(3+4+5+2-1)=23,所以叶子的个数为23
前两个很好理解,就不说了。
第三个:设度为一的节点数为n1所以叶子的个数为:n0=2xn2+n1-(n1+n2-1)=n2+1;记住这个结论,加快解题速度。
当然用PPT上的证明也可以理解,就是麻烦一点,解释一下PPT上第二个式子:
大部分结点头上都有一个分支连着,除了根节点,所以节点数与分支数的关系为:n-1=分支数,即
来道例题:
直接n0-1=19
这个很好理解就是K层的塞满结点(不能再多的树)
就是在满二叉树的基础上,从左往右去掉若干个结点(必须按照顺序,不能越过某一个)
性质5很简单,那就解释一下性质四,n在(2k-1-1,2k-1],即[2k-1,2k-1],所以向下取整后值必为k-1,再加上一个1就是k了。
一个一个来吧,第一题:
100个节点,第一个想法是利用n0=n2+1,先求出层数k,那么从2到k-2之间的都是度为二的,再加上第k层的节点数mod2向下取整得到第k-1层的度为2的节点数。但是这题有更好的方法,还记得那个编号吗,叶子的特点是没有孩子,也就是说叶子的编号乘以二是大于100,那么很明显,51-100都是叶子,共50个。
第二题:第七层可以容下26个,这里明显没有满,所以一共七层,那么总结点书就是,10+前六层的个数(前六层是一个满二叉树)=73,利用上一题的结论叶子数为37,所以n2=37-1=36,进而推出n1=73-37-36=0
第三题:
对的,从完全二叉树定义出发,1到k-2层肯定没有度为1的,k-1层最多一个,k层都是叶子,所以要么一个要么没有,同时这题给了我们一个结论,就是总结点数为偶数的完全二叉树入度为1的个数为1,总结点数为奇数的完全二叉树入度为1的个数为0.
第四题:
两者编号介于[2k-1,2k-1],之间,所以以2为底取对数后向下取整的值是一样都为k-1,考虑这个范围的下面一个,值为k-2,上面一个值为k,所以只要满住以2为底取对数后向下取整的值一样就行。
解答一下两个问题:
一.220-1,230-1,参考满二叉树结点个数
二
第二个问题转化为n1,n0的个数问题就行了
看道习题
有两种情况,一种是第六层是做后一层
第二种是第六层是倒数第二层
第一种情况很简单,也不是节点数最多的。看一下第二种,第六层是满的,加上之前的有26-1个结点,第七层有26-2x5或26-(2x5+1)个结点,所以,最多有26-1+26-2x5个结点。
每次在中序中找分割点就行了:以第一层为例,前序第一个为A,所以A是根节点,中序中以A为分隔点,左边为左子树部分,右边为右子树部分,而且这两团在前序中肯定是抱团存在的,找出这两团,BCDE,FG,这两团的中序就是分割后的两部分,又回到了刚开始的情形,明显B,F为左右孩子,。。。。
这个简单,更之前的一样,只是这次都是从每团的最后一个找。
还有,为什么只有前序和后序不能确定一棵二叉树,答案很明显,我们可以通过后序每团的最后一个和前序每团第一个确定根节点,我们甚至可以根据抱团的原则,找出那个是左边那团,那个是右边那团,但是抱团会出现歧义(当然如果限定条件的话也许可以画出唯一的二叉树)
比如这个:
有这么多种分割方法(框出来的是左子树)。为什么前面说一定会出现歧义:因为子框和红框这两种必然存在的分类方式就已经可以导致歧义了。
练习
(2)不会,先放着
(3)在visit那步加一个计数的就行了。
第一个:限定输出条件就行了,
第二个:跟背包问题(见递归那里)类似,定义一个数组(全局)存待输出的值,再定义一个数(局部)存放入了几个数,不断往左往右试探,遇到叶子就打印数组。
第三个:解答PPT上有,这个递归函数的出口时到达叶子时返回1
return max(fun(T->left),fun(T->right))+1 //T是当前结点
二叉树包含数据和结构,数据好说,但是结构难搞。
这里的解决方案是要求用户以前序遍历的结果输入数据
传入当前节点指针的引用用于改变当前的内容(NULL或塞东西)
还有get_root的反回值必须是引用,不然我们没法改变根节点指针的指向。
这个从根节点开始,一个一个来相互补充就行了。
略,详见视频笔记
森林:很多棵树
就是把上面的结点位置变了一下,没有结构上的改变,因为上面的本来就是一棵二叉树。
为了跟上面做区分,树与数之间用红线相连。
就是前序遍历化完后的二叉树
把结点的指针塞给优先队列,然后拿前两个合并一下重新塞回去
这个结论记一下
从根节点往下走,往左记0往右记1,解码的话就是把按照码不断从根节点往下走(0往左,1往右遇到根节点就打印,然后回到根节点)