計算二叉樹高度演算法

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

(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)。

(1)計算二叉樹高度演算法擴展閱讀：

類型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ⅱ 以二叉鏈表作存儲結構,試編寫求二叉樹高度的演算法

主方法調用RootFirst(&root,0);即可，g_nMax 即為最終的樹的高度。
int g_nMax = 0;
voild RootFirst(TreeNode *p,int nLevel)
{
if (null == p->left && null == p->right) //當前為葉子節點
{
if (g_nMax < nLevel)
{
g_nMax = nLevel;
return;
}
}
if(null != p->left )
{
RootFirst(p->left,nLevel+1);//遍歷左子樹
}
if(null != p->right)
{
RootFirst(p->right,nLevel+1);//遍歷右子樹
}
}

Ⅲ 什麼是二叉樹如何計算二叉樹的高度

看左子樹高還是右子樹高，高的那個的高度加一就是整個二叉樹的高度了。利用這個關系，搞個遞歸就出來了。

Ⅳ 求二叉樹的高度

公式:V0=(V2)
+2(
V3)+3
(V4)....(k-1)(Vk)+1
所有的樹都滿足這個公式，其中v0...vk代表
度為0...K的節點個數。
所有計算度與節點個數的問題無論是幾叉樹的都必須用這個式子，我建議樓主哥哥記住!
葉子節點就是度為0的節點V0，其他的分支節點度都為m那麼就只存在度為0和度為m的節點
代入上面公式:
V0=(m-1)Vm+1
又因為:
Vm+V0=n
//因為樹總共n個節點
解這個方程組，就得
V0=((m-1)n+1)/m
用計算機計算
，你可以將它理解成一個層序遍歷的過程，使用隊列來遍歷:
存儲結構是
typedef
struct
Node
{
int
data;
struct
node
*FirstChild;
struct
node
*NextBrother;
}*Tree;
static
int
leafnum;
//全局函數用於計數葉子節點
void
BFSCount(Tree
t)
{
int
i=0;
SeqQueue
*Q;
TreeNode
*p;
InitQueue(Q);
if(t==NULL)
return;
EnterQueue(Q,t);
While(!Empty(Q))
{
DeleteQueue(Q,p);
//出隊
然後判斷這個節點
if(p->FirstChild==NULL)
leafnum++;
//如果這個節點一個孩子也沒有，則是葉子，計數+1
else{
p=t->FirstChild;
//否則開始將它第一個孩子繼續進入隊
EnterQueue(Q,p);
while(i<=m)
//把第一個孩子的下一個兄弟依次入隊
{
p=p->NextBrother;
EnterQueue(Q,p);
}
}
}
}

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

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

Int Depth(BinTree *T){int dep1,dep2;

if(T==Null) return(0);

else{dep1=Depth(T->lchild);

dep2=Depth(T->rchild);

if(dep1>dep2) return(dep1+1);

else return(dep2+1);}

樹的寬度：按層遍歷二叉樹，採用一個隊列q，讓根結點入隊列，最後出隊列，若有左右子樹，則左右子樹根結點入隊列，如此反復，直到隊列為空。

int Width(BinTree *T){intfront=-1,rear=-1;

/*隊列初始化*／int flag=0,count=0,p;

/* pint CountNode (BTNode *t)

//節點總數{int num;if (t == NULL)num = 0;

elsenum = 1 + CountNode (t->lch) + CountNode (t->rch);

return (num);}void CountLeaf (BTNode *t)

//葉子節點總數{if (t != NULL){if (t->lch == NULL && t->rch == NULL)count ++;

// 全局變數CountLeaf (t->lch);CountLeaf (t->rch);}}。

(6)計算二叉樹高度演算法擴展閱讀

方法：

求二叉樹的高度的演算法基於對二叉樹的三種遍歷，可以用後序遍歷的演算法加上記錄現在的高度和已知的最高的葉子的高度，當找到一個比已知高度還要高的葉子，刷新最高高度。

最後遍歷下來就是樹的高度，至於後序遍歷的演算法，是一本數據結構或者演算法的書中都有介紹和參考代碼

Ⅶ 設計演算法統計二叉樹高度

#include<stdio.h>
#include<malloc.h>
typedef struct binode{
int data;
struct binode *lchild,*rchild;
}binode,*bitree;
typedef struct{
bitree elem[100];
int top;
}stack;
bitree creat_bt(){ //按擴展前序建二叉樹
bitree t;int x;
scanf("%d",&x);
if (x==0) t=NULL;
else { t=(bitree)malloc(sizeof(binode));
t->data=x;
t->lchild=creat_bt();
t->rchild=creat_bt();
}
return t;
}
void exchange(bitree t) //左、右子樹交換
{bitree p;
if(t!=NULL)
{ p=t->lchild;t->lchild=t->rchild;
t->rchild=p;
exchange(t->lchild);
exchange(t->rchild);
}
}
void inorder(bitree bt) //遞歸的中序遍歷
{ if (bt){
inorder(bt->lchild);
printf("% d",bt->data);
inorder(bt->rchild);
}
}
main()
{bitree root;
printf("\n");
printf("建二叉樹，輸入元素：");
root=creat_bt(); /*create tree of useing preorder*/
printf("交換前的中序序列是：");
inorder(root);
exchange(root);
printf("\n交換後的中序序列是：");
inorder(root);
printf("\n");
}

Ⅷ 求二叉樹高度的原理、演算法是什麼，越詳細越好，C語言，謝謝

首先分析二叉樹的深度（高度）和它的左、右子樹深度之間的關系。從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，演算法中「訪問結點」的操作為：求得左、右子樹深度的最大值，然後加
1
。
int
Depth
(BiTree
T
){
//
返回二叉樹的深度
if
(
!T
)
depthval
=
0;
else
{
depthLeft
=
Depth(
T->lchild
);
depthRight=
Depth(
T->rchild
);
depthval
=
1
+
(depthLeft
>
depthRight
?
depthLeft
:
depthRight);
}
return
depthval;
}

Ⅸ 二叉樹演算法

二叉樹是沒有度為1的結點。
完全二叉樹定義：
若設二叉樹的高度為h，除第
h
層外，其它各層
(1～h-1)
的結點數都達到最大個數，第
h
層從右向左連續缺若干結點，這就是完全二叉樹。
完全二叉樹葉子結點的演算法：
如果一棵具有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

Ⅹ 如何用非遞歸演算法求二叉樹的高度

if（T＝＝null）

return0；

intfront＝－1，

rear＝－1；

／／front出隊指針

rear入隊指針intlast＝0，

level＝0；

／／last每一層的最右指針

（front＝＝last時候一層遍歷結束level＋＋）BiTreeQ［Maxsize］；

／／模擬隊列Q［＋＋rear］＝T；

BiTreep；

while(front<rear){

p＝Q［＋＋front］；／／開始出隊

因為front要趕到lash

實現level＋＋

if(p->lchild)

Q[++rear] = p->lchild;

if(p->rchild)

Q[++rear] = p->rchild;

if（front＝＝last）｛

level＋＋；

last＝rear；／／last指向下層節點｝

｝

(10)計算二叉樹高度演算法擴展閱讀

非遞歸演算法思想：

（1）設置一個棧S存放所經過的根結點（指針）信息；初始化S；

（2）第一次訪問到根結點並不訪問，而是入棧；

（3）中序遍歷它的左子樹，左子樹遍歷結束後，第二次遇到根結點，就將根結點（指針）退棧，並且訪問根結點；然後中序遍歷它的右子樹。

（4）當需要退棧時，如果棧為空則結束。