完全二叉樹演算法

㈠ 二叉樹演算法

二叉樹的演算法主要分為三種：先序遍歷，中序遍歷和後序遍歷。二叉樹（Binary Tree）是n（n>=0）個節點的有限集合，該集合或者空集（稱為空二叉樹），或者由一個根節點和兩棵互不相交的，分別稱為根節點的左子樹和右子樹的二叉樹組成。

(1)完全二叉樹演算法擴展閱讀

二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的'子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^（i 1）個結點;深度為k的二叉樹至多有2^k 1個結點;對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0 = n2 + 1。二叉樹演算法常被用於實現二叉查找樹和二叉堆。

概念

編輯 語音

二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。

基本形態：

二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：

(1)空二叉樹——(a)

(2)只有一個根結點的二叉樹——(b);

(3)右子樹為空的二叉樹——(c);

(4)左子樹為空的二叉樹——(d);

(5)完全二叉樹——(e)

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

㈡ 二叉樹各種計算公式總結有哪些

二叉樹各種計算公式總結有n個節點的二叉樹一共有2n除以n乘以 n+1這種，n層二叉樹的第n層最多為2乘n減1個。二叉樹節點計算公式 N 等於n0加n1加n2，度為0的葉子節點比度為2的節點數多一個。N等於1乘n1加2乘n2加1。具有n個節點的完全二叉樹的深度為log2n加 1。

二叉樹的含義

二叉樹是樹形結構的一個重要類型。許多實際問題抽象出來的數據結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存儲結構及其演算法都較為簡單，因此二叉樹顯得特別重要。二叉樹特點是每個最多隻能有兩棵子樹，且有左右之分。

二叉樹是n個有限元素的集合，該集合或者為空，或者由一個稱為根的元素及兩個不相交的，被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。當集合為空時，稱該二叉樹為空二叉樹。

㈢ 什麼是完全二叉樹，並舉例說明， 以及樹高度、深度的計算，並舉例。

完全二叉樹是指這樣的二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只連續缺少右邊的若干結點。

具有n個結點的完全二叉樹的深度為[log2n]+1

例：一棵完全二叉樹共有64個結點，深度為[log2（2^6）]+1=7

㈣ 完全二叉樹的葉子節點數公式是什麼

完全二叉樹的葉子節點數公式為：

設葉子節點數為n0, 度為1的節點數為n1，度為2的節點數為n2，總節點為n。

1、當n為奇數時（即度為1的節點為0個），n0= (n+1)/2。

2、當n為偶數（即度為1的節點為1個）， n0= n/2。

n1，n2，都可以求。

特殊類型：

1、滿二叉樹：如果一棵二叉樹只有度為0的結點和度為2的結點，並且度為0的結點在同一層上，則這棵二叉樹為滿二叉樹。

2、完全二叉樹：深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1到n的結點一一對應時，稱為完全二叉樹。

3、完全二叉樹的特點是葉子結點只可能出現在層序最大的兩層上，並且某個結點的左分支下子孫的最大層序與右分支下子孫的最大層序相等或大1。

相關術語：

1、結點：包含一個數據元素及若干指向子樹分支的信息。

2、結點的度：一個結點擁有子樹的數目稱為結點的度。

3、葉子結點：也稱為終端結點，沒有子樹的結點或者度為零的結點。

4、結點的層次：從根結點開始，假設根結點為第1層，根結點的子節點為第2層，依此類推，如果某一個結點位於第L層，則其子節點位於第L+1層。

5、樹的深度：也稱為樹的高度，樹中所有結點的層次最大值稱為樹的深度。

以上內容參考 網路-二叉樹

㈤ 計算機二級二叉樹演算法

1、二叉樹的概念

二叉樹是一種特殊的樹形結構，每個結點最多隻有兩棵子樹，且有左右之分不能互換，因此，二叉樹有五種不同的形態。

2、二叉樹的性質

