数据结构习题解析与实训 第六章.doc

《数据结构习题解析与实训 第六章.doc》由会员分享，可在线阅读，更多相关《数据结构习题解析与实训 第六章.doc（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章 树和二叉树这一章的重点是二叉树。通过本章的习题可以在机器上运行程序,以验证二叉树的各种遍历算法和在二叉树上的各种操作,包括二叉树左右子树交换、求二叉树叶子结点个数、求二叉树的深度、求某结点的双亲结点等。二叉树的存储结构采用二叉链表,结构如下所示。#defineDATATYPE2chartypedefstructnode1DATATYPE2data;structnode1lchild,rchild;BTCHINALR;要实现在二叉树上的各种操作,首先应将二叉树以上述的二叉链表结构在内存中建立起来,而后在其上面进行各种操作。下面提供一个建立二叉树的函数,供各应用程序调用,函数源程序以“二叉

2、树.c”为名放在光盘上。“二叉树.c”源代码如下所示。BTCHINALRcreatebt()BTCHINALRq;structnode1s50;intj,i,x;printf(建立二叉树,输入结点对应的编号和值nn);printf(i,x=);scanf(%d,%c,&i,&x);while(i!=0&x!=)q=(BTCHINALR)malloc(sizeof(BTCHINALR);/建立一个新结点q/q-data=x;q-lchild=NULL;q-rchild=NULL;si=q;/q新结点地址存入s指针数组中/if(i!=1)/i=1,q结点是根结点/j=i/2;/否则求q结点的双亲结

3、点的编号j/l62数据结构习题解析与实训if(i%2=0)sj-lchild=q;/q结点编号为偶数则挂在双亲结点j的左边/elsesj-rchild=q;/q结点编号为奇数则挂在双亲结点j的右边/printf(i,x=);scanf(%d,%c,&i,&x);returns1;/返回根结点地址/下面举例说明二叉树的建立。设有一棵二叉树如图61(a)所示,将二叉树模拟为完全二叉树从根开始对结点进行编号,编号从1开始,结果如图61(b)所示。在运行过程中要求输入结点对应的编号和值时,请按图61(c)中的数据输入,最后以编号i=0;结点值x=结束。图6.1二叉树的建立6.1习题解析【习题1】二叉树

4、中序遍历题目要求:对建立的二叉树进行中序遍历,并输出遍历结果。中序遍历算法可以用递归算法实现,也可以用非递归算法实现。建立二叉树的函数放在“二叉树.c”源程序中。以下各例中均如此。【解答】#include#includedatastru.h#include#include二叉树.cvoidinorder(BTCHINALRbt)/中序遍历二叉树(递归算法)/if(bt!=NULL)inorder(bt-lchild);第6章树和二叉树l63printf(%c,bt-data);inorder(bt-rchild);voidinorder_notrecursive(BTCHINALRbt)/中序

5、遍历二叉树(非递归算法)/BTCHINALRq,s20;inttop=0;intbool=1;q=bt;dohile(q!=NULL)top+;stop=q;q=q-lchild;if(top=0)bool=0;elseq=stop;top-;printf(%c,q-data);q=q-rchild;while(bool);main()TCHINALRbt;charch;inti;bt=createbt();i=1;whil(i)printf(n中序遍历二叉树(递归按y键,非递归按n键):);fflush(stdin);scanf(%c,&ch);if(ch=y)inorder(bt);els

6、einorder_notrecursive(bt);printf(n);printf(n继续操作吗?(继续按1键,结束按0键):);fflush(stdin);scanf(%d,&i);【习题2】求二叉树叶子结点数题目要求:计算二叉树叶子结点数。计算二叉树叶子结点数的算法很多,既可用递归算法实现,也可用非递归算法实现。该例用递归算法实现。【解答】#include#includedatastru.hl64数据结构习题解析与实训#include#include二叉树.cintleaf(BTCHINALRbt)if(bt=NULL)return0;elsef(bt-lchild=NULL&bt-rc

7、hild=NULL)return1;elsereturn(leaf(bt-lchild)+leaf(bt-rchild);main()TCHINALRbt;intleafnum;bt=createbt();leafnum=leaf(bt);printf(n二叉树的叶子结点数=%dnn,leafnum);【习题3】求二叉树深度题目要求:计算二叉树深度,树根为第一层。【解答】#include#includedatastru.h#include#include二叉树.cinttreehight(BTCHINALRbt)intlh,rh,h;if(bt=NULL)h=0;elseh=treehight

8、(bt-lchild);rh=treehight(bt-rchild);h=(lhrh?lh:rh)+1;returnh;main()TCHINALRbt;inttreeh;bt=createbt();treeh=treehight(bt);第6章树和二叉树l65printf(n二叉树深度=%dnn,treeh);【习题4】二叉树左右子树交换题目要求:从二叉树的根结点开始,将每一个结点的左右子树交换。为验证算法的正确性,程序将显示交换前及交换后的二叉树的中序遍历结果。二叉树左右子树交换算法用递归算法实现。前面图61(a)例举的二叉树在运行本算法后的新二叉树如图62所示。运行过程如图63所示。图

9、6.2更新的二叉树图6.3二叉树左右子树交换运行过程【解答】#includedatastru.h#include#include#include二叉树.cl66数据结构习题解析与实训BTCHINALRchange(BTCHINALRbt)/二叉树左右子树交换递归算法/BTCHINALRp;if(bt!=NULL)if(bt-lchild!=NULL|bt-rchild!=NULL)p=(BTCHINALR)malloc(sizeof(BTCHINALR);p-data=bt-data;p-rchild=NULL;p-lchild=bt-lchild;bt-lchild=bt-rchild;bt

10、-rchild=p-lchild;bt-lchild=change(bt-lchild);bt-rchild=change(bt-rchild);returnbt;voidinorder(BTCHINALRbt)/中序遍历二叉树(递归算法)/if(t!=NULL)inorder(bt-lchild);printf(%c,bt-data);inorder(bt-rchild);main()BTCHINALRbt;bt=createbt();printf(n二叉树左右子树交换前中序遍历:);inorder(bt);printf(n);bt=change(bt);printf(n二叉树左右子树交换后

11、中序遍历:);inorder(bt);printf(n);【习题5】查找给定结点题目要求:设二叉树中结点值互不相同,即各值具有惟一性。输入一给定值,确定给定值对应的结点是否在二叉树中存在。第6章树和二叉树l67【解答】#includedatastru.h#include#include#include二叉树.cBTCHINALRsearch_ch(BTCHINALRcur,charx)/先序查找/BTCHINALRtemp;if(cur=NULL)returnNULL;if(x=cur-data)returncur;temp=search_ch(cur-lchild,x);if(temp!=N

12、ULL)returntemp;elsereturnsearch_ch(cur-rchild,x);main()TCHINALRbt,p;charch;inti;bt=createbt();fflush(stdin);i=1;while(i)printf(输入待查结点数据:);scanf(%c,&ch);p=search_ch(bt,ch);if(p=NULL)printf(无此结点nn);elseprintf(结点存在nn);printf(n继续操作吗?(继续按1键,结束按0键):n);fflush(stdin);scanf(%d,&i);fflush(stdin);printf(n);【习题

