二叉樹的高度怎么算 如何用非遞歸算法求二叉樹的高度

以二叉鏈表為存儲結(jié)構(gòu),寫出求二叉樹高度和寬度的算法，求二叉樹高度，以二叉樹鏈表作為二叉樹的存儲結(jié)構(gòu)，怎么編寫算法計(jì)算返回二叉樹的高度？如何用非遞歸算法求二叉樹的高度？

本文導(dǎo)航

• 以二叉鏈表為存儲結(jié)構(gòu),寫出求二叉樹高度和寬度的算法
• 求二叉樹高度
• 以二叉樹鏈表作為二叉樹的存儲結(jié)構(gòu)，怎么編寫算法計(jì)算返回二叉樹的高度？
• 如何用非遞歸算法求二叉樹的高度

以二叉鏈表為存儲結(jié)構(gòu),寫出求二叉樹高度和寬度的算法

原題：

以二叉鏈表為存儲結(jié)構(gòu)，分別寫出求二叉樹高度及寬度的算法。所謂寬度是指在二叉樹的各層上，具有結(jié)點(diǎn)數(shù)最多的那一層上的結(jié)點(diǎn)總數(shù)。

標(biāo)準(zhǔn)答案：

①求樹的高度

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

}

②求樹的寬度

思想：按層遍歷二叉樹，采用一個(gè)隊(duì)列q，讓根結(jié)點(diǎn)入隊(duì)列，最后出隊(duì)列，若有左右子樹，則左右子樹根結(jié)點(diǎn)入隊(duì)列，如此反復(fù)，直到隊(duì)列為空。

int Width(BinTree *T)

{

int

front=-1,rear=-1;/*

隊(duì)列初始化*／

int flag=0,count=0,p;

/* p用于指向樹中層的最右邊的結(jié)點(diǎn)，標(biāo)志flag記錄層中結(jié)點(diǎn)數(shù)的最大值。*／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)

/* 當(dāng)前層已遍歷完畢*/

{

if(flag<count)

flag=count;

count=0;

p=rear; /* p指向下一層最右邊的結(jié)點(diǎn)*/

}

}

/* endwhile*/

return(flag);

}

求二叉樹高度

公式：V0=（V2） +2（ V3）+3 （V4）....(k-1)（Vk）+1 所有的樹都滿足這個(gè)公式，其中v0...vk代表 度為0...K的節(jié)點(diǎn)個(gè)數(shù)。

所有計(jì)算度與節(jié)點(diǎn)個(gè)數(shù)的問題無論是幾叉樹的都必須用這個(gè)式子，我建議樓主哥哥記?。?/p>

葉子節(jié)點(diǎn)就是度為0的節(jié)點(diǎn)V0，其他的分支節(jié)點(diǎn)度都為m那么就只存在度為0和度為m的節(jié)點(diǎn)

代入上面公式：

V0=(m-1)Vm+1

又因?yàn)椋?/p>

Vm+V0=n //因?yàn)闃淇偣瞡個(gè)節(jié)點(diǎn)

解這個(gè)方程組，就得 V0=((m-1)n+1)/m

用計(jì)算機(jī)計(jì)算 ，你可以將它理解成一個(gè)層序遍歷的過程，使用隊(duì)列來遍歷：

存儲結(jié)構(gòu)是

typedef struct Node

{

int data;

struct node *FirstChild;

struct node *NextBrother;

}*Tree;

static int leafnum; //全局函數(shù)用于計(jì)數(shù)葉子節(jié)點(diǎn)

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); //出隊(duì) 然后判斷這個(gè)節(jié)點(diǎn)

if(p->FirstChild==NULL) leafnum++; //如果這個(gè)節(jié)點(diǎn)一個(gè)孩子也沒有，則是葉子，計(jì)數(shù)+1

else{

p=t->FirstChild; //否則開始將它第一個(gè)孩子繼續(xù)進(jìn)入隊(duì)

EnterQueue(Q,p);

while(i<=m) //把第一個(gè)孩子的下一個(gè)兄弟依次入隊(duì)

{

p=p->NextBrother;

EnterQueue(Q,p);

}

}

}

}

以二叉樹鏈表作為二叉樹的存儲結(jié)構(gòu)，怎么編寫算法計(jì)算返回二叉樹的高度？

編寫方法如下：

