图中的结点数量为 15 个,套用 性质4 的公式可以得出 log2n + 1 = log215 + 1 = 3.91(向下取整) + 1 = 3 + 1 = 4 ,当前树的深度即为 4 ,性质4 和 性质2 可以看作是互补的
对于 性质5 来说,请注意每个结点边上的编号,我们就选取 E 结点来作为例子说明。E 结点当前为 5 ,所以它的双亲为 5 / 2 = 2 (向下取整);E 的左孩子为 2i ,也就是 2*5=10 ,E 的右孩子为 2i + 1 ,也就是 2*5+1 = 11;性质5 的定义中说得更抽象一些,而且是拿叶子结点来做说明的,针对的是整个二叉树的情况,但其实意思和我们这里解释的是一样的,大家可以再拿其它结点验证一下。性质5 对于后面我们要讲的使用顺序结构来存储二叉树非常重要!
请务必掌握并记牢二叉树的这五个性质及其含义,因为在后面的学习中,不管是二叉树的顺序、链式存储结构,还是二叉树的遍历,都有可能会接触到上面的五个性质中的内容。可以说,它们就是二叉树学习中最最基础的灵魂。
森林
最后,我们来简单的了解下什么是“森林”。多个树放在一起,就形成了一片“森林”。就像上文中二叉树的解释图一样,(a)(b)(c)(d)放在一起将它们整体一起来看,就是一片“森林”,在这片“森林”中分别有着(a)(b)(c)(d)这四颗树。
森林中的树和树之间是没有联系的,如果我们要操作或者遍历一个森林的话,往往是将这片森林转化为一颗树。具体的算法和步骤不是我们学习的重点,所以大家了解一下即可,有想深入研究的同学可以搜索相关的内容或者查阅相关的教材。
总结
从栈和队列前进到树后,是不是突然感觉到一下子就迈了一大步?有点搞不懂了?没关系,今天的内容其实都是一些基础的理论内容,能理解的就理解,不能理解的就接着继续学习之后再返过来看今天的这些概念。
学习就不不断地重复进步地过程,当然一切都还是要以地基为基础的。当你了解了树的数据结构及一些简单的遍历算法之后,再回来深入的理解这些概念并把他们背下来,相信一般的面试中关于树相关的题目就不在话下了,一起努力吧!
推荐学习:php视频教程
以上就是三分钟带你了解树和二叉树的详细内容!