13、6】查找给定结点的双亲结点题目要求:实现此功能是基于上一算法的基础,当确定给定结点存在二叉树中,则输出该结点的双亲结点;如果给定结点是根结点,则给出相应的提示信息。【解答】#includedatastru.h#include#include#include二叉树.cBTCHINALRsearch_ch(BTCHINALRcur,charx)l68数据结构习题解析与实训/先序查找:在以cur为根的子树中查找值为x的结点是否存在/BTCHINALRtemp;if(cur=NULL)returnNULL;if(x=cur-data)returncur;temp=search_ch(cur-lchil

14、d,x);if(temp!=NULL)returntemp;elsereturnsearch_ch(cur-rchild,x);BTCHINALRparent(BTCHINALRstart,BTCHINALRcurrent)/从start所指结点起查找当前结点current的父亲结点/BTCHINALRp;if(start=NULL)returnNULL;if(start-lchild=current|start-rchild=current)returnstart;p=parent(start-lchild,current);if(p!=NULL)returnp;elsereturnpare

15、nt(start-rchild,current);main()BTCHINALRbt,p,temp;charch;inti;bt=createbt();/建立二叉树,根为bt/fflush(stdin);i=1;while(i)printf(n输入结点数据:);scanf(%c,&ch);p=search_ch(bt,ch);if(p=NULL)printf(n无此结点nn);elseif(p=bt)printf(n无双亲结点,是根结点nn);elseemp=parent(bt,p);printf(n%c的双亲结点是%cnn,ch,temp-data);printf(n继续操作吗?(继续按1键

16、,结束按0键):n);fflush(stdin);scanf(%d,&i);fflush(stdin);printf(n);第6章树和二叉树l69【习题7】人机下棋题目要求:这是一个井字游戏人机下棋的程序,游戏程序的逻辑思路采用树形结构图6.4棋盘格式图示分析法,参见图64图69。1.游戏规则棋盘格式如图64所示。参加者:人、计算机。人和计算机在棋盘上交替走步,约定使用的符号计算机用“x”,人用“o”,谁使棋盘一条线上的3点为己方符号,则谁胜。2.程序要求按游戏树法则编程,使用求值函数计算;要求下棋深度至少考虑一步,程序结果只能是计算机胜或平局;开始由哪一方先走可以选择。3.算法辅导(1)从初