性質1 在二叉樹的第k層上，最多有2^(k-1)(k≥1）個結點。

性質2 深度為m的二叉樹最多有2^m-1個結點。

性質3 在任意一棵二叉樹中，度為0的結點（葉子結點）總是比度為2的結點多一個。

性質4 具有n個結點的二叉樹，其深度不小於[log2n]+1,其中[log2n]表示為log2n的整數部分。

㈥ 完全二叉樹葉子節點的演算法

設：度為i的結點數為ni，由二叉樹的性質可知：
n0 = n2 + 1……………………①式
n = n0 + n1 + n2……………②式
由①式可得 n2 = n0 - 1，帶入②式得：
n0 = （n + 1 - n1）/ 2
由完全二叉樹性質可知：
如圖，當n為偶數時，n1 = 1， n0 = n / 2

將兩式合並，寫作：n0 = ⌊（n+1）/2⌋（向下取整符號不能丟）

(6)完全二叉樹演算法擴展閱讀：

完全二叉樹的特點:

1.葉子結點只可能在層次最大的兩層上出現。

2.對任一結點，若其由分支下的子孫的最大層次為l，則其左分支下的子孫的最大層次必為l或l+1。

完全二叉樹的性質：

1.具有n個結點的完全二叉樹的深度為⌊log₂n⌋+1。

2.如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點i，有：

（1）如果i=1，則結點i是二叉樹的根節點，無雙親；如果i>1，則其雙親是結點⌊i/2⌋。

（2）如果2i>n，則結點i無左孩子；否則其左孩子是結點2i。

（3）如果2i+1>n，則結點i無右孩子；否則其右孩子是結點2i+1。

㈦ 二叉樹的深度演算法怎麼算啊

二叉樹的深度演算法：
一、遞歸實現基本思想：
為了求得樹的深度，可以先求左右子樹的深度，取二者較大者加1即是樹的深度，遞歸返回的條件是若節點為空，返回0
演算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非遞歸實現基本思想：
受後續遍歷二叉樹思想的啟發，想到可以利用後續遍歷的方法來求二叉樹的深度，在每一次輸出的地方替換成算棧S的大小，遍歷結束後最大的棧S長度即是棧的深度。
演算法的執行步驟如下：
（1）當樹非空時，將指針p指向根節點，p為當前節點指針。
（2）將p壓入棧S中，0壓入棧tag中，並令p執行其左孩子。
（3）重復步驟（2），直到p為空。
（4）如果tag棧中的棧頂元素為1，跳至步驟（6）。從右子樹返回
（5）如果tag棧中的棧頂元素為0，跳至步驟（7）。從左子樹返回
（6）比較treedeep與棧的深度，取較大的賦給treedeep，對棧S和棧tag出棧操作，p指向NULL，並跳至步驟（8）。
（7）將p指向棧S棧頂元素的右孩子，彈出棧tag，並把1壓入棧tag。（另外一種方法，直接修改棧tag棧頂的值為1也可以）
（8）循環（2）~（7），直到棧為空並且p為空
（9）返回treedeep，結束遍歷
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}

㈧ 如何計算滿二叉樹或者是完全二叉樹的葉數

滿二叉樹定義：一棵深度為k，且有2的(k)次方－1個節點的二叉樹
如果已知深度k，那麼葉數為2的(k-1）次方個葉子
如果已知總節點數n (n = 2的(k)次方- 1），那麼葉數為(n + 1) / 2
比如一個深度為3的滿二叉樹，一共有7個節點（第1層1個，第2層2個，第3層4個），葉子數為4
（4 = 2的(3 - 1)次方， 4 = (7 + 1) / 2

完全二叉樹的定義：深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為完全二叉樹

完全二叉樹的葉子數為(n + 1) / 2取下整
例如5個節點的完全二叉樹，第二層2個節點，其中右節點為葉子；第三層2個節點都是葉子

㈨ 二叉樹演算法是什麼

二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。

二叉樹的第i層至多有2^（i 1）個結點；深度為k的二叉樹至多有2^k 1個結點；對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0 = n2 + 1。二叉樹演算法常被用於實現二叉查找樹和二叉堆。

二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。

(9)完全二叉樹演算法擴展閱讀：

二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：

1、空二叉樹——(a)

2、只有一個根結點的二叉樹——(b);

3、右子樹為空的二叉樹——(c);

4、左子樹為空的二叉樹——(d);

5、完全二叉樹——(e)

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

㈩ 二叉樹 的 常用公式 誰能和新手 說說啊！

(1) 在二叉樹中，第i層的結點總數不超過2^(i-1)；

(2) 深度為h的二叉樹最多有2^h-1個結點(h>=1)，最少有h個結點；

(3) 對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1；

(4) 具有n個結點的完全二叉樹的深度為int（log2n）+1；

(5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：

若I為結點編號則 如果I<>1，則其父結點的編號為I/2；

如果2*I<=N，則其左兒子（即左子樹的根結點）的編號為2*I；若2*I>N，則無左兒子；

如果2*I+1<=N，則其右兒子的結點編號為2*I+1；若2*I+1>N，則無右兒子。

(6)給定N個節點，能構成h(N)種不同的二叉樹。

h(N)為卡特蘭數的第N項。h(n)=C(n,2*n)/(n+1)。

(10)完全二叉樹演算法擴展閱讀：

類型

(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。

(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。

二叉排序樹又叫二叉查找樹或者二叉搜索樹，它首先是一個二叉樹，而且必須滿足下面的條件：

1）若左子樹不空，則左子樹上所有結點的值均小於它的根節點的值；

2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；

3）左、右子樹也分別為二叉排序樹。

若一個結點有子樹，那麼該結點稱為子樹根的「雙親」，子樹的根稱為該結點的「孩子」。有相同雙親的結點互為「兄弟」。一個結點的所有子樹上的任何結點都是該結點的後裔。從根結點到某個結點的路徑上的所有結點都是該結點的祖先。

結點的度：結點擁有的子樹的數目。

葉子結點：度為0的結點。

分支結點：度不為0的結點。

樹的度：樹中結點的最大的度。

層次：根結點的層次為1，其餘結點的層次等於該結點的雙親結點的層次加1。

樹的高度：樹中結點的最大層次。

森林：0個或多個不相交的樹組成。對森林加上一個根，森林即成為樹；刪去根，樹即成為森林。