二叉樹的高度怎么算 如何用非遞歸算法求二叉樹的高度
以二叉鏈表為存儲結構,寫出求二叉樹高度和寬度的算法，求二叉樹高度，以二叉樹鏈表作為二叉樹的存儲結構，怎么編寫算法計算返回二叉樹的高度？如何用非遞歸算法求二叉樹的高度？
本文導航
以二叉鏈表為存儲結構,寫出求二叉樹高度和寬度的算法
原題：
以二叉鏈表為存儲結構，分別寫出求二叉樹高度及寬度的算法。所謂寬度是指在二叉樹的各層上，具有結點數最多的那一層上的結點總數。
標準答案：
①求樹的高度
思想：對非空二叉樹，其深度等于左子樹的最大深度加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)
{
int
front=-1,rear=-1;/*
隊列初始化*／
int flag=0,count=0,p;
/* p用于指向樹中層的最右邊的結點，標志flag記錄層中結點數的最大值。*／if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front<p)
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/* 當前層已遍歷完畢*/
{
if(flag<count)
flag=count;
count=0;
p=rear; /* p指向下一層最右邊的結點*/
}
}
/* endwhile*/
return(flag);
}
求二叉樹高度
公式：V0=（V2） +2（ V3）+3 （V4）....(k-1)（Vk）+1 所有的樹都滿足這個公式，其中v0...vk代表 度為0...K的節(jié)點個數。
所有計算度與節(jié)點個數的問題無論是幾叉樹的都必須用這個式子，我建議樓主哥哥記?。?/p>
葉子節(jié)點就是度為0的節(jié)點V0，其他的分支節(jié)點度都為m那么就只存在度為0和度為m的節(jié)點
代入上面公式：
V0=(m-1)Vm+1
又因為：
Vm+V0=n //因為樹總共n個節(jié)點
解這個方程組，就得 V0=((m-1)n+1)/m
用計算機計算 ，你可以將它理解成一個層序遍歷的過程，使用隊列來遍歷：
存儲結構是
typedef struct Node
{
int data;
struct node *FirstChild;
struct node *NextBrother;
}*Tree;
static int leafnum; //全局函數用于計數葉子節(jié)點
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); //出隊 然后判斷這個節(jié)點
if(p->FirstChild==NULL) leafnum++; //如果這個節(jié)點一個孩子也沒有，則是葉子，計數+1
else{
p=t->FirstChild; //否則開始將它第一個孩子繼續(xù)進入隊
EnterQueue(Q,p);
while(i<=m) //把第一個孩子的下一個兄弟依次入隊
{
p=p->NextBrother;
EnterQueue(Q,p);
}
}
}
}
以二叉樹鏈表作為二叉樹的存儲結構，怎么編寫算法計算返回二叉樹的高度？
編寫方法如下：
高度其實也叫深度，我通俗點說就是 比如根節(jié)點 是第一層，根節(jié)點的左右孩子為第二層，然后根節(jié)點的左右孩子各自的孩子為第三層.....那么二叉樹的高度就是這棵樹最大的層數。這么說不知道樓主明白了沒有，舉例就是：如果只有一個根節(jié)點，那么高度就是1，如果有一個根節(jié)點再加上根節(jié)點的兩個孩子，或者其中一個孩子，那么高度就是2；
那根據這樣 如果用遞歸的思想，算法就比較好寫了，就是統(tǒng)計一下根節(jié)點的左右孩子的高對唄，看哪個的高度更大那二叉樹高度就是哪個。
具體代碼如下：
#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; ; ; ; ; ; ; ; ;//如果根節(jié)點都沒有 那高度肯定就是0了 是吧
else
return 1 + max(TreeHeight(root->lchild), TreeHeight(root->rchild));
} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;//否則遞歸計算他的左右孩子的高度然后在加上根節(jié)點的層數1 對吧
int height(Node *t) ; ; ; ; ;//第二個算法（其實和第一個一樣）
{
if(t==NULL)
return 0;
else
{
int m=height(t->lchild);
int n=height(t->rchild); ; ; ; ; //遞歸計算該節(jié)點的左右孩子的高度
return(m>n)?m+1:n+1; ; ; ; ;//只不過這里沒有用到上面求最大值的那個函數，樓主應該學過C
} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;//吧，這就是個逗號表達式，判斷？A：B ;判斷滿足就返回A不滿
} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;//足就返回B 那這句換還是一樣就是求m和n的最大值然后加1返 回
如何用非遞歸算法求二叉樹的高度
如果是結點的定義中有深度這個屬性，那么用一個隊列就可以了。
隊首放節(jié)點
隊尾取出節(jié)點
比如:根節(jié)點放入隊列
(開始只有這個一個節(jié)點在隊列中)
然后呢
從隊尾取出這個根節(jié)點
然后打散
把他的左右孩子放入對首(這時候有2個節(jié)點
也就是二叉樹的第二層)
之后從隊伍里取出這2個節(jié)點
打散
之后隊伍里應該是
二叉樹第三層的4個節(jié)點
。。。。。
這樣就把二叉樹層次遍歷了
因為有些節(jié)點沒有孩子節(jié)點
也就是葉子
這個隊列中的節(jié)點
逐漸會越來越少
最后一個取出隊列的節(jié)點
的深度也就是二叉樹的高度
如果結點定義沒有深度，我寫了一個方法，請樓主參考。
public
static
int
findlevel(BinaryNode
root)
{
ArrayList<LinkedList<BinaryNode>>
result=new
ArrayList<LinkedList<BinaryNode>>();
LinkedList<BinaryNode>
list=new
LinkedList<BinaryNode>();
list.add(root);
result.add(list);
int
level=0;
while(true)
{
list=new
LinkedList<BinaryNode>();
for(int
i=0;i<result.get(level).size();i++)
{
BinaryNode
tmp=result.get(level).get(i);
if(tmp.left!=null)
list.add(tmp.left);
if(tmp.right!=null)
list.add(tmp.right);
}
if(list.size()>0)
result.add(list);
else
break;
level++;
}
return
level;
}
其實思路和剛才說的是大同小異的，用一個level來記錄二叉樹的層次，最底的層次就是他的高度。
每一層都存在單獨的list里，這些list再存在一個arraylist里，這樣很容易就能知道每一層有哪些結點，如果這些結點有孩子，就把level++，直到某一層沒有任何結點有孩子，這時候level就是最后一層了。