高度其實(shí)也叫深度，我通俗點(diǎn)說就是 比如根節(jié)點(diǎn) 是第一層，根節(jié)點(diǎn)的左右孩子為第二層，然后根節(jié)點(diǎn)的左右孩子各自的孩子為第三層.....那么二叉樹的高度就是這棵樹最大的層數(shù)。這么說不知道樓主明白了沒有，舉例就是：如果只有一個(gè)根節(jié)點(diǎn)，那么高度就是1，如果有一個(gè)根節(jié)點(diǎn)再加上根節(jié)點(diǎn)的兩個(gè)孩子，或者其中一個(gè)孩子，那么高度就是2；

那根據(jù)這樣 如果用遞歸的思想，算法就比較好寫了，就是統(tǒng)計(jì)一下根節(jié)點(diǎn)的左右孩子的高對唄，看哪個(gè)的高度更大那二叉樹高度就是哪個(gè)。

具體代碼如下：

#include<stdio.h>

#include<stdlib.h> ; ; ; ; //頭文件就不用說了吧

typedef struct Node{

char data;

struct Node* lchild;

struct Node* rchild;

}Node,*Tree; ; ; ; ; ; ;//二叉樹的定義也不用多說吧那個(gè)data的數(shù)據(jù)類型char可以任意換是吧

int max(int m, int n)

{

if (m > n)

return m;

else

return n;

} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; //這個(gè)我想能夠看明白 求兩個(gè)數(shù)最大值，為什么要求最大值上面也說了

int TreeHeight(Node *root)

{

if (root == NULL)

return 0; ; ; ; ; ; ; ; ;//如果根節(jié)點(diǎn)都沒有 那高度肯定就是0了 是吧

else

return 1 + max(TreeHeight(root->lchild), TreeHeight(root->rchild));

} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;//否則遞歸計(jì)算他的左右孩子的高度然后在加上根節(jié)點(diǎn)的層數(shù)1 對吧

int height(Node *t) ; ; ; ; ;//第二個(gè)算法（其實(shí)和第一個(gè)一樣）

{

if(t==NULL)

return 0;

else

{

int m=height(t->lchild);

int n=height(t->rchild); ; ; ; ; //遞歸計(jì)算該節(jié)點(diǎn)的左右孩子的高度

return(m>n)?m+1:n+1; ; ; ; ;//只不過這里沒有用到上面求最大值的那個(gè)函數(shù)，樓主應(yīng)該學(xué)過C

} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;//吧，這就是個(gè)逗號表達(dá)式，判斷？A：B ;判斷滿足就返回A不滿

} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;//足就返回B 那這句換還是一樣就是求m和n的最大值然后加1返 回

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

如果是結(jié)點(diǎn)的定義中有深度這個(gè)屬性，那么用一個(gè)隊(duì)列就可以了。

隊(duì)首放節(jié)點(diǎn)

隊(duì)尾取出節(jié)點(diǎn)

比如:根節(jié)點(diǎn)放入隊(duì)列

(開始只有這個(gè)一個(gè)節(jié)點(diǎn)在隊(duì)列中)

然后呢

從隊(duì)尾取出這個(gè)根節(jié)點(diǎn)

然后打散

把他的左右孩子放入對首(這時(shí)候有2個(gè)節(jié)點(diǎn)

也就是二叉樹的第二層)

之后從隊(duì)伍里取出這2個(gè)節(jié)點(diǎn)

打散

之后隊(duì)伍里應(yīng)該是

二叉樹第三層的4個(gè)節(jié)點(diǎn)

。。。。。

這樣就把二叉樹層次遍歷了

因?yàn)橛行┕?jié)點(diǎn)沒有孩子節(jié)點(diǎn)

也就是葉子

這個(gè)隊(duì)列中的節(jié)點(diǎn)

逐漸會越來越少

最后一個(gè)取出隊(duì)列的節(jié)點(diǎn)

的深度也就是二叉樹的高度

如果結(jié)點(diǎn)定義沒有深度，我寫了一個(gè)方法，請樓主參考。

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;

}

其實(shí)思路和剛才說的是大同小異的，用一個(gè)level來記錄二叉樹的層次，最底的層次就是他的高度。

每一層都存在單獨(dú)的list里，這些list再存在一個(gè)arraylist里，這樣很容易就能知道每一層有哪些結(jié)點(diǎn)，如果這些結(jié)點(diǎn)有孩子，就把level++，直到某一層沒有任何結(jié)點(diǎn)有孩子，這時(shí)候level就是最后一層了。