小樹截點計算方法

⑴ 關於樹的結點演算法，請大家幫幫忙，過程詳細點，謝謝！！！

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define Max 20 //結點的最大個數
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定義二叉樹的結點類型
typedef BinTNode *BinTree; //定義二叉樹的指針
int NodeNum,leaf; //NodeNum為結點數，leaf為葉子數
//==========基於先序遍歷演算法創建二叉樹==============
//=====要求輸入先序序列，其中加入虛結點"#"以示空指針的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())==' ')
return(NULL); //讀入#，返回空指針
else{
T=(BinTNode *)malloc(sizeof(BinTNode));//生成結點
T->data=ch;
T->lchild=CreatBinTree(); //構造左子樹
T->rchild=CreatBinTree(); //構造右子樹
return(T);
}
}
//========NLR 先序遍歷=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //訪問結點
Preorder(T->lchild); //先序遍歷左子樹
Preorder(T->rchild); //先序遍歷右子樹
}
}
//========LNR 中序遍歷===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍歷左子樹
printf("%c",T->data); //訪問結點
Inorder(T->rchild); //中序遍歷右子樹
}
}
//==========LRN 後序遍歷============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //後序遍歷左子樹
Postorder(T->rchild); //後序遍歷右子樹
printf("%c",T->data); //訪問結點
}
}
//=====採用後序遍歷求二叉樹的深度、結點數及葉子數的遞歸演算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求結點數
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度為0，即為葉子。
return(max+1);
}
else return(0);
}
//====利用"先進先出"（FIFO）隊列，按層次遍歷二叉樹==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定義結點的指針數組cq
cq[1]=T; //根入隊
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出隊
printf("%c",p->data); //出隊，輸出結點的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子樹入隊
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子樹入隊
}
}
}
//==========主函數=================
void main()
{
BinTree root;
int i,depth;
printf("NodeNum:%d\n",NodeNum);
printf("Creat Bin_Tree； Input preorder:"); //輸入完全二叉樹的先序序列，
// 用#代表虛結點，如ABD###CE##F##
root=CreatBinTree(); //創建二叉樹，返回根結點
do { //從菜單中選擇遍歷方式，輸入序號。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //先判斷節點數是否已有。不用再先選擇4，求出該樹的結點數。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //輸入菜單序號（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍歷
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍歷
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //後序遍歷
break;
case 4: depth=TreeDepth(root); //求樹的深度及葉子數
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5:
if(!NodeNum)
TreeDepth(root);
printf("LevePrint Bin_Tree: ");
Levelorder(root); //按層次遍歷
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}

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

n0＝（n＋1）/2

設：度為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⌋（向下取整符號不能丟）

(2)小樹截點計算方法擴展閱讀：

按照某種遍歷方式對二叉樹進行遍歷，可以把二叉樹中所有結點排列為一個線性序列。在該序列中，除第一個結點外，每個結點有且僅有一個直接前驅結點；除最後一個結點外，每個結點有且僅有一個直接後繼結點。

但是，二叉樹中每個結點在這個序列中的直接前驅結點和直接後繼結點是什麼，二叉樹的存儲結構中並沒有反映出來，只能在對二叉樹遍歷的動態過程中得到這些信息。為了保留結點在某種遍歷序列中直接前驅和直接後繼的位置信息，可以利用二叉樹的二叉鏈表存儲結構中的那些空指針域來指示。

⑶ 樹的節點和度的計算

樹的高度=log2(這個在底下)（n+1)這個在上面，n=25,這樣可以算出，是多少高，高度為5，高度為4的總結點為（2^4）-1=15，那麼，第5層就剩10,度為0也就是葉子節點為10，度為2的節點是度為0的節點-1，就是9。

例如：

設該樹中所有結點的度為x，因為，在樹的結權點中，除了根結點以外，其餘結點都有一個分支進入，所以，n=x+1，所以x=n-1。

每個結點有零個或多個子結點；沒有父結點的結點稱為根結點；每一個非根結點有且只有一個父結點；除了根結點外，每個子結點可以分為多個不相交的子樹。

(3)小樹截點計算方法擴展閱讀：

對於二叉樹有下列基本運算：

（1）建空二叉樹Setnull（BT），置BT為空二叉樹。

（2）求二叉樹的根root（x），求結點x所在二叉樹的根。

（3）求雙親結點parent（BT，x），在二叉樹BT中求結點x的雙親結點。

（4）求左或右孩子結點lchild（BT，x）或rchild（BT，x），在二叉樹BT中求結點x的左孩子結點或右孩子結點。

⑷ 二叉樹結點的計算

首先我們知道，前序遍歷的規則是：根結點→左子結點→右子結點
中序遍歷是：左子結點→根結點→右子結點
後序遍歷是：左子結點→右子結點→根結點

