計算二叉樹的高度演算法

1. 假設以二叉鏈表作為二叉樹的存儲結構，試編寫一個求樹的高度的演算法

#include<iostream.h>
#include<malloc.h>

#define FALSE 0
#define TRUE 1
#define OK 1
#define maxsize 100
typedef int status;
typedef int elemtype;

typedef struct binode
{
elemtype data;
struct binode *lchild,*rchild;
}binode,*bitree;

status treecreated=FALSE;
int leafcount=0;

status createbitree(bitree *t);
status preordertraverse(bitree t);
int height(bitree t);
void swap(bitree *t);
void leafcounts(bitree t);

void main()
{
int choice=0;
status leave=FALSE,flag;
binode *bt;
cout<<"===========二叉樹演示程序==============="<<endl;
do
{
cout<<"1：創建一個二叉樹，按先序遍歷結果輸入，空用0表示 "<<endl;
cout<<"2：先序遍歷二叉樹，遞歸方式遍歷二叉樹 "<<endl;
cout<<"3：求葉子數"<<endl;
cout<<"4：計算二叉樹的高度"<<endl;
cout<<"5: 樹進行左右翻轉"<<endl;
cout<<"0：退出"<<endl;
cout<<"-------請輸入你的選擇:"<<endl;
cin>>choice;
switch(choice)
{
case 1:
if(treecreated)
{
cout<<"sorry,the tree has been already created!"<<endl;
break;
};
cout<<"請輸入代表樹的數字："<<endl;
flag=createbitree(&bt);
if(flag==OK)
{
cout<<"你已經建立了一棵樹了！"<<endl;
treecreated=TRUE;
}
break;

case 2:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
cout<<"先序遍歷順序:"<<endl;
preordertraverse(bt);
cout<<endl;
break;

case 3:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
leafcounts(bt);
cout<<"樹的葉子數:"<<leafcount<<endl;
cout<<endl;
break;

case 4:
int h;
h=height(bt);
cout<<"樹的高度:"<<h<<endl;
break;

case 5:
swap(&bt);
cout<<"樹已經翻轉！！！"<<endl;
break;

case 0:
leave=TRUE;
break;
}
}while(!leave);
cout<<" 謝謝 再見了！！！"<<endl;
}
//遞歸方法實現創建
status createbitree(bitree *t)
{
int ch=0;
cin>>ch;
if(ch==0) //輸入如果是0表示是空
(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode)); //申請空間
(*t)->data=ch; //把數據傳給他
createbitree(&(*t)->lchild); //左孩子重新進入創建函數
createbitree(&(*t)->rchild); //右孩子重新進入創建函數
}
return OK;
}

//遞歸方法實現先序遍歷
status preordertraverse(bitree t)
{
if(t)
{
cout<<t->data<<" "; //先把頭結點輸出
preordertraverse(t->lchild); //然後是左結點
preordertraverse(t->rchild); //然後是右結點
return OK;
}
else
return OK;
}

int height(bitree t)
{
int hl,hr;
if(t==NULL)
return 0;
hl=height(t->lchild)+1; //最下面的左孩子加一
hr=height(t->rchild)+1; //最下面的右孩子加一
return (hl>hr?hl:hr); //比較誰大就取誰
}

void swap(bitree *t) //進行左右翻轉
{
bitree p;
if(*t!=NULL)
{
p=(*t)->lchild; //p為中間變數
(*t)->lchild=(*t)->rchild;
(*t)->rchild=p;
swap(&(*t)->lchild);
swap(&(*t)->rchild);
}
}

void leafcounts(bitree t) //求葉子數
{
if(t) //如果不為空
{
if(t->lchild==NULL && t->rchild==NULL)//左右孩子都為空 表明是葉子
leafcount++;
leafcounts(t->lchild);
leafcounts(t->rchild);
}
}

2. 求二叉樹高度的原理、演算法是什麼，越詳細越好，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;
}

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

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

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

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

5. 以二叉樹鏈表作為二叉樹的存儲結構，怎麼編寫演算法計算返回二叉樹的高度

編寫方法如下：

6. 二叉樹的高度計算和查找結點雙親

求高度的演算法：
int BTNodeHeight(BTNode *b)
{int lchildh,rchildh;
if(b==NULL)return 0;
else
{ lchild=BTNodeHeight(b->lchild);
rchild=BTNodeHeight(b->rchild);
return(lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
查找節點：
BTNode *FindNode(BTNode *b ,char x)
{BTNode *p;
if(b==NULL)
return NULL;
else if(b->data==x)
return b;
else
{p=FindNode(b->lchild,x);
if(p!=NULL)
return p;
else
return FindNode(b->rchild,x);
}
}

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

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指向下層節點｝

｝

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

非遞歸演算法思想：

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

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

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

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

8. 以二叉鏈表為存儲結構,寫出求二叉樹高度和寬度的演算法

樹的高度：對非空二叉樹，其深度等於左子樹的最大深度加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);}}。

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

方法：

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

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

9. 二叉樹求高度，用棧模擬遞歸.怎麼實現

計算二叉樹的高度可以採用幾種不同的演算法。 演算法一：採用後序遍歷二叉樹，結點最大棧長即為二叉樹的高度； 演算法二：層次遍歷二叉樹，最大層次即為二叉樹的高度； 演算法三：採用遞歸演算法，求二叉樹的高度。

10. 求二叉樹的高度

公式: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);
}
}
}
}