二叉樹的深度演算法

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

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

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

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

㈢ 求二叉樹的深度演算法(具體點)

肯定要判斷啊，因為二叉樹的深度除了根的一層外，肯定是左右子樹的的深度的最大值加1

㈣ 二叉樹深度的演算法

#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、一顆樹只有一個節點，它的深度是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，則無左孩子；

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

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

㈦ 如何求二叉樹深度

二叉樹性質如下：
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的對數）

㈧ 二叉樹的深度和高度有什麼區別

一、概念不同

深度是從根節點數到它的葉節點，高度是從葉節點數到它的根節點。

二叉樹的深度是指所有結點中最深的結點所在的層數。

對於整棵樹來說，最深的葉結點的深度就是樹的深度；樹根的高度就是樹的高度。這樣樹的高度和深度是相等的。

對於樹中相同深度的每個結點來說，它們的高度不一定相同，這取決於每個結點下面的葉結點的深度。

二、定義不同

高度和深度是相反的表示，深度是從上到下數的，而高度是從下往上數。

三、計算方式不同

1、二叉樹深度演算法如下：

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

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

2、分析二叉樹的深度（高度）和它的左、右子樹深度之間的關系。從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，演算法中「訪問結點」的操作為：求得左、右子樹深度的最大值，然後加 1 。

(8)二叉樹的深度演算法擴展閱讀：

樹是一種重要的非線性數據結構，直觀地看，它是數據元素按分支關系組織起來的結構，很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。

樹在計算機領域中也得到廣泛應用，如在編譯源程序如下時，可用樹表示源源程序如下的語法結構。又如在資料庫系統中，樹型結構也是信息的重要組織形式之一。一切具有層次關系的問題都可用樹來描述。滿二叉樹，完全二叉樹，排序二叉樹。

在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」和「右子樹」。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。

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

二叉樹性質如下：

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 （稱為後根次序遍歷）。