树和二叉树心得体会

时间：2018-04-10 17:13

树和二叉树实验总结

树的话是计算机语言，其中二叉树是树的一个特例，是树每个节点分出2个小节满树的树为二叉树。

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

#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

急急急
已知二叉树有50个叶子结点，则该二二叉树总结点至少多少个

99个。

1、二叉树共用3类结点，即度为2的结点，度为1的结点和度为0的结点（叶子结点）；2、任何一个二叉树的叶子结点数总比度为2的结点数多一个；3、至少的情况就是该二叉树为满二叉树，及没有度为1的结点；故，50+49=99.

已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个

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

。

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

。

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

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

。

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

。

最后一层叶子结点个数为：699-（1023-512）=188倒数第二层的叶子节点数为：（512-188)\\\/2=162叶子总数应该是：188+162 = 250不确定有没有算对.大概思路应该是这样的.希望对你有帮助

一个二叉树中共有70个叶子结点与80个度为1的结点,则该二叉树的总结点树为多少个?