php之二叉树

二叉树的特点:

①、每个节点最多有两个子树,所以二叉树中不存在度大于2的节点。注意不是只有两个子树,最多有两个子树,没有子树或者只有一颗子树都是可以的。

②左子树和右子树是有顺序的。

③即使树中只有一颗子树,也要区分它是左子树还是右子树。

二叉树具有五种基本形态。

①、空二叉树。

②、只有一个根节点。

③根节点只有左子树。

④根节点只有右子树。

⑤根节点既有左子树又有右子树。

特殊的二叉树

①斜树

所有的节点都只有左子树的二叉树称为左斜树。

所有的节点都只有右子树的二叉树称为右斜树。

②满二叉树

在一颗二叉树中,如果所有的分支节点都存在左子树和右子树,并且所有的叶子结点都在同一层上,这样的二叉树称为满二叉树。

满二叉树的特点:

1、叶子只能出现在最下面一层。

2、非叶子结点的度一定是2.

3、同样结点的二叉树中,满二叉树中结点个数最多,叶子结点最多

③完全二叉树

完全二叉树的特点:

1、叶子结点只能出现在最下面的两层。

2、最下层的叶子一定集中在左侧连续位置。

3、倒数第二层有叶子结点,一定集中在右侧连续位置。

4、如果某个结点的度是1,则该结点一定只有左孩子。

5、同样结点的二叉树,完全二叉树的深度是最小的。

二叉树的性质

①在二叉树中的第n层,最多2的n-1次方个结点(n>1)。

②在一颗深度为n的二叉树中,最多有2的n次方-1个结点。(n>1)

对于任意一颗二叉树,n0代表叶子结点的个数,n1代表度数为1的节点的个数,n2代表度度数为2的节点的个数。

则由于节点的总个数

n = n0 + n1 + n2

然后根据连接线,计算一颗二叉树的进入线的条数

由于根节点没有分支进入,则总的进入线条数等于n-1,然后根据节点的度计算总的进入线条数为n1+2n2

即n-1 = n1 + n2

根据①式和②式可得n0 = 2n2+1.

③一颗完全二叉树的深度,假设二叉树的深度为h,节点个数为n,

则由于一颗二叉树的节点总个数为2的h次方-1,

最大极端情况是这课完全二叉树是满二叉树,则n小于等于2的h次方-1

最小极端的情况是把这颗完全二叉树的最下层去掉,则n > 2的h-1次方-1

结合这两个式子可得h小于等于log2 n

上一篇:android资料


下一篇:基于CentOS与VmwareStation10搭建Oracle11G RAC 64集群环境:4.安装Oracle RAC FAQ-4.7.Oracle 11G R2 RAC修改public网络IP