习题课(树与二叉树)

第六章树和二叉树6.33intex633(intu,intv)//判断u是否v的子孙,是返回1,否则返回0{if(u==v)return1;else{if(L[v])if(ex633(u,L[v]))return1;if(R[v])if(ex633(u,R[v]))return1;}return0;}6.34假定用两个一维数组L[N]和R[N]作为有N个结点1，2,…，N的二叉树的存储结构。L[i]和R[i]分别指示结点i的左儿子和右儿子；L[i]=0（R[i]=0）表示i的左（右）儿子为空。试写一个算法，由L和R建立一个一维数组T[N]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。【哈尔滨工业大学1999七(14分)】【华南师范大学2000六(17分)】解：[题目分析]由指示结点i左儿子和右儿子的两个一维数组L[i]和R[i]，很容易建立指示结点i的双亲的一维数组T[i]，根据T数组，判断结点U是否是结点V后代的算法，转为判断结点V是否是结点U的祖先的问题。intGenerate(intU,intV,intN,intL[],intR[],intT[])/*L[]和R[]是含有N个元素且指示二叉树结点i左儿子和右儿子的一维数组，本算法据此建立结点i的双亲数组T，并判断结点U是否是结点V的后代。*/{for(i=1;i=N;i++)T[i]=0;//T数组初始化for(i=1;i=N;i++)//根据L和R填写Tif(L[i]!=0)T[L[i]]=i;//若i的左子女是L，则L的双亲是ifor(i=1;i=N;i++)if(R[i]!=0)T[R[i]]=i;//i的右子女是R，则R的双亲是iintparent=U;//判断U是否是V的后代while(parent!=V&&parent!=0)parent=T[parent];if(parent==V){printf(“结点U是结点V的后代”);return(1);}else{printf(“结点U不是结点V的后代”);return(0);}}//结束Generation6.36intex636(BiTreeT1,BiTreeT2)//判断两棵树是否相似递归算法{if(!T1&&!T2)return1;elseif(!T1||!T2)return0;else{b1=ex636(T1-lchild,T2-lchild);b2=ex636(T1-rchild,T2-rchild);returnb1&&b2;}}6.37voidex637(BiTreeT)//先序遍历二叉树的非递归算法{InitStack(S);Push(S,T);while(!StackEmpty(S)){while(GetTop(S,p)&&p){coutp-data;push(S,p-lchild);}pop(S,p);if(!StackEmpty(S)){pop(S,p);push(S,p-rchild);}}}6.37利用栈的基本操作写出先序遍历二叉树的非递归算法，要求进栈的元素最少。【山东科技大学2002四、(10分)】解：[题目分析]先序遍历二叉树的非递归算法，要求进栈元素少，意味着空指针不进栈。voidPreOrder(Bitreebt)//对二叉树bt进行非递归先序遍历{inttop=0;Bitrees[];//top是栈s的栈顶指针，栈中元素是树结点指针，栈容量足够大while(bt!=null||top0){while(bt!=null){coutbt-data;//访问根结点if(bt-rchlid)s[++top]=bt-rchild;//若有右子女，则右子女进栈bt=bt-lchild;}if(top0)bt=s[top--];}}6.38voidex638(BiTreeT)//后序遍历二叉树的非递归算法,用栈{BiTrees[100];chartag[100];p=T;top=0;do{while(p){tag[top]=’L’;s[top]=p;top++;p=p-lchild;}while(top0&&tag[top-1]==’R’){top--;p=s[top];coutp-data“”;}if(top0){tag[top-1]=’R’;p=s[top-1]-rchild;}}while(top0);}6.43设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild,data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。【福州大学1998四、2(10分)】解：voidexchange(BiTree&bt)//将二叉树bt所有结点的左右子树交换{if(bt){BiTrees；s=bt-lchild;bt-lchild=bt-rchild;bt-rchild=s;//左右子女交换exchange(bt-lchild);//交换左子树上所有结点左右子树exchange(bt-rchild);//交换右子树上所有结点左右子树}}[算法讨论]将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历不适合本题。下面是本题的非递归算法voidexchange(BiTree&bt)//交换二叉树中各结点的左右孩子的非递归算法{inttop=0;BiTrees[],t,p;//s是二叉树的结点指针的栈，容量足够大if(bt){s[++top]=bt;while(top0){t=s[top--];if(t-lchild||t-rchild){p=t-lchild;t-lchild=t-rchild;t-rchild=p;}//交换左右子树if(t-lchild)s[++top]=t-lchild;//左子女入栈if(t-rchild)s[++top]=t-rchild;//右子女入栈}//while(top0)}//if(bt)}//结束exchange6.47voidex647(BiTreeT)//层序遍历二叉树{InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);coutp-data;if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-rchild);}}6.56BiThrTreeex656(BiThrTreep)//在先序后继线索二叉树中查找结点p的先序后继{if(p-ltag==Link)returnp-lchild;elsereturnp-rchild;}6.57BiThrTreeex657(BiThrTreep)//在后序后继线索二叉树中查找结点p的后序后继,并返回指针{if(!p-parent)returnNULL;elseif(p==p-parent-lchild&&p-parent-rchild){q=p-parent-rchild;while(q-lchild||q-rchild)if(q-lchild)q=q-lchild;elseq=q-rchild;returnq;}elsereturnp-parent;}例1．二叉树采用二叉链表存储：（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是二叉树所有层中结点个数的最大值）。【西北大学2001四】解：[题目分析]求二叉树高度的算法略。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。intWidth(BiTreebt)//求二叉树bt的最大宽度{if(bt==null)return(0);//空二叉树宽度为0else{BiTreeQ[];//Q是队列,元素为二叉树结点指针,容量足够大front=1;rear=1;last=1;//front头指针,rear尾指针,last同层最右结点在队列中的位置temp=0;maxw=0;//temp记局部宽度,maxw记最大宽度Q[rear]=bt;//根结点入队列while(front=last){p=Q[front++];temp++;//同层元素数加1if(p-lchild!=null)Q[++rear]=p-lchild;//左子女入队if(p-rchild!=null)Q[++rear]=p-rchild;//右子女入队if(frontlast)//一层结束{last=rear;if(tempmaxw)maxw=temp;//last指向下层最右元素,更新当前最大宽度temp=0;}//if}//whilereturn(maxw);}//结束width例2．要求二叉树按二叉链表形式存储，（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。【西北大学2000六(12分)】【青岛海洋大学1999六(15分)】【南京航空航天大学2001十(10分)】【北方交通大学1997八(20分)】【哈尔滨工业大学2000十一(14分)】【南开大学1997四(16分)】【北京邮电大学1994九(20分)】解：[题目分析]二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。BiTreeCreat()//建立二叉树的二叉链表形式的存储结构{intx；BiTreebt;scanf(“%d”,&x);//本题假定结点数据域为整型if(x==0)bt=null;elseif(x0){bt=(BiNode*)malloc(sizeof(BiNode));bt-data=x;bt-lchild=creat();bt-rchild=creat();}elseerror(“输入错误”)；return(bt);}//结束BiTreeintJudgeComplete(BiTreebt)//判断二叉树是否是完全二叉树,如是，返回1，否则，返回0{inttag=0;BiTreep=bt,Q[];//Q是队列，元素是二叉树结点指针，容量足够大if(p==null)return(1);InitQueue(Q);EnQueue(Q,p);//初始化队列，根结点指针入队while(!QueueEmpty(Q)){p=DeQueue(Q);//出队if(p-lchild&&!tag)EnQueue(Q,p-lchild);//左子女入队else{if(p-lchild)return0;//前边已有结点为空，本结点不空elsetag=1;//首次出现结点为空if(p-rchild&&!tag)EnQueue(Q,p-rchild);//右子女入队elseif(p-rchild)return0;elsetag=1;}//whilereturn1;}//JudgeComplete[算法讨论]完全二叉树证明还有其它方法。判断时易犯错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。例3．已知一棵二叉树的中序序列和后序序列，写一个建立该二叉树的二叉链表存储结构的算法。【东北大学1999六、3（12分）】解：BiTreeIntoPost(ElemTypein[],ElemTypepost[],intl1,inth1,intl2,inth2)/*in和post是二叉树的中序序列和后序序列,l1,h1,l2,h2分别是两序列第一和最后结点的下标*/{BiTreebt=(BiTree)malloc(sizeof(BiNode