二叉树的心得体会

时间：2017-06-13 16:37

求数据结构做二叉树实验的心得体会、、、

#include#include#includeStatus.c#includeSqStack.c#include二叉树.cvoid 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;} \\\/\\\/PreOderTraversevoid 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} \\\/\\\/InOrderTraverseStatus 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;} \\\/\\\/CreateBiTreevoid 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} \\\/\\\/countleafvoid 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 100typedef struct {DataType data[M]; \\\/\\\/存放栈元素的数组int top; \\\/\\\/ 栈顶指针,初始时设为0} Stack,*SqStack; \\\/\\\/--------基本操作的函数原型说明----------Stack InitStack(){ \\\/\\\/构造一个空栈SStack S; S.top=0; return S;}\\\/\\\/InitStackStatus 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){ \\\/\\\/ 判断栈满，若栈满返回1if (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;}\\\/\\\/PushStatus 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

已知二叉树度为1的结点,怎么求二叉树的总结点数?

度为1的结点个数不决定二叉树的结点总数，因此只是知道二叉树为1的结点数不能推出整个二叉树结点总数。

例如度为1的结点数为0 ，此时二叉树可以是任意层次的满二叉树

二叉树有叶子结点，有度为1的结点，总结点怎么算
有公式嘛

二叉树有如下性质：N0 = N2 +1，即叶子节点数等于度为2的结点数+1,该性质证明网上很多。

根据叶子节点算出度为2的结点数，然后结合度为1的节点数，就可以算出总结点数了。

试编程求二叉树T的总结点数

二叉树就是说一个结点下面可能有两个子结点（度为2），也可能有一个子结点（度为1），或者没有子结点（度为0，也叫叶子结点）那么在这棵树中只可能出现三种情况：度为2，度为1，度为0（叶子结点）。

不可能出现其他情况，否则就不是二叉树了。

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

已经知道：度为0=70，度为1=80度为2=度为0-1=69（这是公式，原因说起来太麻烦，你自己画个图可能会更清楚。

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

二级C语言中告诉了完全二叉树的总结点数,怎么求它的叶子结点数?

设一棵完全二叉树共有699个结点.首先需要求出这棵树的深度。

。

也就是说这棵树有多少层。

。

完全二叉树有一个性质：具有n个结点的完全二叉树的深度为log2n(2是下标)+1。

根据这个性质，就可以求得完全二叉树的深度为1010层满二叉树的总结点数为1023，最后一层的结点数应该是2的9次方为512，所以肯定699个结点肯定不是满二叉树。

。

叶子节点出现在最后两层上。

。