編寫演算法球二叉樹的深度

1. 幫我寫出二叉樹深度的演算法急急急！

typedefstructtree//二叉樹的定義
{chardata;structtree*lchild,*rchild;}TREE,*Tree;
voidcreate(Treet)//創建一棵二叉樹
{charch;scanf("%c",&ch);if(ch=='#')t=NULL;<br/>else{t->data=ch;create(t->lchild);create(t->rchild);}
}
intdeep(Treet)//深度演算法
{if(!t)return0;else{ld=deep(t->lchild);rd=deep(t->rchild);<br/>if(ld>rd)returnrd+1;elsereturnld+1;<br/>}
voidmain()//主函數
{Treet;create(t);printf("%d\n",deep(t));}

2. 數據結構：寫一個演算法求一顆二叉樹的深度，二叉樹以二叉鏈表為存儲方式。

二叉樹結構體
struct
bintree{
int
data;
struct
bintree
*
left;
struct
bintree
*
right;
};
有一棵已建好的二叉樹
根指針為*root
函數max定義為
int
max(int
a,int
b)
{
if
(a>b)
return
a;
else
return
b;
}
則設計遞歸演算法
函數
depth
int
depth(struct
bintree
*
r)
{
if
(r==null)
return
0;
if
(r->left
==
null
&&
r->right
==
null)
return
1;
else
return
1+(max(depth(r->left),depth(r->right)));
}

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

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;

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

#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

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

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)); }

6. 二叉樹的深度演算法怎麼算啊

二叉樹的深度演算法：
一、遞歸實現基本思想：
為了求得樹的深度，可以先求左右子樹的深度，取二者較大者加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
}

7. 如何求二叉樹深度

二叉樹性質如下：
1
：在二叉樹的第i層上至少有2^（i-1）個結點
2：深度為k的二叉樹至多有2^(k-1)個結點
3：對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1
4：具有n個結點的完全二叉樹的深度是【log2n】+1（向下取整）
5：如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點i(1in)，有：
如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親是i/2
如果2i>n，則結點i無左孩子；如果2in，則其左孩子是2i
如果2i+1>n，則結點i無右孩子；如果2i+1n，則其右孩子是2i+1
二叉樹深度演算法如下：
深度為m的滿二叉樹有2^m-1個結點；
具有n個結點的完全二叉樹的深度為[log2n]+1.（log2n是以2為底n的對數）

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

#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開始算深度的，就是根節點是深度下。

9. 二叉樹的性質有些啊怎麼求它的深度

二叉樹性質如下：

1 ：在二叉樹的第i層上至少有2^（i-1）個結點

2：深度為k的二叉樹至多有2^(k-1)個結點

3：對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1

4：具有n個結點的完全二叉樹的深度是【log2n】+1（向下取整）

5：如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點i(1in)，有：

如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親是i/2

如果2i>n，則結點i無左孩子；如果2in，則其左孩子是2i

如果2i+1>n，則結點i無右孩子；如果2i+1n，則其右孩子是2i+1

二叉樹深度演算法如下：

深度為m的滿二叉樹有2^m-1個結點；

具有n個結點的完全二叉樹的深度為[log2n]+1.（log2n是以2為底n的對數）

(9)編寫演算法球二叉樹的深度擴展閱讀：

在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。

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

二叉樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二叉樹還要滿足根結點的度不大於2。有了根結點之後，每個頂點定義了唯一的父結點，和最多2個子結點。然而，沒有足夠的信息來區分左結點和右結點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。

遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

設L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為後根次序遍歷）。

10. 寫出二叉樹深度的演算法

基本思路就是如果當前節點還有子節點，則繼續訪問，遞歸的找尋子節點直到葉子節點為止。
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));
}