CWYAlpha

Just another WordPress.com site

Thought this was cool: 数据结构重读 – 二叉树

leave a comment »


1、二叉树(Binary Tree)是一种特殊的树形结构:每个结点至多有两棵子树,即二叉树中不存在度大于2的结点。

2、二叉树的子树有左右之分,次序不能任意颠倒。

3、性质1:二叉树的第i层上至多有2^(i-1)个结点,i从1下标开始。所有

4、性质2:深度为k的二叉树至多有2^k -1个结点,k也是从1下标开始。

5、性质3:对于任何一棵二叉树,如果终端结点数为n0,度为2的结点数为n2,则n0 = n2+1。这个很简单:

(1)设度为1的结点数为n1,则总结点数n = n0 + n1 + n2。
(2)根据先前的(任意树)上的公式:结点数量 = 所有结点度之和 + 1,即n = n0+ n1 + n2 = n1 + 2 n2 +1,两边消掉,有:

n0 = n2 + 1。

6、满二叉树:一棵深度为k,且有2^k -1个结点的二叉树。特点是每一层都是满的。

7、完全二叉树不是满二叉树!它的结点可以不足2^k – 1,但是深度必须和对应的满二叉树对应,已经有的结点从1~k必须和同深度的满二叉树一一对应(即在满二叉树的第k层从右向左去掉若干个结点,至少保留一个结点)。

8、满二叉树是完全二叉树,但完全二叉树不是满二叉树!

9、性质4:具有n个结点的完全二叉树,深度为[ log(n)] + 1,其中[]是向下取整。

10、性质5:如果对一棵有n个结点的完全二叉树的结点按层次编号,每层从左到右,层次从上到下。对任意结点i,
(1) 如果i=1,结点i是二叉树的根,无双亲。i>1,则双亲PARENT(i)是结点[i/2],还是向下取整。
(2) 如果2i>n,则结点无左孩子,否则左孩子是2i。
(3)如果2i+1>n,无右孩子,否则右孩子是2i+1。

11、二叉树的顺序存储,利用上述性质5,可以把任何一个二叉树映射到完全二叉树上,从而映射到数组上。当然这个数组的中间某些位置可能是“空的”。

12、

 

 

 
from 四号程序员四号程序员: http://www.coder4.com/archives/3177

Written by cwyalpha

五月 19, 2012 在 9:53 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: