求樹高演算法
⑴ 如何用非遞歸演算法求二叉樹的高度
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指向下層節點｝
｝
(1)求樹高演算法擴展閱讀
非遞歸演算法思想：
（1）設置一個棧S存放所經過的根結點（指針）信息；初始化S；
（2）第一次訪問到根結點並不訪問，而是入棧；
（3）中序遍歷它的左子樹，左子樹遍歷結束後，第二次遇到根結點，就將根結點（指針）退棧，並且訪問根結點；然後中序遍歷它的右子樹。
（4）當需要退棧時，如果棧為空則結束。
⑵ 求二叉樹高度的原理、演算法是什麼，越詳細越好，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。
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);}}。
(3)求樹高演算法擴展閱讀
方法：
求二叉樹的高度的演算法基於對二叉樹的三種遍歷，可以用後序遍歷的演算法加上記錄現在的高度和已知的最高的葉子的高度，當找到一個比已知高度還要高的葉子，刷新最高高度。
最後遍歷下來就是樹的高度，至於後序遍歷的演算法，是一本數據結構或者演算法的書中都有介紹和參考代碼
⑷ 設樹採用孩子兄弟表示法存放，用類C語言設計演算法計算樹的高度。
採用遞歸求解，先求左子樹的高度和右子樹的高度，然後整棵樹的高度就是兩顆子樹高度的最大值+1。假定葉子節點高度為0。代碼如下：
structnode{
intval;
structnode*left;
structnode*right;
};
intheight(structnode*root)
{
inth,lh,rh;
if(root==NULL)
return-1;//這里返回-1表示葉子節點的高度為0，若規定葉子節點的高度為1，這里返回0即可
lh=height(root->left);
rh=height(root->right);
if(lh>rh)
h=lh+1;
else
h=rh+1;
returnh;
}
⑸ 二叉樹的深度演算法怎麼算啊
二叉樹的深度演算法：
一、遞歸實現基本思想：
為了求得樹的深度，可以先求左右子樹的深度，取二者較大者加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
}
⑹ 設計演算法統計二叉樹高度
#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");
}
⑺ 二叉樹求高度，用棧模擬遞歸.怎麼實現
計算二叉樹的高度可以採用幾種不同的演算法。 演算法一：採用後序遍歷二叉樹，結點最大棧長即為二叉樹的高度； 演算法二：層次遍歷二叉樹，最大層次即為二叉樹的高度； 演算法三：採用遞歸演算法，求二叉樹的高度。
⑻ 怎麼計算二叉樹高度
分析二叉樹的深度（高度）和它的左、右子樹深度之間的關系。從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加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;
}
(8)求樹高演算法擴展閱讀：
一棵深度為k，且有2^k-1個結點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的結點數都是最大結點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且或者最後一層是滿的，或者是在右邊缺少連續若干結點，則此二叉樹為完全二叉樹。具有n個結點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個葉子結點，至多有2k-1個結點。
二叉樹的深度是從根節點開始（其深度為1）自頂向下逐層累加的；而二叉樹高度是從葉節點開始（其高度為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);
}
}
⑽ 以二叉鏈表作存儲結構,試編寫求二叉樹高度的演算法
主方法調用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);//遍歷右子樹
}
}