首页 > 代码库 > 二叉树逻辑结构重点

二叉树逻辑结构重点



                                   二叉树
1.满二叉树:在二叉树中所有的根结点都有左右子数。并且所有的叶子都在同一层上

2.完全二叉树:编号为i的结点与同深度的满二叉树中编号为i的元素位置相同。

3.满二叉树特点:

  a.叶子只能出现在最下面一层;

  b.只有度为0或2的

4.完全二叉树特点:

  a.叶子只能出现在最下两层,且最下层的叶子主要集中在左侧的连续位置

  b.若有且仅有一个度为1的结点,并且该节点只能有左结点。

5.二叉树性质:

  a.二叉树的第i层上最多有2^(i-1)个结点

  b.一颗深度为K的二叉树中,最多有2^k-1个结点,最少有K个结点

    (出现最多的情况是满二叉树 ,最少的情况是斜二叉树)

  c.二叉树中,如果叶子的结点的个数为n0,度=2的结点个数为n2,则有n0=1+n2;

  d.具有n个结点的完全二叉树的深度为【log2n(以二为底n的对数)】+1

  e.具有n个结点的完全二叉树中的结点从1开始按层标号,任意的编号为i的结点有:

            @1.如果i>1,结点i的双亲的编号为【i/2】,否则结点i就是根结点,无双亲;

            @2.若2i<=n,结点i的左孩子的编号为2i,否则无左孩子。

            @3.若2i+1<=n,结点i的右孩子编号为2i+1,否则无右孩子。                        *****

6.二叉树的遍历:

从根结点出发,按照某种次序访问书中的所有的结点,每个结点都被访问密且仅被访问一次。因为二叉树有根结点和左右子数,所有遍历就
有三种方式:前序遍历||中序遍历||后序遍历。另外从另一个角度考虑可以按层遍历。所以一共四种遍历方式。

  a.前序遍历:根结点->左结点->右结点

  b.中序遍历:左结点->根结点->右结点

  c.后序遍历:左结点->右结点->根结点

  d.层序遍历:按曾从上到下,在每层中按从左到右的顺序遍历。

二叉树逻辑结构重点