由于二叉树的知识更倾向于理论,所以我们在实际应用开发过程中使用的并不多,但是二叉树作为数据结构的一个重要的组成部分,所以,在程序猿的面试过程中,会经常遇到二叉树知识相关问题.所以学习二叉树是相当有必要的.
我们先看一下二叉树的定义是如何的.
对于特殊二叉树,我只想谈一下满二叉树和完全二叉树,因为这两种二叉树容易发生混乱.
定义: 在一棵二叉树中,如果所有的分支节点都存在左子树和右子树,并且所有叶子都在同一层面上,这样的二叉树成为满二叉树.
下面我们看一下满二叉树和普通的二叉树的区别以及构成
其实学习完全二叉树要与满二叉树对比着看,首先我们先看一下完全二叉树的定义
定义: 对于一棵具有 n 个节点的二叉树按层序编号,如果编号为 i ( 1<= i <= n)的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中位置完全相同,则这棵二叉树成为完全二叉树.
看完上面的完全二叉树和满二叉树的定义和特点,可能对两种特殊的二叉树有所混淆,所以我们来区分一下两种二叉树,首先从字面上区分,"完全"和"满"的差异,满二叉树一定是一棵完全二叉树,但完全二叉树不一定是满的.其实,完全二叉树的所有节点与同样深度的满二叉树,他们按层序编号相同的结点,是一一对应的,这里有个关键词是按层序编号.
二叉树的性质在面试题中会经常提到并且使用它进行计算面试题中的题目.那么接下来,看一下二叉树都有一些什么的性质吧.
如下图,第一层是根节点,只有一个,所以是 2^(1-1) = 2^0 = 0.第二层有两个,2^(2-1) = 2 ^ 1 = 2.第三层有四个,2^(3-1) = 2 ^ 2 = 4.所以通过数据归纳法的论证,很容易得到二叉树的第 i 层上至多有2(i -1) 个结点的结论.
还是上面的图,深度为k的意思就是有K层的二叉树.如果有一层,至多有1 = 2 ^ 1 -1 个结点.如果有两层,至多有1 + 2 = 2^2 -1个结点.如果有三层,至多有1 + 2 + 4 = 2^3 -1个结点.所以通过数据归纳法的论证,很容易得到深度为 k 的二叉树至多有 2^k - 1 个节点(k >= 1)的结论.
终端结点其实就是叶子结点数,而一棵二叉树,除了叶子结点 外,剩下的就是度为1或2的结点数了.我们设n1为度1的节点数.则数的总结点数为 n = n1 +n2 +n0;我们来看下图,这个二叉树的总结点数为10,它是由A,B,C,D等度为2的结点,F,G,I,J等度为0的叶子结点和E这个度为1的结点组成.总和为4 + 1 + 5 = 10;再来看一下,下图的总的连接线数为9,用代数表达式就是分支总数= n -1 = n1 + n2 ,因为我们刚才有等式 n = n0 + n1 + n2 ; 所以可以推导出来 n0 +n1 +n2 -1 = n1 +2 * n2, 结论就是n0 = n2 + 1;
一个完全二叉树的结点数一定少于等于同样读书的满二叉树的结点数2k-1,但一定多于2(k-1) -1;即为2^(k-1) -1 < n <= 2^k-1;由于结点数为整数,所以我们可以简化不等式,所以 2^(k-1) <= n < 2^k,不等式两边去对数 k-1 <= log2n <k ,因此 k = [log (2) n] + 1.(注:k为深度)
我们还是以下面这一棵二叉树进行验证,通过对性质5的一一比对,发现性质5是正确的,这里我就不一一比对了.
二叉树的遍历多种多样,这里我只说,三种常用的遍历,前序遍历,中序遍历,后续遍历.我们在面试当中会遇到当量的二叉树遍历的问题.
####### 内容: 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。