那麼，對於一棵二叉樹，前序遍歷的第一個結點一定是這棵樹的根結點，即根結點是a。
在中序遍歷的順序dgbaechf中，以a分成左、右兩邊，左邊是dgb，右邊是echf。
所以，這棵樹現在可以確定如下：
a
/\
dgbechf
接下來再分別對左子樹和右子樹進行類似的操作。
對於左子樹dgb來說，在前序遍歷abdgcefh中找到bdg，證明這子樹的根是b，那麼現在可以確定的樹結構如下：
a
/\
bechf
/
dg
再看dg，前序遍歷中的順序為dg，所以d是dg這部分子樹的根，那麼又因為中序遍歷的dg順序也是dg，所以g是右子結點。
即：
a
/\
bechf
/
d
\
g
現在看echf這部分子樹，前序中順序是cefh，所以子樹根結點是c，那麼左子結點是e，右子樹是hf：
得到：
a
/\
bc
//\
dehf
\
g
最後只剩下hf部分了，前序遍歷中是fh，所以根是f，那麼h就是左子結點。
現在得到了整棵樹：
a
/\
bc
//\
def
\/
gh

對這棵樹再進行後序遍歷就行了，結果就是：gdbehfca

⑸ 二叉樹結點計算

1.深度為m的滿二叉樹有2^m-1個結點.
因為滿二叉樹的定義為:一顆深度為k且有2^k-1個結點的二叉樹稱為滿二叉樹.
2.若要樹深為最小,顯然要使除最後一層外的每一層都有盡可能多的結點,即要二叉樹為完全二叉樹.

由二叉樹的一個重要性質:具有n個結點的完全二叉樹的深度為[log2n]+1.(這是在根節點層次為1時,若為0,將+1去掉即可)
log2n是以2為底n的對數
[log2n]為不大於log2n的最大整數

可知,含有100個(根)結點的二叉樹,(應該沒"根"字吧)
可能的最小樹深為[log2 100 ]+1
二叉樹根結點的層次為0時,可能的最小樹深為[log2 100 ]
即為6.

可以這樣計算:確定最小樹深當且僅當二叉樹為完全二叉樹時出現,設深度為k,(此時設二叉樹根結點的層次為0)有:
2^0+2^1+2^2+...+2^(k-1)<100=<2^0+2^1+...+2^k
即2^k-1<100=<2^(k+1)-1
或2^k=<100<2^(k+1) (上下兩式是相等的)
其中2^k為完全二叉樹的第k層的最多結點個數
解得k=<log2 100<k+1
即k=[log2 100]=6

⑹ 二叉樹計算節點

二叉樹計算節點方法：
(1)在二叉樹的第k 層上，最多有2k-1(k≥1)個結點，
(2)深度為m的二叉樹最多有2m-1 個結點，
(3)度為0 的結點(即葉子結點)總是比度為2 的結點多一個，
(4)具有n 個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n] 表示取log2n 的整數部分，
(5)具有n 個結點的完全二叉樹的深度為[log2n]+1，
(6)設完全二叉樹共有n 個結點。如果從根結點開始，按層序(每 一層從左到右)用自然數1，2，….n 給結點進行編號(k=1,2….n)， 有以下結論:
①若k=1，則該結點為根結點，它沒有父結點;若k>1，則該結點的 父結點編號為INT(k/2);
②若2k≤n，則編號為k 的結點的左子結點編號為2k;否則該結點 無左子結點(也無右子結點);
③若2k+1≤n，則編號為k 的結點的右子結點編號為2k+1;否則該 結點無右子結點。

⑺ 二叉樹結點的計算方法

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

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

⑻ 怎麼樣才能算出一個樹或二叉樹有多少個結點

如果用程序來實現的話，我覺得應該遍歷這個樹。
首先設置一個計數器，每訪問一個節點，就把計數器加1，最後察看你計數器的值，也就知道有多少個節點了；
如果是2叉樹，可以採用先序，中序或後序遍歷的方法。
如果是普通樹，可以採用廣度優先搜索或深度優先搜索的方法來遍歷這個樹。

⑼ 二叉樹的葉子節點數如何計算

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

計算公式：n0=n2+1

n0 是葉子節點的個數

n2 是度為2的結點的個數

n0=n2+1=5+1=6

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

(9)小樹截點計算方法擴展閱讀

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

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

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

在二叉樹中：

n0=n2+1；

N=n0+n1+n2

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

⑽ 葉子節點數計算公式是什麼

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

計算公式：n0=n2+1

n0 是葉子節點的個數

n2 是度為2的結點的個數

n0=n2+1=5+1=6

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

(10)小樹截點計算方法擴展閱讀：

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

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

在二叉樹中：

n0=n2+1；

N=n0+n1+n2