二叉樹參數計算方法研究

『壹』 二叉樹的演算法

如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1~n的結點一一對應，這棵二叉樹稱為完全二叉樹。
可以根據公式進行推導，假設n0是度為0的結點總數（即葉子結點數），n1是度為1的結點總數，n2是度為2的結點總數，由二叉樹的性質可知：n0＝n2＋1，則n= n0＋n1＋n2（其中n為完全二叉樹的結點總數），由上述公式把n2消去得：n= 2n0+n1－1，由於完全二叉樹中度為1的結點數只有兩種可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合並成一個公式：n0＝（n＋1）/2 ，就可根據完全二叉樹的結點總數計算出葉子結點數。

因此葉子結點數是(839+1)/2=420

『貳』 二叉樹的深度演算法怎麼算啊

二叉樹的深度演算法：
一、遞歸實現基本思想：
為了求得樹的深度，可以先求左右子樹的深度，取二者較大者加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
}

『叄』 二叉樹的深度怎麼算

二叉樹的深度計算，首先要判斷節點，以下是計算二叉樹的詳細步驟：

1、一顆樹只有一個節點，它的深度是1；

2、二叉樹的根節點只有左子樹而沒有右子樹，那麼可以判斷，二叉樹的深度應該是其左子樹的深度加1；

3、二叉樹的根節點只有右子樹而沒有左子樹，那麼可以判斷，那麼二叉樹的深度應該是其右樹的深度加1；

4、二叉樹的根節點既有右子樹又有左子樹，那麼可以判斷，那麼二叉樹的深度應該是其左右子樹的深度較大值加1。

一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且最後一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。

具有n個節點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個葉子節點，至多有2k-1個節點。

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

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

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

『肆』 二叉樹各種計算公式總結有哪些

二叉樹各種計算公式總結有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個有限元素的集合，該集合或者為空，或者由一個稱為根的元素及兩個不相交的，被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。當集合為空時，稱該二叉樹為空二叉樹。

『伍』 關於二叉樹的計算

答案：dgebhfca

分析：排列的概念問題，就不多說了。從前序排列可以得出，樹的根節點為a，根節點的左節點為b，再根據中序排列中從根節點a的左右分開分別為左右子樹的結點，左子樹為dbge，右子樹為chf，再根據前序排列c為右子樹第一個即為根節點的右結點。再根據中序排列中右邊根節點的左邊為d，即d為b的左子樹且可以看出d沒有左右子樹，又在根據前序排列中e緊跟在b後面得出e為b右子樹，再根據根據中序排列中g在e前得出g為e的左子樹。

根節點的右子樹就不多做分析了，原理類似。

最後得出如下二叉樹，最後再進行後序排列。

『陸』 二叉樹演算法

int deep(BiTree T)
{
int a,b;
if(T==NULL)//若為空樹，深度為0
return 0;
if((a=deep(T->lchild))>(b=deep(T->rchild)))//若左孩子深度大於右孩子
return(a+1);//返回左孩子深度＋1
else reurn(b+1);//否則返回右孩子深度＋1
}

『柒』 二叉樹的葉子節點數如何計算

結點的度是指，該結點的子樹的個數，在二叉樹中，不存在度大於2的結點。

計算公式：n0=n2+1

n0 是葉子節點的個數

n2 是度為2的結點的個數

n0=n2+1=5+1=6

故二叉樹有5個度為2的結點，則該二叉樹中的葉子結點數為6。

(7)二叉樹參數計算方法研究擴展閱讀

葉子結點是離散數學中的概念。一棵樹當中沒有子結點（即度為0）的結點稱為葉子結點，簡稱「葉子」。 葉子是指度為0的結點，又稱為終端結點。

葉子結點 就是度為0的結點 就是沒有子結點的結點。

n0：度為0的結點數，n1:度為1的結點 n2：度為2的結點數。 N是總結點

在二叉樹中：

n0=n2+1；

N=n0+n1+n2

參考資料：葉子結點_網路

『捌』 二叉樹參數計算，急求

給你提供思路吧，使用先根遍歷程序搜索所有子節點，搜索完畢數量就統計出來了。具體流程：找到最底層的一個葉子，然後分配一個int數組 數組長度是樹的層數，

『玖』 二叉樹結點的計算方法

一般會給你一度的結點個數，在給你一個已知的0度或是2度的節點個數

再根據度是0的節點個數比度是2的節點個數多1的二叉樹特性來算出總共的節點！

『拾』 c語言中二叉樹個數計算方法

遞歸……非空樹的總結點數=左子樹結點數+右子樹結點數+1（也就是根結點）。
偽代碼：
int
node_counter(TreeNode
*root)
{
if
(root==null)
return
0;
else
return
node_counter(root->left)
+
node_counter(root->right)
+
1;
}