鏈式存儲二叉樹求高度
主方法調用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);//遍歷右子樹
}
}
❷ C程序，求二叉樹的樹高
#include "stdio.h"
#include "malloc.h"
#include "math.h"
#include "string.h"
#define MAX 100
void exit(int);
/*--------------------*/
int count; /* 記錄二叉樹中的二度結點的個數 */
int flag; /* 標明二叉樹是否為AVL樹 */
/*--------------------*/
typedef struct node{
char d;
struct node *lchild,*rchild;
}TNode;
/*-----通過中序序列和後序序列建樹-----*/
void MkTree(char in[],int is,int ie,char post[],int posts,int poste,TNode **r)
{
int i;
if(is>ie || posts>poste)
*r=NULL;
else{
*r=malloc(sizeof(TNode));
(*r)->d=post[poste];
for(i=is;i<=ie;i++)
if(post[poste]==in){
MkTree(in,is,i-1,post,posts,posts+i-is-1,&(*r)->lchild);
MkTree(in,i+1,ie,post,posts+i-is,poste-1,&(*r)->rchild);
break;
}
if(i>ie){
printf("error:input contains an error!\n");
exit(9);
}
}
}
/*-----前序遍歷二叉樹-----*/
void preorder(TNode *r)
{
if(r){
printf("%c",r->d);
preorder(r->lchild);
preorder(r->rchild);
}
}
/*-----求二叉樹中二度結點的個數-----*/
void BNode(TNode *r)
{
if(r){
if(r->lchild&&r->rchild)
count++;
BNode(r->lchild);
BNode(r->rchild);
}
}
/*-----求二叉樹中葉子的個數-----*/
int leaf(TNode *r)
{
if(r==NULL)
return 0;
else
if(r->lchild==NULL && r->rchild==NULL)
return 1;
else
return leaf(r->lchild) + leaf(r->rchild);
}
/*-----求二叉樹中葉子的高度-----*/
int Height(TNode *r)
{
int h1,h2;
if(r==NULL)
return 0;
else{
h1=Height(r->lchild);
h2=Height(r->rchild);
if(abs(h1-h2)>1)
flag=1;
return 1+(h1>h2?h1:h2);
}
}
void main()
{
TNode *r;
int height;
char post[MAX],in[MAX];
printf("Input inorder and postorder :\n");
gets(in);
gets(post);
MkTree(in,0,strlen(in)-1,post,0,strlen(post)-1,&r);
printf("The preorder is as follows:\n");
preorder(r);
printf("\nThere are %dletters in the tree.\n",leaf(r));
count=0;
BNode(r);
printf("\nThere are %d binarynode in the tree.\n",count);
flag=0;
height=Height(r);
printf("\nThe height of the tree is %d\n",height);
if(flag==1)
printf("\nThis bintree is not an AVL!\n");
else
printf("\nThis bintree is an AVL!\n");
}
❸ 設一棵二叉樹以二叉鏈表為存儲結構，結點結構為（lchild,data,rchild），設計一個演算法求二叉樹的高度
typedef struct node
{
char data
struct node *lchild;
struct node *rchild;
} Node;
int max(int m, int n)
{
if (m > n)
return m;
else
return n;
}
// 獲取二叉樹的高度
int TreeHeight(Node *root)
{
if (root == NULL)
return 0;
else
return 1 + max(TreeHeight(root->lchild), TreeHeight(root->rchild));
}
❹ 以二叉鏈表為存儲結構,寫程序求出二叉樹的高度，寬度,結點總數,葉子結點總數
int CountNode (BTNode *t) //節點總數 { int num; if (t == NULL) num = 0; else num = 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); } }
❺ 以二叉樹鏈表作為二叉樹的存儲結構，怎麼編寫演算法計算返回二叉樹的高度
編寫方法如下：
❻ 假設二叉樹採用鏈式方法存儲,編寫一個計算一棵二叉樹t的高度的函數
#include "stdio.h"
#include "stdlib.h"
int BiTreeDepth(BiTree T)
{ int h1,h2,h;
if (T==NULL)
return 0;
else
{ h1=BiTreeDepth(T->lchild);
h2=BiTreeDepth(T->rchild);
if (h1>h2)
h=h1+1;
else
h=h2+1;
}
return h;
}
❼ 怎麼計算二叉樹高度
分析二叉樹的深度（高度）和它的左、右子樹深度之間的關系。從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加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;
}
(7)鏈式存儲二叉樹求高度擴展閱讀：
一棵深度為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);
}
}
❾ 以二叉樹鏈表作為二叉樹的存儲結構，編寫演算法計算返回二叉樹的高度
樓主看樣子是才學數據結構吧...我以前學過，忘很多了，看這么高的分，我就順便復習一下吧；
首先理解一下什麼是高度：高度其實也叫深度，我通俗點說就是 比如根節點 是第一層，根節點的左右孩子為第二層，然後根節點的左右孩子各自的孩子為第三層.....那麼二叉樹的高度就是這棵樹最大的層數。這么說不知道樓主明白了沒有，舉例就是：如果只有一個根節點，那麼高度就是1，如果有一個根節點再加上根節點的兩個孩子，或者其中一個孩子，那麼高度就是2；
那根據這樣 如果用遞歸的思想，我想演算法就比較好寫了，就是統計一下根節點的左右孩子的高對唄，看哪個的高度更大那二叉樹高度就是那個唄。下面我粘貼出網上的兩個演算法（我沒去運行試過，錯了別怪我）順便解釋一下：
#include<stdio.h>
#include<stdlib.h> //頭文件就不用說了吧
typedef struct Node{
char data;
struct Node* lchild;
struct Node* rchild;
}Node,*Tree; //二叉樹的定義也不用多說吧那個data的數據類型char可以任意換是吧
int max(int m, int n)
{
if (m > n)
return m;
else
return n;
} //這個我想能夠看明白 求兩個數最大值，為什麼要求最大值上面也說了
int TreeHeight(Node *root)
{
if (root == NULL)
return 0; //如果根節點都沒有 那高度肯定就是0了 是吧
else
return 1 + max(TreeHeight(root->lchild), TreeHeight(root->rchild));
} //否則遞歸計算他的左右孩子的高度然後在加上根節點的層數1 對吧
int height(Node *t) //第二個演算法（其實和第一個一樣）
{
if(t==NULL)
return 0;
else
{
int m=height(t->lchild);
int n=height(t->rchild); //遞歸計算該節點的左右孩子的高度
return(m>n)?m+1:n+1; //只不過這里沒有用到上面求最大值的那個函數，樓主應該學過C
} //吧，這就是個逗號表達式，判斷？A：B 判斷滿足就返回A不滿
} //足就返回B 那這句換還是一樣就是求m和n的最大值然後加1返 回
大概就這么個意思，如果程序沒通過，樓主可以試著按這個想法稍微改改。
分能給我么？
❿ 以二叉鏈表為存儲結構,寫出求二叉樹高度和寬度的演算法
樹的高度：對非空二叉樹，其深度等於左子樹的最大深度加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);}}。
(10)鏈式存儲二叉樹求高度擴展閱讀
方法：
求二叉樹的高度的演算法基於對二叉樹的三種遍歷，可以用後序遍歷的演算法加上記錄現在的高度和已知的最高的葉子的高度，當找到一個比已知高度還要高的葉子，刷新最高高度。
最後遍歷下來就是樹的高度，至於後序遍歷的演算法，是一本數據結構或者演算法的書中都有介紹和參考代碼