二叉樹的性質(zhì)

滿二叉樹

性質(zhì)1：

在二叉樹的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)(i>0)

因?yàn)橐粋€(gè)節(jié)點(diǎn)度不大于2（即每個(gè)結(jié)點(diǎn)只能有兩棵子樹）瀑凝，如果假設(shè)這棵二叉樹是一棵滿二叉樹，那么每個(gè)結(jié)點(diǎn)都有兩棵子樹，按每層來看的話芯砸，會(huì)發(fā)現(xiàn)它是首項(xiàng)為1蒲赂，公比為2的等比數(shù)列，所以第i層最多有2^(i-1)個(gè)結(jié)點(diǎn)(i>0)

性質(zhì)2：

一棵深度為k的二叉樹中醋安，最多有2^k-1個(gè)結(jié)點(diǎn)

其實(shí)這也很好得出這個(gè)性質(zhì)杂彭，既然每層的結(jié)點(diǎn)數(shù)量就是等比數(shù)列的一項(xiàng)，那么深度為k的樹吓揪，假設(shè)為滿二叉樹亲怠，那么結(jié)點(diǎn)總數(shù)就是等比數(shù)列求和，所以柠辞，一棵深度為k的二叉樹中团秽，最多有2^k-1個(gè)結(jié)點(diǎn)

性質(zhì)3：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為[log2n]+1

其實(shí)就是性質(zhì)2的逆推，假設(shè)有棵深度為x的完全二叉樹钾腺，那么他的結(jié)點(diǎn)總數(shù)的范圍為2^(k-1)-1 < n <= 2^k-1徙垫，兩邊同時(shí)取對(duì)數(shù)得k-1 < og2n <= k，具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為[log2n]+1

性質(zhì)4：

對(duì)于一棵非空的二叉樹放棒，如果葉子結(jié)點(diǎn)數(shù)為n0姻报，度為2的結(jié)點(diǎn)數(shù)為n2，
則n0 = n2+1

整棵樹的結(jié)點(diǎn)數(shù)： n = n0+n1+n2 (n0葉子結(jié)點(diǎn)數(shù)间螟，n1度為1的結(jié)點(diǎn)數(shù)吴旋，n2度為2的結(jié)點(diǎn)數(shù))
根據(jù)節(jié)點(diǎn)度的定義子結(jié)點(diǎn)的的數(shù)量為： n0×0+n1×1+n2×2
子節(jié)點(diǎn)的數(shù)量為：n-1 (除根以外每個(gè)結(jié)點(diǎn)都是子節(jié)點(diǎn))
所以解得 n0 = n2+1

性質(zhì)5：

對(duì)于具有n個(gè)節(jié)點(diǎn)的完全二叉樹，如果按照從上至下和從左至右的順序?qū)Χ鏄渲兴薪Y(jié)點(diǎn)進(jìn)行從1的編號(hào)厢破，則對(duì)于任意的序號(hào)為i結(jié)點(diǎn)荣瑟，有:

• 如果i>1，則序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)為i/2摩泪，如果i==1笆焰，則序號(hào)為i的結(jié)點(diǎn)是根節(jié)點(diǎn)，無雙親結(jié)點(diǎn)
• 如果2i<=n见坑，則序號(hào)為i的結(jié)點(diǎn)的左孩子節(jié)點(diǎn)的序號(hào)為2i嚷掠，否則i結(jié)點(diǎn)無左孩子
• 如果2i+1<=n，則序號(hào)為i的結(jié)點(diǎn)的右孩子節(jié)點(diǎn)的序號(hào)為2i荞驴，否則i結(jié)點(diǎn)無右孩子

注意:性質(zhì)1,2,4所有二叉樹都通用不皆，性質(zhì)3,5只有完全二叉樹適用

二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹的存儲(chǔ)方式也可以分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種存儲(chǔ)結(jié)構(gòu)

二叉樹的順序存儲(chǔ)結(jié)構(gòu)

這里的順序存儲(chǔ)也是用一組連續(xù)的存儲(chǔ)單元依次從上至下，從左至右存儲(chǔ)二叉樹上的節(jié)點(diǎn)元素熊楼。對(duì)于完全二叉樹來說樹中結(jié)點(diǎn)的序號(hào)都是按照從上至下霹娄，從左至右進(jìn)行編排的，所以結(jié)點(diǎn)的序號(hào)可以唯一的反映節(jié)點(diǎn)之間的邏輯關(guān)系（性質(zhì)5）

完全二叉樹

存儲(chǔ)在數(shù)組中，數(shù)組下表從零開始

數(shù)組下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
-------|----------------------------------
數(shù)據(jù) | A | B | C | D | E | F | G | H | I

如果是一般的二叉樹的話犬耻，如果我在對(duì)他進(jìn)行從上至下踩晶，從左至右進(jìn)行編號(hào)時(shí)就不能很好的反映數(shù)組元素之間的關(guān)系了，如果我們進(jìn)行適當(dāng)?shù)母脑煜阕罚ㄟ^添加一些結(jié)點(diǎn)合瓢，把他補(bǔ)成一顆完全二叉樹，那么再進(jìn)行編號(hào)透典，就可以進(jìn)行順序存儲(chǔ)了

經(jīng)過改造的一般二叉樹

數(shù)組下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
-------|--------------------------------------------
數(shù)據(jù) | A | B | C | D | E | 0 | 0 | 0 | 0 | 0 | F

由此可以看出，這樣的存儲(chǔ)方式顿苇，會(huì)造成很多空間的浪費(fèi)峭咒，而且如果要進(jìn)行對(duì)樹上元素進(jìn)行刪除、插入操作需要移動(dòng)大量的數(shù)據(jù)元素纪岁，因此二叉樹不宜采用順序存儲(chǔ)結(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是凑队，用類似于鏈表的存儲(chǔ)方法來存儲(chǔ)樹上元素的邏輯關(guān)系，即用指針來表示元素之間的邏輯關(guān)系

結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)

data是數(shù)據(jù)域幔翰，leftChild和rightChild是指針域漩氨，leftChild是
指向左兒子的指針，rightChild是指向有兒子的指針叫惊，當(dāng)左兒子或右兒子為空時(shí)，相應(yīng)的指針域也為空

代碼描述

//存儲(chǔ)的數(shù)據(jù)類型
typedef char DataType
typedef struct node
{
    DataType data;              //數(shù)據(jù)域
    struct node* leftChild;     //左兒子
    struct node* rightChild;    //右兒子
}BinNode;
typedef BinNode* BinTree;

這是二叉鏈表的定義做修，除此之外還有三叉鏈表，三叉鏈表比起二叉鏈表多了一個(gè)指向雙親結(jié)點(diǎn)的指針域饰及，如圖所示

結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)

代碼描述

//存儲(chǔ)的數(shù)據(jù)類型
typedef char DataType
typedef struct node
{
    DataType data;              //數(shù)據(jù)域
    struct node* leftChild;     //左兒子
    struct node* rightChild;    //右兒子
    struct node* parent;        //雙親
}BinNode;
typedef BinNode* BinTree;