17、始状态开始,有3种不同的走法。中间m1;四角m2;边中间m3。图6.53种走法(2)计算机考虑的优先级次序为:已有一行3个对方的符号,已输;已有一行3个自己的符号,已赢;建立一行包括3个自己的符号;阻止对方形成一行3个对方的符号(即在计算机下了一步以后,对方不应出现在一行上有两个对方符号和一个空格的情况);建立一行包括两个自己的符号和一个空格;阻止对方形成一行两个对方符号和一个空格;建立一行包括一个自己的符号和两个空格。(3)变量规定:n3存放一行3个“o”的行数;c3存放一行3个“x”的行数;n2存放一行两个“o”的行数(另一个为空格);c2存放一行两个“x”的行数(另一个为空格);n1存放

18、一行只有一个“o”的行数(另两个为空格);c1存放一行只有一个“x”的行数(另一个为空格)。图66中c1=2,n1=3,c2=n2=c3=n3=0。l70数据结构习题解析与实训图67中c1=3,n1=1,n2=1,c2=c3=n3=0。虚线是由“x”符号组成的行,实线是由“o”符号组成的行。图66图674.求值函数y=k3c3-k2n2+k2c2-k1n1+k1c1其中:k3,k2,k2,k1,k1是常数,分别可取128,63,31,15,7。其中:k3可以任取,其他值满足下列不等式。k32k2,k22k2,k22k1,k12k15.最佳移动如何确定(观察深度为一步的移动)图6.8最佳移动在计

19、算机所有可能走步构成的树中,把求值函数用于终端结点,分别求出s1,s2,s3的值,值最大的走步对计算机最有利,即可确定走这一步。如果人先走,设人走在6号位,则计算机所有可能走的棋步如图69所示,将求值函数用于终端结点,求出终端结点对应的函数值,取其中最大值对应的走步为计算机走步。图6.9最佳移动的应对【解答】#include第6章树和二叉树l71typedefcharchess10;typedefinttemparr10;chessarr;temparrbrr;intnumber,suc,c3,n2,c2,n1,c1;charch;voidinarrdata(chessa)1=1;a2=2;a

20、3=3;a4=4;a5=5;a6=6;a7=7;a8=8;a9=9;voiddisplay(chessa)printf(棋盘显示n);printf(n);printf(n);printf(%c|%c|%cn,a1,a2,a3);printf(n);printf(%c|%c|%cn,a4,a5,a6);printf(n);printf(%c|%c|%cn,a7,a8,a9);printf(n);printf(n);intarrfull()nti;intarrf=0;for(i=1;i=9;i+)if(i=arri-48)arrf=1;returnarrf;voidcn(intline)switc

