朝花夕拾 · 数据结构 | 二叉树篇

一.树的基本特性二.二叉树1.定义2.几种特殊的二叉树3.二叉树的基本性质1非空二叉树上的叶结点数等于度为2的结点数加1即n0n2十1。证明:设度为0,1和2的结点个数分别为n0,n1和n2结点总数nn0n1n2。再看二叉树中的分支数除根结点外其余结点都有一个分支进入设B为分支总数则nB1。这些分支是由度为1或2的结点射出的因此又有Bn12n2。于是得n0n1n2n12n21则n0n21。2)非空二叉树的第k层最多有2^(k-1)个结点(k≥1)。第1层最多有2^(1-1)1个结点(根)第2层最多有2^(2-1)2个结点以此类推可以证明其为一个公比为2的等比数列2^(k-1)。3)高度为h的二叉树至多有2^h-1个结点(h≥1)。该性质利用性质2求前h项的和即等比数列求和的结果性质2和性质3还可以拓展到m叉树的情况即m叉树的第k层最多有m^(k-1)个结点高度为h的m叉树至多有(m^h-1)/(m-1)个结点。性质4相对不常用感兴趣了解即可。4)对完全二叉树按从上到下、从左到右的顺序依次编号1,2,...,n则有以下关系:最后一个分支结点的编号为⌊n/2⌋(向下取整,若i≤⌊n/2⌋,则结点i为分支结点否则为叶结点。叶结点只可能在最后两层上出现(相当于在相同高度的满二叉树的最底层、最右边减少一些连续叶结点当减少2个或以上叶结点时次底层将出现叶结点)。若有度为1的结点则最多只可能有一个且该结点只有左孩子而无右孩子(度为1的分支结点只可能是最后一个分支结点其结点编号为⌊n/2⌋)。按层序编号后一旦出现某结点(如编号i)为叶结点或只有左孩子的情况则编号大于i的结点均为叶结点(与结论1和结论3是相通的)。若n为奇数则每个分支结点都有左、右孩子;若n为偶数则编号最大的分支结点(编号为n/2)只有左孩子没有右孩子其余分支结点都有左、右孩子。当i1时结点i的双亲结点的编号为⌊i/2⌋。若结点i有左、右孩子则左孩子编号为2i右孩子编号为2i1。结点i所在层次(深度)为⌊log2 i⌋1。5)具有n个(n0)结点的完全二叉树的高度为⌈log2(n1)⌉或⌊log2n⌋1。设高度为h根据性质3和完全二叉树的定义有2^(h-1)n≤2^h-1 或者 2^(h-1)≤n2^h得2^(h-1) n1 ≤ 2^h即h-1 log2(n1) ≤ h因为h为正整数所以h⌈log2(n1)⌉,或者得h-1≤ log2n h所以h⌊log2n⌋1。4.二叉树的遍历1.先序遍历2.中序遍历3.后序遍历上述三种遍历算法中递归遍历左、右子树的顺序都是固定的只是访问根结点的顺序不同。不管采用哪种遍历算法每个结点都访问一次且仅访问一次所以时间复杂度都是O(n)。在递归遍历中递归工作栈的栈深恰好为树的深度所以在最坏情况下二叉树是有n个结点且深度为n的单支树遍历算法的空间复杂度为O(n)。4.层序遍历