小树截点计算方法

⑴ 关于树的结点算法，请大家帮帮忙，过程详细点，谢谢！！！

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())==' ')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree root;
int i,depth;
printf("NodeNum:%d\n",NodeNum);
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do { //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //先判断节点数是否已有。不用再先选择4，求出该树的结点数。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5:
if(!NodeNum)
TreeDepth(root);
printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}

⑵ 完全二叉树的叶子节点数公式是什么

n0＝（n＋1）/2

设：度为i的结点数为ni，由二叉树的性质可知：

n0 = n2 + 1……………………①式

n = n0 + n1 + n2……………②式

由①式可得 n2 = n0 - 1，带入②式得：

n0 = （n + 1 - n1）/ 2

由完全二叉树性质可知：

如图，当n为偶数时，n1 = 1， n0 = n / 2

将两式合并，写作：n0 = ⌊（n+1）/2⌋（向下取整符号不能丢）

(2)小树截点计算方法扩展阅读：

按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱结点；除最后一个结点外，每个结点有且仅有一个直接后继结点。

但是，二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么，二叉树的存储结构中并没有反映出来，只能在对二叉树遍历的动态过程中得到这些信息。为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。

⑶ 树的节点和度的计算

树的高度=log2(这个在底下)（n+1)这个在上面，n=25,这样可以算出，是多少高，高度为5，高度为4的总结点为（2^4）-1=15，那么，第5层就剩10,度为0也就是叶子节点为10，度为2的节点是度为0的节点-1，就是9。

例如：

设该树中所有结点的度为x，因为，在树的结权点中，除了根结点以外，其余结点都有一个分支进入，所以，n=x+1，所以x=n-1。

每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。

(3)小树截点计算方法扩展阅读：

对于二叉树有下列基本运算：

（1）建空二叉树Setnull（BT），置BT为空二叉树。

（2）求二叉树的根root（x），求结点x所在二叉树的根。

（3）求双亲结点parent（BT，x），在二叉树BT中求结点x的双亲结点。

（4）求左或右孩子结点lchild（BT，x）或rchild（BT，x），在二叉树BT中求结点x的左孩子结点或右孩子结点。

⑷ 二叉树结点的计算

首先我们知道，前序遍历的规则是：根结点→左子结点→右子结点
中序遍历是：左子结点→根结点→右子结点
后序遍历是：左子结点→右子结点→根结点

那么，对于一棵二叉树，前序遍历的第一个结点一定是这棵树的根结点，即根结点是a。
在中序遍历的顺序dgbaechf中，以a分成左、右两边，左边是dgb，右边是echf。
所以，这棵树现在可以确定如下：
a
/\
dgbechf
接下来再分别对左子树和右子树进行类似的操作。
对于左子树dgb来说，在前序遍历abdgcefh中找到bdg，证明这子树的根是b，那么现在可以确定的树结构如下：
a
/\
bechf
/
dg
再看dg，前序遍历中的顺序为dg，所以d是dg这部分子树的根，那么又因为中序遍历的dg顺序也是dg，所以g是右子结点。
即：
a
/\
bechf
/
d
\
g
现在看echf这部分子树，前序中顺序是cefh，所以子树根结点是c，那么左子结点是e，右子树是hf：
得到：
a
/\
bc
//\
dehf
\
g
最后只剩下hf部分了，前序遍历中是fh，所以根是f，那么h就是左子结点。
现在得到了整棵树：
a
/\
bc
//\
def
\/
gh

对这棵树再进行后序遍历就行了，结果就是：gdbehfca

⑸ 二叉树结点计算

1.深度为m的满二叉树有2^m-1个结点.
因为满二叉树的定义为:一颗深度为k且有2^k-1个结点的二叉树称为满二叉树.
2.若要树深为最小,显然要使除最后一层外的每一层都有尽可能多的结点,即要二叉树为完全二叉树.

由二叉树的一个重要性质:具有n个结点的完全二叉树的深度为[log2n]+1.(这是在根节点层次为1时,若为0,将+1去掉即可)
log2n是以2为底n的对数
[log2n]为不大于log2n的最大整数

可知,含有100个(根)结点的二叉树,(应该没"根"字吧)
可能的最小树深为[log2 100 ]+1
二叉树根结点的层次为0时,可能的最小树深为[log2 100 ]
即为6.

可以这样计算:确定最小树深当且仅当二叉树为完全二叉树时出现,设深度为k,(此时设二叉树根结点的层次为0)有:
2^0+2^1+2^2+...+2^(k-1)<100=<2^0+2^1+...+2^k
即2^k-1<100=<2^(k+1)-1
或2^k=<100<2^(k+1) (上下两式是相等的)
其中2^k为完全二叉树的第k层的最多结点个数
解得k=<log2 100<k+1
即k=[log2 100]=6

⑹ 二叉树计算节点

二叉树计算节点方法：
(1)在二叉树的第k 层上，最多有2k-1(k≥1)个结点，
(2)深度为m的二叉树最多有2m-1 个结点，
(3)度为0 的结点(即叶子结点)总是比度为2 的结点多一个，
(4)具有n 个结点的二叉树，其深度至少为[log2n]+1,其中[log2n] 表示取log2n 的整数部分，
(5)具有n 个结点的完全二叉树的深度为[log2n]+1，
(6)设完全二叉树共有n 个结点。如果从根结点开始，按层序(每 一层从左到右)用自然数1，2，….n 给结点进行编号(k=1,2….n)， 有以下结论:
①若k=1，则该结点为根结点，它没有父结点;若k>1，则该结点的 父结点编号为INT(k/2);
②若2k≤n，则编号为k 的结点的左子结点编号为2k;否则该结点 无左子结点(也无右子结点);
③若2k+1≤n，则编号为k 的结点的右子结点编号为2k+1;否则该 结点无右子结点。

⑺ 二叉树结点的计算方法

一般会给你一度的结点个数，在给你一个已知的0度或是2度的节点个数

再根据度是0的节点个数比度是2的节点个数多1的二叉树特性来算出总共的节点！

⑻ 怎么样才能算出一个树或二叉树有多少个结点

如果用程序来实现的话，我觉得应该遍历这个树。
首先设置一个计数器，每访问一个节点，就把计数器加1，最后察看你计数器的值，也就知道有多少个节点了；
如果是2叉树，可以采用先序，中序或后序遍历的方法。
如果是普通树，可以采用广度优先搜索或深度优先搜索的方法来遍历这个树。

⑼ 二叉树的叶子节点数如何计算

结点的度是指，该结点的子树的个数，在二叉树中，不存在度大于2的结点。

计算公式：n0=n2+1

n0 是叶子节点的个数

n2 是度为2的结点的个数

n0=n2+1=5+1=6

故二叉树有5个度为2的结点，则该二叉树中的叶子结点数为6。

(9)小树截点计算方法扩展阅读

叶子结点是离散数学中的概念。一棵树当中没有子结点（即度为0）的结点称为叶子结点，简称“叶子”。 叶子是指度为0的结点，又称为终端结点。

叶子结点 就是度为0的结点 就是没有子结点的结点。

n0：度为0的结点数，n1:度为1的结点 n2：度为2的结点数。 N是总结点

在二叉树中：

n0=n2+1；

N=n0+n1+n2

参考资料：叶子结点_网络

⑽ 叶子节点数计算公式是什么

结点的度是指，该结点的子树的个数，在二叉树中，不存在度大于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