21、h(line)ase0:c3=c3+1;break;case1:n2=n2+1;break;case2:c2=c2+1;break;case3:n1=n1+1;break;case4:c1=c1+1;break;l72数据结构习题解析与实训intlinenum(chara,charb,charc)intln=5;if(=X)&(b=X)&(c=X)ln=0;if(a=O)&(b=O)&(c!=O)|(a=O)&(b!=O)&(c=O)|(a!=O)&(b=O)&(c=O)ln=1;if(a=X)&(b=X)&(c!=X)|(a=X)&(b!=X)&(c=X)|(a!=X)&(b=X)&(c=X

22、)ln=2;if(a=O)&(b!=O)&(c!=O)|(a!=O)&(b=O)&(c!=O)|(a!=O)&(b!=O)&(c=O)ln=3;if(a=X)&(b!=X)&(c!=X)|(a!=X)&(b=X)&(c!=X)|(a!=X)&(b!=X)&(c=X)ln=4;returnln;intmaxbrr(intbr)nttemp,i,mb;temp=-888;for(i=1;i=9;i+)iftemp=bri)temp=bri;mb=i;returnmb;voidmanstep()/人走棋处理模块/ntj;display(arr);if(arrfull()/如果棋盘上还有可下棋的位置,

23、给人走一步棋/第6章树和二叉树l73printf(输入下一步对应位置编号:);scanf(%d,&j);printf(n);while(j9)|(j!=arrj-48)printf(输入错误,重新输入:);scanf(%d,&j);arrj=0;voidcomputerstep()/计算机走棋处理模块/inti;ifarrfull()/如果棋盘上还有可下棋的位置,则计算机走一步棋/for(i=1;i=9;i+)/对每一步可走棋的位置进行计算/if(i=arri-48)3=0;n2=0;c2=0;n1=0;c1=0;arri=X;number=linenum(arr1,arr2,arr3);cn

24、(number);number=linenum(arr4,arr5,arr6);cn(number);number=linenum(arr7,arr8,arr9);cn(number);number=linenum(arr1,arr4,arr7);cn(number);number=linenum(arr2,arr5,arr8);cn(number);number=linenum(arr3,arr6,arr9);cn(number);number=linenum(arr1,arr5,arr9);cn(number);number=linenum(arr3,arr5,arr7);cn(numbe

25、r);brri=(128c3-63n2+31c2-15n1+7c1);/计算此步权值/arri=i+48;elsebrri=-999;arrmaxbrr(brr)=X;/确定计算机走哪一步:权值最大的一步/c3=0;n2=0;c2=0;n1=0;c1=0;number=linenum(arr1,arr2,arr3);cn(number);number=linenum(arr4,arr5,arr6);cn(number);number=linenum(arr7,arr8,arr9);cn(number);number=linenum(arr1,arr4,arr7);cn(number);numb

26、er=linenum(arr2,arr5,arr8);cn(number);number=linenum(arr3,arr6,arr9);cn(number);number=linenum(arr1,arr5,arr9);cn(number);number=linenum(arr3,arr5,arr7);cn(number);if(c3!=0)/计算机已胜/isplay(arr);l74数据结构习题解析与实训printf(n);printf(计算机胜!nnn);fflush(stdin);suc=0;elsesuc=0;main()inarrdata(arr);/棋盘坐标编号/display(

27、arr);/显示初始坐标/suc=1;printf(你先走吗?(y/n);scanf(%c,&ch);printf(n);if(ch=y)|(ch=Y)/人先走棋/while(suc)manstep();computerstep();display(arr);elsewhile(suc)/计算机先走棋/omputerstep();if(suc)manstep();6.2实训练习题【习题8】二叉树先序遍历题目要求:对建立的二叉树进行先序遍历,并输出遍历结果。先序遍历算法可以用递归算法实现,也可以用非递归算法实现。建立二叉树的函数放在“二叉树.c”源程序中。请学生参考中序遍历程序在二叉树上实现先序

28、遍历程序。【习题9】二叉树后序遍历题目要求:对建立的二叉树进行后序遍历,并输出遍历结果。请学生参考中序遍历程序完成二叉树上的后序遍历程序。建立二叉树的函数放在“二叉树.c”源程序中。后序遍历程序的非递归算法实现较为复杂,在此,只须考虑递归算法实现。第6章树和二叉树l75【习题10】求二叉树叶子结点题目要求:计算二叉树叶子结点数的算法很多,至少有六七种算法。【习题2】中采用了递归算法中的一种算法实现。请学生编写实现这一操作的其他算法程序(两个以上)并上机调试。【习题11】判断二叉树是否是满二叉树题目要求:判断二叉树是否是满二叉树,有多种算法处理。下面介绍一种算法:对建立的二叉树计算其结点数nodenum和其深度treedeg,如果nodenum=2treedeg-1,则该二叉树是满二叉树,否则不是。建立二叉树的函数放在“二叉树.c”源程序中。【习题12】求给定结点的祖先结点题目要求:求给定结点的祖先结点可基于【习题6】查找给定结点的双亲结点的程序思路。如果给定结点存在且又是根结点,则该结点无祖先结点;如果给定结点存在但不是根结点,则查找给定结点的双亲结点,再查找双亲结点的双亲结点,一直查找到根结点为止,即求得给定结点的全部祖先结点。建立二叉树的函数放在“二叉树.c”源程序中。