树度的算法
Ⅰ C语言关于二叉树的度的算法
可怜的管理员哭泣着乱踹两脚
被映得粉亮的翅膀，直到拖着尖锐的
我们为之干杯的死亡，
父亲戴一件绒毛状火红头饰
让路。白日怀疑自己，
她每天只就让复一个工作哈哈
Ⅱ 二叉树的深度怎么算
二叉树的深度计算，首先要判断节点，以下是计算二叉树的详细步骤：
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"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); 了。分析同上。
这个过程的确比较复杂。慢慢琢磨吧。呵呵。
Ⅳ 二叉树的深度算法怎么算啊
二叉树的深度算法：
一、递归实现基本思想：
为了求得树的深度，可以先求左右子树的深度，取二者较大者加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
}
Ⅵ 求二叉树高度的原理、算法是什么，越详细越好，C语言，谢谢
首先分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加
1
。
int
Depth
(BiTree
T
){
//
返回二叉树的深度
if
(
!T
)
depthval
=
0;
else
{
depthLeft
=
Depth(
T->lchild
);
depthRight=
Depth(
T->rchild
);
depthval
=
1
+
(depthLeft
>
depthRight
?
depthLeft
:
depthRight);
}
return
depthval;
}
Ⅶ 关于递归算法求二叉树深度算法
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;
这个就是终止条件了，如果没有子节点就返回。
Ⅷ 求一个关于求二叉树度为2的结点数 的算法
分析:二叉树中2度结点数的递归定义为
①当T为空或为叶子时,以T为根的二叉树的2度结点数为0;
②当T是2度结点时,以T为根的二叉树的2度结点数为T的左右子树中2度结点数这和再加上T结点本身;
③当T是1度结点时,以T为根的二叉树中2度结点数为T的左或子树中2度结点数之和.
其算法如下:
int D2Nodes(BinTree T){
if(!T||!T->lchild&&!T->rchild) //T为空或是叶子
return 0;
if(T->lchild&&T->rchild) //T是2度结点
return 1+D2Nodes(T->lchild)+D2Nodes(T->rchild);
else //T是1度结点
return D2Nodes(T->lchild)+D2Nodes(T->rchild);
}
Ⅸ 对以孩子链表表示的树编写计算树的深度的算法
typedef struct TreeNode
{
TreeNode *child;
TreeNode *sibling;
int data;
}TreeNode;
//这是用了递归的思想，需要仔细体会
int GetChildeSiblingTreeDegree(TreeNode *root)
{
//如果当前树的根节点没有孩子和兄弟，那么，该树的度就是0
if (root->child == NULL && root->sibling == NULL)
{
return 0;
}
//如果该树只有兄弟，则该树的度就等效于对他的兄弟分支的子树求度
else if( root->sibling != NULL)
{
return GetChildeSiblingTreeDegree(root->sibling);
}
//如果该树只有孩子，那么先求出该根节点的度，然后再对它孩子分支子树求度，两者取较大者，即该树的度
else if(root->child != NULL)
{
int rootDegree = 1;
TreeNode *p = root->child;
while(p->sibling != NULL)
{
p = p->sibling;
rootDegree++;
}
int childTreeDegree = GetChildeSiblingTreeDegree(root->child);
return rootDegree > childTreeDegree ? rootDegree : childTreeDegree;
}
}
Ⅹ 叶子节点数计算公式是什么
结点的度是指，该结点的子树的个数，在二叉树中，不存在度大于2的结点。
计算公式：n0=n2+1
n0 是叶子节点的个数
n2 是度为2的结点的个数
n0=n2+1=5+1=6
故二叉树有5个度为2的结点，则该二叉树中的叶子结点数为6。
(10)树度的算法扩展阅读：
叶子结点就是度为0的结点，就是没有子结点的结点。
n0：度为0的结点数，n1:度为1的结点 n2：度为2的结点数，N是总结点。
在二叉树中：
n0=n2+1；
N=n0+n1+n2