二叉樹(Binary Tree):每個結(jié)點至多只有兩顆子樹，二叉樹的子樹有左右之分，不能任意顛倒。

下面給出二叉樹的5種基本形態(tài)（如下圖）

二叉樹的性質(zhì)：

1.二叉樹第i層上至多有2^(i-1)個結(jié)點(i>=1)。

2.深度為k的二叉樹至多有2^k-1(k>=1)個結(jié)點。

3.對任何一顆二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。

怎么證明？如下圖:

這個就比較困難了，需要推導獲得
首先我們再假設(shè)度為1的結(jié)點數(shù)為n1，則二叉樹T的結(jié)點總數(shù)n=n0+n1+n2
其次我們發(fā)現(xiàn)連接數(shù)總是等于總結(jié)點數(shù)n-1，并且等于n1+2*n2
所以n-1=n1+2*n2
所以n0+n1+n2-1=n1+n2+n2
最后n0=n2+1

4.具有n個結(jié)點的完全二叉樹的深度為[log2n]+1([]不是中括號，是取下線的意思如，如果是2.3，則取下線后就2)

證明的話就是性質(zhì)2求k，指數(shù)函數(shù)和對數(shù)函數(shù)互為反函數(shù)

5.對一顆有n個結(jié)點的完全二叉樹（其深度為[log2n]+1）的結(jié)點按層序編號，對任意一結(jié)點i(i<=i<=n)有以下性質(zhì)

如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i>1，則其雙親是結(jié)點[i/2](取下線)。

如果2i>n，則結(jié)點i無做做孩子（結(jié)點i為葉子結(jié)點）；否則其左孩子是結(jié)點2i。

如果2i+1>n，則結(jié)點i無右孩子；否則其右孩子是結(jié)點2i+1。

一顆深度為k且有2^k-1個結(jié)點的二叉樹稱為滿二叉樹。

深度為k的，有那個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。

如下圖所示：

下面是二叉樹的存儲：

代碼如下：

typedef int ElemType; typedef struct BiTNode {ElemType data;struct BiTNode *lchild, *rchid; }BiTNode,*BiTree;
圖就是這樣的：

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的6.2二叉树及二叉树存储结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。