二叉树的深度算法

㈠ 请写出计算二叉树的深度的算法

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 （称为后根次序遍历）。