首页 > 代码库 > 二叉树逻辑结构重点
二叉树逻辑结构重点
二叉树
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.层序遍历:按曾从上到下,在每层中按从左到右的顺序遍历。
二叉树逻辑结构重点