求二叉树的总结点数

求二叉树T的总结点数~

#include
#include
#include"Status.c"
#include"SqStack.c"
#include"二叉树.c"
void main( ){

BiTree T;

int c,h,l;
printf("构造二叉树
");
CreateBiTree(T);
printf("统计二叉树的叶结点数
");
countleaf(T,&c);
printf("计算二叉树的深度
");
treedepth(T,l,&h);
printf("%d
%d
",&c,&h);


}


以下这一段建文件为SqStack.c
//-----------二叉树的二叉链表存储表示---------

typedef struct BiTNode{
DataType data;
struct BiTNode *lchild, *rchild;
} BiTNode,*BiTree;//左右孩子指针

int PreOderTraverse( BiTree T,int(*visit)(DataType) ) { //先序遍历的递归算法
if(T) {
if(visit(T->data))
if(PreOderTraverse (T->lchild,visit))
if(PreOderTraverse (T->rchild,visit))
return OK;
return ERROR; }
else return OK;
} //PreOderTraverse
void preTraverse(BiTree T ){ //先序遍历的非递归算法
BiTree p;
Stack S;
if(T){
p=T;
S=InitStack();//构造一个空栈

Push(&S,p);//根指针进栈
while(!StackEmpty(&S)) {
while(GetTop(&S,&p)&& p){
p=p->data;//访问*p
Push(&S,p->lchild);//向左到头
}
Pop(&S,&p);//空指针退栈
if(!StackEmpty(&S)){ //访问结点，向右一步
Pop(&S,&p);
p=p->rchild;
Push(&S,p); //向右走
} // if
} //while
} // if
} //InOrderTraverse
Status CreateBiTree(BiTree T){ //先序输入二叉树中元素值，构造二叉链表
char ch;
ch=getchar( );
if(ch==' ') T=NULL;
else {
T=(BiTree )malloc(sizeof(BiTNode));
if(!T) exit(OVERFLOW);
T->data=ch; //生成根结点
CreateBiTree(T->lchild); //构造左子树
CreateBiTree(T->rchild);
} //构造右子树
return OK;
} //CreateBiTree
void countleaf(BiTree T, int c) {
//统计二叉树T的叶结点数，结果存于c中
if(T){
if((!T->lchild)&&(!T->rchild)) {
c++; // 若T所指结点无左、右子结点则计数
return;
}
countleaf(T->lchild,c);//统计左子树的叶结点数
countleaf(T->rchild,c);//统计左子树的叶结点数
} //if
} //countleaf
void treedepth(BiTree T,int l,int h){
// 求二叉树T的深度，结果存放在h中，l是当前层数
int l1=0,l2=0,h1=0,h2=0;
if(T){
l++;
if (l>h) h=l;
treedepth(T->lchild,l1, h1);//求左子树的深度
treedepth(T->rchild,l2, h2);//求右子树的深度
if (h1>h2) h=h+h1;
else h=h+h2;
} //if
} // treedepth


以下这一段，建文件为 二叉树.c
//===========ADT Stack的表示与实现===========

//-------------栈的顺序存储表示----------

#define M 100
typedef struct {
DataType data[M]; //存放栈元素的数组
int top; // 栈顶指针,初始时设为0
} Stack,*SqStack;

//--------基本操作的函数原型说明----------
Stack InitStack(){
//构造一个空栈S
Stack S;
S.top=0;
return S;
}//InitStack
Status ClearStack(SqStack S){
//将栈S清空,把S置为空栈
S->top=0;
return OK;
}
Status StackEmpty(SqStack S){
//若栈S为空栈，则返回TRUE，否则返回FALSE
if(S->top==0) return TRUE;
else return FALSE;
}
Status GetTop(SqStack S, DataType *e) {
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
if( S->top==0) return ERROR;
*e=S->data[S->top-1];
return OK;
}
Status StackFull(SqStack S){
// 判断栈满，若栈满返回1
if (S->top==M)
return TRUE;
else return FALSE;
}

Status Push(SqStack S,DataType e){
//若栈满返回0，否则在栈顶插入元素e
if (StackFull(S)) //栈满不能进栈
return OVERFLOW;
S->data[S->top] = e; //在栈顶插入x
S->top++; //栈顶指针加1
return OK;
}//Push
Status Pop(SqStack S, DataType *e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(StackEmpty(S))
return ERROR;
S->top--; //栈顶指针减1
*e=S->data[S->top];//取栈顶元素存入e，
return OK;
}//Pop

//---------------------------------------------------------------------------
#include

using namespace std;

typedef struct node
{
struct node *L,*R;
string name;
}NODE;
int count =0; //计数

//输入
void Input(NODE **T,int num)
{
string name;
int L,R;
*T = new NODE[num];
for (int i=0;i<num;)
{
cout << "输入第"<<i+1<<"个结点名称、左右子序号:"<<endl;
cin >> name >> L >> R;
if(L >=num || R >=num)
{
cout << "输入结点序号非法，请重新输入"<<endl;
continue;
}
(*T+i)->name = name;
(*T+i)->L = L==-1? NULL:*T+L;
(*T+i)->R = R==-1? NULL:*T+R;
i++;
}

}
//前序
void NLR(NODE *T)
{
if(T==NULL)return ;
count++;
cout name<<" ";
NLR(T->L);
NLR(T->R);
}

int main()
{
NODE *T=NULL,t;
int num;
cout << "输入结点数:"<<endl;
cin >> num;
Input(&T,num);
cout <<"前序：";
NLR(T);
cout << endl;

cout << "总结点数:"<< count << endl;

system("PAUSE");
return 0;
}

二叉树一个结点下面可能有两个子结点（度为2），也可能有一个子结点（度为1），或者没有子结点（度为0，也叫叶子结点）

那么在这棵树中只可能出现三种情况：度为2，度为1，度为0（叶子结点）。不可能出现其他情况，否则就不是二叉树了。

所以，总结点数应该为三者之和。

已经知道：度为0=70，度为1=80

度为2=度为0-1=69（这是公式，原因说起来太麻烦，你自己

画个图可能会更清楚。）

所以：总结点数=度为2+度为1+度为0=69+80+70=219

扩展资料：

二叉树性质

(1) 在非空二叉树中，第i层的结点总数不超过

, i>=1；

(2) 深度为h的二叉树最多有

个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为

（注：[ ]表示向下取整）

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I>1，则其父结点的编号为I/2；

如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I>N，则无左孩子；

如果2*I+1<=N，则其右孩子的结点编号为2*I+1；若2*I+1>N，则无右孩子。

(6)给定N个节点，能构成h(N)种不同的二叉树。

h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。

(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

参考资料：百度百科-二叉树

二叉树就是说一个结点下面可能有两个子结点（度为2），也可能有一个子结点（度为1），或者没有子结点（度为0，也叫叶子结点）

那么在这棵树中只可能出现三种情况：度为2，度为1，度为0（叶子结点）。不可能出现其他情况，否则就不是二叉树了。
所以，总结点数应该为三者之和。
已经知道：度为0=70，度为1=80
度为2=度为0-1=69（这是公式，原因说起来太麻烦，你自己
画个图可能会更清楚。）
所以：总结点数=度为2+度为1+度为0=69+80+70=219

二叉树一个结点下面可能有两个子结点（度为2），也可能有一个子结点（度为1），或者没有子结点（度为0，也叫叶子结点）
那么在这棵树中只可能出现三种情况：度为2，度为1，度为0（叶子结点）。不可能出现其他情况，否则就不是二叉树了。
所以，总结点数应该为三者之和。
已经知道：度为0=70，度为1=80
度为2=度为0-1=69（这是公式，原因说起来太麻烦，你自己
画个图可能会更清楚。）
所以：总结点数=度为2+度为1+度为0=69+80+70=219
扩展资料：
二叉树性质
(1) 在非空二叉树中，第i层的结点总数不超过
, i>=1；
(2) 深度为h的二叉树最多有
个结点(h>=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(4) 具有n个结点的完全二叉树的深度为
（注：[ ]表示向下取整）
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I>1，则其父结点的编号为I/2；
如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I>N，则无左孩子；
如果2*I+1<=N，则其右孩子的结点编号为2*I+1；若2*I+1>N，则无右孩子。
(6)给定N个节点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。
(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i
参考资料：百度百科-二叉树
编辑于 2019-07-29

总结点数=度为2+度为1+度为0（叶子）
度为2=度为0-1（公式）

so 总=69+80+70=219

---

永泰县14752506796： 二叉树中,度为1的结点有15个,度为2的结点有16个,求结点总数. - ？
漫涛迪维：[答案] 设二叉树中度为0,1,2的结点分别有N0,N1,N2个,总结点数为N. (二叉树中结点数满足N0=N2+1.) 总结点数N=N0+N1+N2,将上式代入,即=N2+1+N1+N2=2*N2+N1+1 根据你给的题,结点总数=2*16+15=47

永泰县14752506796： 二叉树共有70个叶子节点与80个度为1的节点,总结点数怎么计算? - ？
漫涛迪维：[答案] 二叉树中只有度为0.1.2的结点,其中度为2的节点数比度为0的结点数(叶子结点)少1 N0+N1+N2=70+80+69=219

永泰县14752506796： 数据结构二叉树一棵二叉树中共有70 个叶子结点与80 个度为1的结点,则该二叉树中的总结点数为多少?其计算公式是什么? - ？
漫涛迪维：[答案] 已知公式 1结点总数n=n0+n1+n2 2 n0 = n2+1 得到n=2n0+n1-1 no = 70 n1 = 80 n = 219

永泰县14752506796： 已知二叉树有50个叶子结点,则该二二叉树总结点至少多少个? - ？
漫涛迪维：[答案] 99个. 1、二叉树共用3类结点,即度为2的结点,度为1的结点和度为0的结点(叶子结点); 2、任何一个二叉树的叶子结点数总比度为2的结点数多一个; 3、至少的情况就是该二叉树为满二叉树,及没有度为1的结点; 故,50+49=99.

永泰县14752506796： 一棵二叉树中共有70个叶子结点与80个度为1的结点,则该二叉树中的总结点数为 219 - ？
漫涛迪维：[答案] 一棵二叉树中,度为2的节点数等于度为0的节点数(n0=70个叶子结点)减1,即n2=n0-1,叶子节点即度为0,故n2=69. 总节点数=n0+n1+n2=70+80+69=219 所以命题正确 做的正确吗

永泰县14752506796： 已知一棵树深为8的完全二叉树最下层有4个结点,计算其叶子结点数和总结点数(写出计算过程) - ？
漫涛迪维：[答案] 设根结点层次为1 按照条件,最下层(第8层)有4个结点,于是上面7层为满二叉树,有结点2^7-1=127个 于是总结点数为127+4 = 131个 因为满二叉树第7层有2^(7-1)=64个结点,最下层为4个结点,因为是完全二叉树,因此4个结点占有双亲结点数=...

永泰县14752506796： 某二叉树共有60个叶子结点和50个度为1的结点,则该二叉树中的总结点数为 - ？
漫涛迪维：[选项] A. 148 B. 169 C. 182 D. 198 怎么计算

永泰县14752506796： 告诉了一棵完全二叉树的总结点个数,求叶子结点个数怎么计算?设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点个数为?怎么计算, - ？
漫涛迪维：[答案] 首先需要求出这棵树的深度.也就是说这棵树有多少层. 完全二叉树有一个性质: 具有n个结点的完全二叉树的深度为log2n(2是下标)+1. 根据这个性质,就可以求得完全二叉树的深度为10 10层满二叉树的总结点数为1023,最后一层的结点数应该是2的...

永泰县14752506796： 二叉树共70个叶子结点,80个度为1的结点,则总结点数? - ？
漫涛迪维：[答案] n=n2+n1+n0=(n0-1)+n1+n0=69+80+70=219

永泰县14752506796： 已知二叉树有51个叶子结点,则该二叉树的总结点数至少是______________. - ？
漫涛迪维：[答案] 这个应该这么想,添上多少最接近满,也就是,到64个叶子节点,即深度到7.则第六层是满的,即32个节点,但若干节点不是叶子节点,设个X,而剩下的是叶子节点设为Y,若第七层的叶子节点为偶数,或者为基数,其式子都...