深度演算法_深度優先演算法和寬度優先演算法的優缺點

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

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

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

關於遞歸，你可以看成是一句一句往下運行嘛。需要保存狀態的時候，系統就會自動用棧幫你保存。就依你說得那個為例：
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"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的結點的演算法

⑸ 深度優先演算法和寬度優先演算法的優缺點

1、深度優先演算法佔內存少但速度較慢，廣度優先演算法佔內存多但速度較快，在距離和深度成正比的情況下能較快地求出最優解。
2、深度優先與廣度優先的控制結構和產生系統很相似，唯一的區別在於對擴展節點選取上。由於其保留了所有的前繼節點，所以在產生後繼節點時可以去掉一部分重復的節點，從而提高了搜索效率。
3、這兩種演算法每次都擴展一個節點的所有子節點，而不同的是，深度優先下一次擴展的是本次擴展出來的子節點中的一個，而廣度優先擴展的則是本次擴展的節點的兄弟點。在具體實現上為了提高效率,所以採用了不同的數據結構。

⑹ 二叉樹中是否有深度優先演算法

二叉樹中有深度優先演算法。
事實上，樹和圖中都有深度優先演算法。

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

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;

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

⑻ 求基坑深度計算方法、、

基坑開挖深度=基礎底部的設計標高值-（±0.000的黃海高程值-自然地面的黃海高程值）

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

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

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

導航:首頁 > 源碼編譯 > 深度演算法

深度演算法

與深度演算法相關的資料