《第六章-树(算法设计)许昌网络公司》由会员分享，可在线阅读，更多相关《第六章-树(算法设计)许昌网络公司（5页珍藏版）》请在装配图网上搜索。
1、第六章 树（算法设计）一、树的算法验证程序已知一棵具有n个结点的完全二叉树被顺序存储在一维数组An中,试编写一个算法输出Ai结点的双亲和所有孩子。void parent(int a,int n,int i)if(i=1) printf(无双亲 n);return;elseprintf(双亲:%dn,a(i-1)/2);void child(int a,int n,int i) /*i为序号 */int queueMAX,front=0,tail=0,p; /* 队列作为辅助，存储孩子的序号*/queue0=i;tail+;while(fronttail)p=queuefront+;if(p!=
2、i)printf(%d ,ap-1); /*自身不输出 */if(2*p=n)queuetail+=2*p;if(2*p+1data=ch;create(&(*T)-lchild);create(&(*T)-rchild); void inorder(NODE *p) /中序编历二叉树if(p!=NULL)inorder(p-lchild);printf(%c ,p-data);inorder(p-rchild);int num=0;void count(NODE *p) /统计出二叉树中单孩子的结点数方法1if(p!=NULL)count(p-lchild);if(p-lchild!=NUL
3、L&p-rchild=NULL|p-lchild=NULL&p-rchild!=NULL)num+;count(p-rchild);void count1(NODE *p,int *num1)if(p!=NULL)count1(p-lchild,num1);if(p-lchild!=NULL&p-rchild=NULL|p-lchild=NULL&p-rchild!=NULL)(*num1)+;count1(p-rchild,num1);int onechild(NODE *t) /统计出二叉树中单孩子的结点数方法2int num1,num2;if(t=NULL) return(0);else
4、 if(t-lchild=NULL&t-rchild!=NULL|t-lchild!=NULL&t-rchild=NULL)return(onechild(t-lchild)+onechild(t-rchild)+1);elsenum1=onechild(t-lchild);num2=onechild(t-rchild);return(num1+num2);int sum(NODE *t) /统计出二叉树中所有结点数if(t=NULL) return(0);else return(sum(t-lchild)+sum(t-rchild)+1);int leaf(NODE *t) /统计出二叉树中
5、叶子结点数if(t=NULL) return(0);else if(t-lchild=NULL&t-rchild=NULL) return(leaf(t-lchild)+leaf(t-rchild)+1);elsereturn(leaf(t-lchild)+leaf(t-rchild);void preorder1(NODE *root) /非递归二叉树前序编历 NODE *p,*s100,*q; /q为p的双亲结点int top=0; /top为栈顶指针p=root;q=p;while(p!=NULL)|(top0) while(p!=NULL)printf(%d ,p-data);s+to
6、p=p; p=p-lchild; p=stop-; p=p-rchild; void delk(NODE *root,char k) /删去并释放数据值为k的叶结点 NODE *p,*s100,*q; /q为p的双亲结点int top=0; /top为栈顶指针if(*root)=NULL)return;if(*root)-lchild=NULL &(*root)-rchild=NULL&(*root)-data=k) *root=NULL;return;p=*root;q=p;while(p!=NULL)|(top0) while(p!=NULL)if(p-lchild=NULL&p-rchi
7、ld=NULL &p-data=k)if(q-lchild=p) q-lchild=NULL;else q-rchild=NULL; free(p);return;s+top=p; q=p; p=p-lchild; p=stop-; q=p;p=p-rchild; void lev_traverse(NODE *T) /按层次从上到下,每层从右到左的顺序列出二叉树所有结点的数据信息NODE *q100,*p;int head,tail;q0=T;head=0;tail=1;while(headdata);if(p-rchild!=NULL)qtail+=p-rchild;if(p-lchild
8、!=NULL)qtail+=p-lchild;int depth(NODE *t) /求二叉树的深度int num1,num2;if(t=NULL) return(0);if(t-lchild =NULL&t-rchild =NULL) return(1);elsenum1=depth(t-lchild );num2=depth(t-rchild );if(num1num2)return(num1+1);elsereturn(num2+1);int onechild3(NODE *root) /非递归统计出二叉树共有多少个度为1的结点 NODE *p,*s100;int top=0,num=0
9、; /top为栈顶指针p=root;while(p!=NULL)|(top0) while(p!=NULL)if(p-lchild!=NULL&p-rchild=NULL |p-lchild=NULL&p-rchild!=NULL)num+;s+top=p; p=p-lchild; p=stop-; p=p-rchild; return num;int like(NODE *t1,NODE *t2) /判定两颗二叉树是否相似int like1,like2;if(t1=t2&t2=NULL) return(1);else if(t1=NULL &t2!=NULL|t1!=NULL&t2=NULL
10、) return(0);elselike1=like(t1-lchild,t2-lchild);like2=like(t1-rchild ,t2-rchild );return(like1&like2);char a100; /数组顺序存储二叉树void change(NODE *t,int i) /将二叉树的链接存储转换为顺序存储 if(t!=NULL) ai=t-data;change(t-lchild,2*i);change(t-rchild,2*i+1);int complete(NODE *t) /判断二叉树是否为完全二叉树int i,flag=0;change(t,1);for(i=1;i100;i+)if(!flag&ai=0) flag=1;if(flag&ai!=0) break;if(i=100) return(1);else return(0);
第六章-树(算法设计)许昌网络公司
