求二叉樹深度的演算法

⑴ 關於遞歸演算法求二叉樹深度演算法

u,v 分別求出當前節點左子樹和右子樹的深度（高度），
然後當前節點的 深度就等於左右子樹裡面較大的那個+1.

if (u>n) return (u+1)
return (v+1)
這句就是返回較深的+1.

u=height(T->lchild);
v=height(T->rchild);

這兩句就是遞歸的調用，求深度了。

if (T==NULL) return 0;

這個就是終止條件了，如果沒有子節點就返回。

⑵ 二叉樹深度的演算法

#include"stdio.h"
#include"alloc.h"
typedef
char
datatype;
typedef
struct
node
{
datatype
data;
struct
node
*lchild,
*rchild;
}
bitree;
int
k
=
1;
bitree
*Q[10];
bitree
*CREAT()
{
char
ch;
int
front,
rear;
bitree
*root,
*s;
root
=
NULL;
front
=
1;
rear
=
0;
printf("\n
=======二叉樹的建立和遍歷=======\n");
printf("
請輸入字元:
");
ch
=
getchar();
while
(ch
!=
'$')
{
s
=
NULL;
if
(ch
!=
'@')
{
s
=
malloc(sizeof(bitree));
s
->
data
=
ch;
s
->
lchild
=
NULL;
s
->
rchild
=
NULL;
}
rear++;
k
=
k++;
Q[rear]
=
s;
if
(rear
==
1)
root
=
s;
else
{
if
(s
&&
Q[front])
if
(rear
%
2
==
0)
Q[front]
->
lchild
=
s;
else
Q[front]
->
rchild
=
s;
if
(rear
%
2
==
1)
front++;
}
ch
=
getchar();
}
return
root;
}
int
COUNTER(t)
bitree
*t;
{
if
(t
==
NULL)
return
0;
else
if
(t->lchild
!=
NULL
&&
t->rchild
==
NULL
||
t->lchild
==
NULL
&&
t->rchild
!=
NULL)
return
1;
else
return
COUNTER(t->lchild)
+
COUNTER(t->rchild);
}
main()
{
int
i;
bitree
*p;
p
=
CREAT();
printf("
建立的二叉樹為:
");
for
(i
=
0;
i
<
k;
i++)
{
printf("%c
",
Q[i]
->
data);
}
printf("\n
度為1的節點數為:
");
printf("%d
",
COUNTER(p));
}
這是二叉樹的建立
遍歷
加二叉樹的度為1的結點的演算法

⑶ 關於求二叉樹深度的遞歸演算法

關於遞歸，你可以看成是一句一句往下運行嘛。需要保存狀態的時候，系統就會自動用棧幫你保存。就依你說得那個為例：
n為全局變數，初值為0；

第一次調用height(T)，假設T！=NULL
由於T!=NULL：跳過if (T==NULL) return 0;

關鍵到了u=height(T->lchild); 調用本身的函數：此時的T->lchild保存在棧中，既然是調用就得從函數開頭執行：
看下這時候T2（其實就是T->lchild），if (T==NULL) return 0；
這里假設T不是NULL，就繼續運行在遇到u=height(T->lchild); 在調這個函數本身——
這里就假設它為T->lchild==NULL吧。這下可好，這個函數執行return 0；

慢著：第二次函數調用u=height(T->lchild)中的函數值已經計算出來啦。這時u=0；

你還記得第二次調用運行到了v=height(T->rchild); 這句話吧？好，這個過程就和u=height(T->lchild)完全一樣。
這里也假設得到的v=0

則第二次調用到了if (u>n) return (u+1)
return (v+1)
得到一個返回值，不如就假設u〉n，於是返回值1；
好，這一波完畢；

你還記得第一次調用的height吧，這時把返回值給u,u=1；
然後執行到第一次調用中的v=height(T->rchild); 了。分析同上。

這個過程的確比較復雜。慢慢琢磨吧。呵呵。

⑷ 設計演算法求二叉樹的深度

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
char data;
struct node *left,*right;
}Node,*PNode;
PNode createBtree(PNode root)//創建二叉樹，控制台下輸入，基於先序遍歷輸入
{
char data;
scanf("%c",&data);
if (data==' ')
{
root=NULL;
return root;
}
root = (PNode)malloc(sizeof(Node));
root->data = data;
root->left = createBtree(root->left);
root->right = createBtree(root->right);

return root;
}

int depth(PNode root)//這就是你要的函數。
{
int ld,rd;
if (root==NULL)
{
return 0;
}
ld = 1+depth(root->left);
rd = 1+depth(root->right);
return ld>rd?ld:rd;
}
int main()
{
PNode root=NULL;
root = createBtree(root);
printf("%d",depth(root));
return 0;
}

為了測試，寫了二叉樹的建立程序；
如下輸入可以看到結果
虛節點用空格輸入的。例如你輸入
先序遍歷
234空格空格5空格6空格空格7空格空格回車就可以看到結果。
另外，本演算法是從1開始算深度的，就是根節點是深度下。
樹的圖形參考
http://hi..com/huifeng00/blog/item/c1e37a4d59310b3caec3ab32.html

⑸ 二叉樹的深度怎麼算

二叉樹的深度計算，首先要判斷節點，以下是計算二叉樹的詳細步驟：

1、一顆樹只有一個節點，它的深度是1；

2、二叉樹的根節點只有左子樹而沒有右子樹，那麼可以判斷，二叉樹的深度應該是其左子樹的深度加1；

3、二叉樹的根節點只有右子樹而沒有左子樹，那麼可以判斷，那麼二叉樹的深度應該是其右樹的深度加1；

4、二叉樹的根節點既有右子樹又有左子樹，那麼可以判斷，那麼二叉樹的深度應該是其左右子樹的深度較大值加1。

一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且最後一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。

具有n個節點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個葉子節點，至多有2k-1個節點。

5、有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：

若I為結點編號則 如果I>1，則其父結點的編號為I/2；

如果2*I<=N，則其左孩子（即左子樹的根結點）的編號為2*I；若2*I>N，則無左孩子；

⑹ 請寫出計算二叉樹的深度的演算法

typedef struct tree//二叉樹的定義
{ char data; struct tree *lchild,*rchild; }TREE,*Tree;

void create(Tree t)//創建一棵二叉樹
{ char ch; scanf("%c",&ch); if(ch=='#') t=NULL;
else { t->data=ch; create(t->lchild); create(t->rchild); }
}
int deep(Tree t)//深度演算法
{ if(!t) return 0; else { ld=deep(t->lchild); rd=deep(t->rchild);
if(ld>rd) return rd+1; else return ld+1;
}
void main()//主函數
{ Tree t; create(t); printf("%d\n",deep(t)); }

⑺ 寫一個求二叉樹的深度的演算法

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
char data;
struct node *left,*right;
}Node,*PNode;
PNode createBtree(PNode root)//創建二叉樹，控制台下輸入，基於先序遍歷輸入
{
char data;
scanf("%c",&data);
if (data==' ')
{
root=NULL;
return root;
}
root = (PNode)malloc(sizeof(Node));
root->data = data;
root->left = createBtree(root->left);
root->right = createBtree(root->right);

return root;
}

int depth(PNode root)//這就是你要的函數。
{
int ld,rd;
if (root==NULL)
{
return 0;
}
ld = 1+depth(root->left);
rd = 1+depth(root->right);
return ld>rd?ld:rd;
}
int main()
{
PNode root=NULL;
root = createBtree(root);
printf("%d",depth(root));
return 0;
}

為了測試，寫了二叉樹的建立程序；
如下輸入可以看到結果
虛節點用空格輸入的。例如你輸入
先序遍歷
234空格空格5空格6空格空格7空格空格回車就可以看到結果。
另外，本演算法是從1開始算深度的，就是根節點是深度下。

⑻ 編寫遞歸演算法求二叉樹的深度（要求寫出二叉樹的類型定義）

type btnode=record
key:integer;
lchd,rchd:^btnode;
end;
var bt:btnode;

function depth(bt):integer;
var a,b:integer;
begin
if bt=nil then depth:=0
else
begin
a:=depth(bt^lchd);
b:=depth(bt^rchd);
if a>b then depth:=a+1 else depth:=b+1; /* 根結點深度為1 */
end;
end;

⑼ 寫出二叉樹深度的演算法

基本思路就是如果當前節點還有子節點，則繼續訪問，遞歸的找尋子節點直到葉子節點為止。
procere
tree(a:node,depth:integer);
begin
if
result<depth
then
result:=depth;
if
a.leftchild<>nil
then
tree(a.leftchild,depth+1);
if
a.rightchild<>nil
then
tree(a.rightchild,depth+1);
end;
注:result是全局變數,是結果
實際上最好不用什麼全局變數
int
depth(node
*bt)
{
if
(bt==NULL)
return
0;
ldepth=depth(bt->left)+1;
rdepth=depth(bt->right)+1;
return
max(ldepth,rdepth);
}
全局變數是bug
int
Height(BiTree
T){
int
m,n;
if(!T)
return(0);
else
m=Height(T->lchild);
n=Height(T->rchild);
return((m>n?m:n)+1);
}
求樹深度的遞歸演算法
//
struct
bnode{struct
bnode
*lc,*rc);
int
depth(struct
bnode
*r)
{
return
r==NULL?0:1+max(depth(r->lc),depth(r->rc));
}