第5章 树、二叉树和森林-V0.1

数据结构实验指导与习题解答——Python语言描述张光河

主编guanghezhang@163.com人民邮电出版社2022年09月1ISBN：978-7-115-56280-7ISBN：978-7-115-56280-7ISBN：978-7-115-48577-9配套教材主教材主教材与配套教材2第五章树、二叉树和森林3习题解答5.3综合实验5.2基础实验5.1目录CONTENTS45.1基础实验55.1.1实现有向图的各种基本操作基础实验1基础实验25.1.25.1.35.1.4实现无向图的各种基本操作实现图的深度优先遍历实现图的广度优先遍历基础实验3基础实验4

基础实验1实现树的各种基本操作6理解树的存储结构，并掌握树的基本操作。实验目的实验内容创建名为ex050601_01.py的文件，在文件中定义两个类，一个是树的结点类，该类包含结点的相关信息（如结点的值和所有的子树）；另一个是树的类，该类包含树的定义及其基本操作。请按以下步骤测试树的基本操作的实现是否正确。（1）初始化一个结点。（2）以（1）中结点作为根结点，使用递归算法创建一棵（3）对树执行先序遍历，并将先序序列输出。（4）对树执行后序遍历，并将后序序列输出。（5）对树执行层次遍历，并将所得序列输出。（6）计算树的深度并输出。（7）插入值为G的结点，使其是值为D的结点的第一个孩子结点。图5-1（主教材图5-48）一棵树71########################2#文件名：ex050601_01.py3#版本号：0.14#创建时间：2019-04-265########################6#类名称：TreeNode7#类说明：定义三叉树结构8#类释义：定义数据结点类型9########################10classTreeNode(object):11def__init__(self,value=None):12self.child_list=[]13self.value=value14defadd_child(self,node):15self.child_list.append(node)16########################17#类名称：SequenceBinaryTree18#类说明：定义一棵顺序存储的树19#类释义：创建一棵树，并对其执行相关操作。20########################21classTree(object):22defCreateTree(self):23root=TreeNode('A')24B=TreeNode('B')25root.add_child(B)实验代码826C=TreeNode('C')27root.add_child(C)28root.add_child(TreeNode('D'))29B.add_child(TreeNode('E'))30C.add_child(TreeNode('F'))31returnroot32###########################33#树的先序遍历函数34###########################35defPreOrder(self,root):36ifrootisNone:37return[]38stack,output=[root,],[]39whilestack:40root=stack.pop()41output.append(root.value)42stack.extend(root.child_list[::-1])43returnoutput44###########################45#后序遍历递归算法46###########################47defPostOrder(self,root):48ifrootisNone:49return[]50stack,output=[root,],[]951whilestack:52root=stack.pop()53ifrootisnotNone:54output.append(root.value)55forjinroot.child_list:56stack.append(j)57returnoutput[::-1]58###########################59#树的层次遍历函数60###########################61defFloorOrder(self,root):62ifrootisNone:63return[]64result=[]65previous_layer=[root]66#层次遍历开始67whileprevious_layer:68current_layer=[]69result.append([])70fornodeinprevious_layer:71result[-1].append(node.value)72current_layer.extend(node.child_list)73previous_layer=current_layer74returnresult75###########################1076#计算三叉树的深度函数77###########################78defGetTreeDepth(self,root):79ifrootisNone:80return081elifroot.child_list==[]:82return183else:84height=[self.GetTreeDepth(j)forjinroot.child_list]85returnmax(height)+186###########################87#插入值为G的结点的函数88###########################89definsertNode(self,root):90G=TreeNode('G')91foriinroot.child_list:92ifi.value=='D':93i.add_child(G)94returnroot95########################96#输出函数97########################98defPrintOut(self):99print('创建一棵树')100print('A')11101print('/|\\')102print('BCD')103print('||')104print('EF')105tree=self.CreateTree()106print('对树进行先序遍历：’)107print(self.PreOrder(tree))108print('\n对树进行后序遍历：’)109print(self.PostOrder(tree))110print('\n对树进行层次遍历：’)111print(self.FloorOrder(tree))112print('\n三叉树的深度：’)113print(self.GetTreeDepth(tree))114print('\n插入值为G的结点：’)115print('\n插入值为G的结点后层次遍历的结果：')116print(self.FloorOrder(self.insertNode(tree)))117if__name__=='__main__':118T=Tree()119T.PrintOut()

基础实验2实现二叉树的各种基本操作12理解二叉树的链式存储结构，并掌握二叉树的基本操作。实验目的实验内容创建名为ex050601_02.py的文件，在文件中定义两个类，一个是二叉树的结点类，该类包含结点的相关信息（如结点的值和左、右子树）；另一个是二叉树的类，该类包含二叉树的定义及其基本操作。请按以下步骤测试二叉树的基本操作的实现是否正确。（1）初始化一个结点。（2）以（1）中结点作为根结点并使用链式存储结构，递归创建一棵图5-2（教材P267图5-49）所示的二叉树。（3）对二叉树执行先序遍历，并将先序序列输出。（4）对二叉树执行中序遍历，并将中序序列输出。（5）对二叉树执行后序遍历，并将后序序列输出。（6）对二叉树执行层次遍历，并将所得序列输出。（7）获取值为F的结点，并将其值修改为Z。（8）为值为G的结点添加右孩子，令其值为K。图5-2（教材图5-49）一棵二叉树131###########################2#文件名：ex050601_023#版本号：0.14#创建时间：2019-04-265###########################6#类名称：BinaryTreeNode7#类说明：定义二叉树的一个结点8#类释义：分别有左孩子LeftChild，右孩子RightChild和结点值data9###########################10classBinaryTreeNode(object):11def__init__(self):12self.data='#'13self.LeftChild=None14self.RightChild=None15###########################16#类名称：CircularSequenceQueue17#类说明：定义一个循环队列18#类释义：提供循环顺序队列的相关操作19###########################20classCircularSequenceQueue:21############################22#默认的初始化循环队列的函数23############################24def__init__(self):25self.MaxQueueSize=4实验代码1426self.s=[Noneforxinrange(0,self.MaxQueueSize)]27self.front=028self.rear=029############################30#初始化循环队列的函数31############################32defInitQueue(self,Max):33self.MaxQueueSize=Max34self.s=[Noneforxinrange(0,self.MaxQueueSize)]35self.front=036self.rear=037#############################38#判断循环队列是否为空的函数39#############################40defIsEmptyQueue(self):41ifself.front==self.rear:42iQueue=True43else:44iQueue=False45returniQueue46#############################47#元素入队的函数48#############################49defEnQueue(self,x):50if(self.rear+1)%self.MaxQueueSize!=self.front:1551self.rear=(self.rear+1)%self.MaxQueueSize52self.s[self.rear]=x53else:54print("队列已满，无法入队")55return56#############################57#元素出队的函数58#############################59defDeQueue(self):60ifself.IsEmptyQueue():61print("队列为空，无法出队")62return63else:64self.front=(self.front+1)%self.MaxQueueSize65returnself.s[self.front]66#############################67#类名称：BinaryTree68#类说明：定义一棵二叉树69#类释义：提供二叉树的相关操作70#############################71classBinaryTree(object):72############################73#创建二叉树函数74############################75defCreateBinaryTree(self,Root):1676data=input('->')77ifdata=='#':78Root=None79else:80Root.data=data81Root.LeftChild=BinaryTreeNode()82self.CreateBinaryTree(Root.LeftChild)83Root.RightChild=BinaryTreeNode()84self.CreateBinaryTree(Root.RightChild)85###########################86#先序遍历递归算法87###########################88defPreOrder(self,Root):89ifRootisnotNone:90self.VisitBinaryTreeNode(Root)91self.PreOrder(Root.LeftChild)92self.PreOrder(Root.RightChild)93###########################94#中序遍历递归算法95###########################96defInOrder(self,Root):97ifRootisnotNone:98self.InOrder(Root.LeftChild)99self.VisitBinaryTreeNode(Root)100self.InOrder(Root.RightChild)17101###########################102#后序遍历递归算法103###########################104defPostOrder(self,Root):105ifRootisnotNone:106self.PostOrder(Root.LeftChild)107self.PostOrder(Root.RightChild)108self.VisitBinaryTreeNode(Root)109###########################110#层次遍历二叉树的函数111###########################112defLevelOrder(self,Root):113tSequenceQueue=CircularSequenceQueue()114tSequenceQueue.InitQueue(100)115tSequenceQueue.EnQueue(Root)116tTreeNode=None117whiletSequenceQueue.IsEmptyQueue()==False:118tTreeNode=tSequenceQueue.DeQueue()119self.VisitBinaryTreeNode(tTreeNode)120iftTreeNode.LeftChildisnotNone:121tSequenceQueue.EnQueue(tTreeNode.LeftChild)122iftTreeNode.RightChildisnotNone:123tSequenceQueue.EnQueue(tTreeNode.RightChild)124########################125#遍历二叉树一个结点函数18126########################127defVisitBinaryTreeNode(self,BinaryTreeNode):128#值为#的结点代表空结点129ifBinaryTreeNode.data!='#':130print(BinaryTreeNode.data,end="")131###########################132#修改指定结点值算法133###########################134defModifyNode(self,Root):135ifRootisnotNone:136self.FindNodeF(Root)137self.ModifyNode(Root.LeftChild)138self.ModifyNode(Root.RightChild)139###########################140#查找结点F算法141###########################142defFindNodeF(self,BinaryTreeNode):143ifBinaryTreeNode.data=='F':144BinaryTreeNode.data='Z'145###########################146#插入指定结点值算法147###########################148defInsertNode(self,Root):149ifRootisnotNone:150self.FindNodeG(Root)19151self.InsertNode(Root.LeftChild)152self.InsertNode(Root.RightChild)153###########################154#查找结点G算法155###########################156defFindNodeG(self,Node):157ifNode.data=='G':158Node.RightChild=BinaryTreeNode()159Node.RightChild.data='K'160#####################################161#输出函数162#####################################163defPrintOut(self):164print("******************************************************")165print("**********基础实验2实现二叉树的各种基本操作**********")166print("\n（1）初始化根结点：”,end="")167try:168self.__init__()169print("树初始化成功！")170except:171print("树初始化失败！")172173print("\n（2）递归算法创建一棵树。")174print('创建一棵二叉树\n')175print('A')20176print('/\\')177print('BC')178print('/\\/\\')179print('DEFG')180print('/\\/')181print('HIJ')182print('ABDH###E#I##CFJ###G##')183#创建一棵二叉树184print('请仿照上述序列，输入某一二叉树中各结点的值（#表示空结点），每输入一个值按回车换行：')185try:186self.CreateBinaryTree(BinaryTreeNode)187print("二叉树创建完成！”)188exceptValueError:189print("输入有误，请重新输入！”)190self.CreateBinaryTree(BinaryTreeNode)191print("\n（3）对二叉树进行前序遍历：”)192try:193self.PreOrder(BinaryTreeNode)194exceptValueError:195print("遍历出错！”)196print("\n\n（4）对二叉树进行中序遍历：”)197try:198self.InOrder(BinaryTreeNode)199exceptValueError:200print("遍历出错！”)21201print("\n\n（5）对二叉树进行后序遍历：”)202try:203self.PostOrder(BinaryTreeNode)204exceptValueError:205print("遍历出错！”)206print("\n\n（6）对二叉树进行层次遍历：”)207try:208self.LevelOrder(BinaryTreeNode)209exceptValueError:210print("遍历出错！”)211print("\n\n（7）获取值为F的结点，并将其值修改为Z。")212try:213self.ModifyNode(BinaryTreeNode)214exceptValueError:215print("修改出错！”)216print("修改F后的二叉树前序遍历结果为：”)217self.PreOrder(BinaryTreeNode)218print("\n\n（8）为值为G的结点添加右孩子，令其值为K。")219try:220self.InsertNode(BinaryTreeNode)221exceptValueError:222print("插入出错！”)223print("插入后的二叉树前序遍历结果为：”)224self.PreOrder(BinaryTreeNode)225if__name__=='__main__':22226bT=BinaryTree()227bT.PrintOut()

基础实验3实现线索二叉树的各种基本操作23理解线索二叉树的基本概念，掌握线索二叉树的基本操作。实验目的实验内容创建名为ex050601_03.py的文件，在文件中定义两个类，一个是线索二叉树的结点类，该类包含结点的相关信息（如结点的值和左、右子树）；另一个是线索二叉树的类，该类包含线索二叉树的定义及其基本操作。请按以下步骤测试线索二叉树的基本操作的实现是否正确。（1）初始化一个结点。（2）以（1）中结点作为根结点并使用链式存储结构，递归创建一棵图5-2所示的二叉树。（3）中序线索化（2）中的二叉树，使其成为一棵带头结点的中序线索二叉树。（4）遍历（3）中的中序线索二叉树，要求起点为该中序线索二叉树对应的中序序列的最后一个结点，最后将遍历所得序列输出。（5）为值为G的结点添加右孩子，令其值为K，并修改相应结点的线索。241###########################2#文件名：ex050601_033#版本号：0.14#创建时间：2019-05-055###########################6#类名称：BinaryTreeNodeThread7#类说明：定义线索化二叉树的结点8#类释义：二叉树中的每一个结点包含左孩子LeftChild，右孩子RightChild9#数据data,左标志LTag和右标志RTag。10###########################11classBinaryTreeNodeThread(object):12def__init__(self):13self.data='#'14self.LeftChild=None15self.RightChild=None16self.LTag=017self.RTag=018###########################19#类名称：BinaryTree20#类说明：定义一棵二叉树21#类释义：包括创建二叉树、对二叉树线索化、中序遍历线索二叉树等基本操作22###########################23classBinaryTree(BinaryTreeNodeThread):实验代码2524##############################25#初始化该树，创建该树的头结点26##############################27def__init__(self):28self.HeadNode=BinaryTreeNodeThread()29self.HeadNode.LTag=030self.HeadNode.RTag=131self.HeadNode.RightChild=self.HeadNode32########################33#创建二叉树的函数34########################35defCreateBinaryTree(self,BinaryTree):36data=input('->')37ifdata=='#':38BinaryTree=None39else:40BinaryTree.data=data41BinaryTree.LeftChild=BinaryTreeNodeThread()42self.CreateBinaryTree(BinaryTree.LeftChild)43BinaryTree.RightChild=BinaryTreeNodeThread()44self.CreateBinaryTree(BinaryTree.RightChild)45##########################################46#遍历中序线索二叉树的算法47##########################################48defInOrderClue(self):49BinaryTreeNode=self.HeadNode.LeftChild2650whileBinaryTreeNodeisnotself.HeadNode:51whileBinaryTreeNode.LTag==0:52BinaryTreeNode=BinaryTreeNode.LeftChild53self.VisitBinaryTreeNode(BinaryTreeNode)54whileBinaryTreeNode.RTag==1andBinaryTreeNode.RightChildisnotself.HeadNode:55BinaryTreeNode=BinaryTreeNode.RightChild56self.VisitBinaryTreeNode(BinaryTreeNode)57BinaryTreeNode=BinaryTreeNode.RightChild58########################59#访问线索二叉树一个结点60########################61defVisitBinaryTreeNode(self,BinaryTreeNode):62#值为#的结点代表空结点63ifBinaryTreeNode.data!='#':64print(BinaryTreeNode.data,end="")65forward=None66####################################67#建立中序线索二叉树的函数68####################################69defInOrderThreading(self,Root):70ifRootisNone:71self.HeadNode.LeftChild=self.HeadNode72else:73self.HeadNode.LeftChild=Root2774self.forward=self.HeadNode75self.InThreading(Root)76self.forward.RTag=177self.forward.RightChild=self.HeadNode78self.HeadNode.RightChild=self.forward79################################80#中序线索化二叉树的函数81################################82defInThreading(self,BinaryTreeNode):83ifBinaryTreeNodeisnotNone:84self.InThreading(BinaryTreeNode.LeftChild)85ifBinaryTreeNode.LeftChildisNone:86BinaryTreeNode.LTag=187BinaryTreeNode.LeftChild=self.forward88ifself.forward.RightChildisNone:89self.forward.RTag=190self.forward.RightChild=BinaryTreeNode91self.forward=BinaryTreeNode92self.InThreading(BinaryTreeNode.RightChild)93###########################94#插入指定结点值算法95###########################96defInsertNode(self):97BinaryTreeNode=self.HeadNode.LeftChild98whileBinaryTreeNodeisnotself.HeadNode:2899whileBinaryTreeNode.LTag==0:100BinaryTreeNode=BinaryTreeNode.LeftChild101self.FindNodeG(BinaryTreeNode)102whileBinaryTreeNode.RTag==1andBinaryTreeNode.RightChildisnotself.HeadNode:103BinaryTreeNode=BinaryTreeNode.RightChild104self.FindNodeG(BinaryTreeNode)105BinaryTreeNode=BinaryTreeNode.RightChild106###########################107#查找结点G算法108###########################109defFindNodeG(self,BinaryTreeNode):110#值为#的结点代表空结点111ifBinaryTreeNode.data=='G':112BinaryTreeNode.RTag=0113BinaryTreeNode.RightChild=BinaryTreeNodeThread()114BinaryTreeNode.RightChild.data='K'115BinaryTreeNode.RightChild.LTag=1116BinaryTreeNode.RightChild.LeftChild=BinaryTreeNode117BinaryTreeNode.RightChild.RTag=1118BinaryTreeNode.RightChild.RightChild=self.HeadNode119self.HeadNode.RightChild=BinaryTreeNode.RightChild120###########################121#输出函数122###########################29123defPrintOut(self):124bTN=BinaryTreeNodeThread()125print("*****************************************************")126print("*******基础实验3实现线索二叉树的各种基本操作*******")127print('(1)创建一棵二叉树')128print('A')129print('/\\')130print('BC')131print('/\\/\\')132print('DEFG')133print('/\\/')134print('HIJ')135print('ABDH###E#I##CFJ###G##')136#创建一棵二叉树并线索化137print('请仿照上述序列,输入某一二叉树中各结点的值(#表示空结点),每输入一个值按回车换行：')138self.CreateBinaryTree(bTN)139print('\n(2)线索化二叉树！')140self.InOrderThreading(bTN)141print('\n(3)遍历中序线索二叉树！’)142self.InOrderClue()143print('\n(4)为值为G的结点添加右孩子，令其值为K。')144self.InsertNode()145print('插入K后的线索二叉树遍历结果为：’)146self.InOrderClue()147if__name__=='__main__':30148bT=BinaryTree()149bT.PrintOut()

基础实验4实现树、森林和二叉树之间的相互转换31理解并掌握树、森林和二叉树的相互转换。实验目的实验内容创建名为ex050601_04.py的文件，在文件中定义如下5个类。（1）树的结点的类，该类包含结点的相关信息（如结点的值和所有子树）。（2）树的类，该类包含树的定义及其基本操作。（3）森林的类，该类包含森林的定义及其基本操作。（4）二叉树的结点的类，该类包含结点的相关信息（如结点的值和左、右子树）。（5）二叉树的类，该类包括二叉树的定义及其基本操作。请按以下步骤测试树、森林和二叉树相互转换的实现是否正确。（1）初始化一个树的结点。（2）以（1）中结点作为根结点，递归创建一棵图5-3（主教材图5-50）所示的树。32（3）将（2）中所得树转换为一棵二叉树。（4）将（2）中所得树删除根结点A，进而转换为森林。（5）将（4）中所得森林转换为一棵二叉树。（6）先序遍历（3）和（5）中所得二叉树，并将遍历得到的序列输出，比较两个序列是否相同。（7）将（3）中所得二叉树转换为树。（8）先序遍历（2）和（7）中的树，并将遍历得到的序列输出，比较两个序列是否相同。（9）将（4）中所得森林加上根结点A，进而转换为树。（10）先序遍历（2）和（9）中的树，并将遍历得到的序列输出，比较两个序列是否相同。图5-3（图5-50）一棵树331###########################2#文件名：ex050601_04.py3#版本号：0.14#创建时间：2019-04-265###########################6#类名称：TreeNode7#类说明：定义树结构8#类释义：定义数据结点类型9###########################10classTreeNode(object):11def__init__(self,value):12self.value=value13self.left=None14self.right=None15self.child_list=[]16defadd_child(self,node):17self.child_list.append(node)18classNode(object):19def__init__(self,value=None,children=None):20self.value=value21self.children=children22self.child_list=[]23defadd_child(self,node):24self.child_list.append(node)25###########################实验代码3426#类名称：Tree27#类说明：定义一棵树28#类释义：创建一棵树，并对其执行相关操作。29###########################30classTree(object):31defCreateTree(self):32root=Node('A')33B=Node('B')34root.add_child(B)35F=Node('F')36root.add_child(F)37H=Node('H')38root.add_child(H)39B.add_child(Node('C'))40F.add_child(Node('D'))41F.add_child(Node('E'))42H.add_child(Node('G'))43H.add_child(Node('I'))44H.add_child(Node('J'))45returnroot46###########################47#将树转化为二叉树48###########################49defTreeToBinaryTree(self,root):50ifnotroot:3551returnNone52rootNode=TreeNode(root.value)53iflen(root.child_list)>0:54firstChild=root.child_list[0]55rootNode.left=self.TreeToBinaryTree(firstChild)56curr=rootNode.left57foriinrange(1,len(root.child_list)):58curr.right=self.TreeToBinaryTree(root.child_list[i])59curr=curr.right60returnrootNode61###########################62#将二叉树转为树63###########################64defBinaryTreeToTree(self,root):65ifnotroot:66returnNone67rootNode=Node(root.value,[])68curr=root.left69whilecurr:70rootNode.children.append(self.BinaryTreeToTree(curr))71curr=curr.right72returnrootNode73###########################74#将二叉树转化为森林75###########################3676defBinaryTreeToForest(self,tree):77arr_forest=[]78foriinrange(0,len(tree.child_list)):79arr_forest.append(tree.child_list[i])80returnarr_forest81###########################82#将森林转化为二叉树83###########################84defForestToBinaryTree(self,forest):85ifnotforest:86returnNone87rootNode=TreeNode(0)88foriinrange(0,len(forest)):89ifi==0:90#删除结点A并为新二叉树重新赋值91left_tr=self.TreeToBinaryTree(forest[0])92rootNode.value=left_tr.value93rootNode.left=left_tr.left94elifi==1:95rootNode.right=self.TreeToBinaryTree(forest[1])96else:97curr=rootNode.right98whilecurr.right!=None:99curr=curr.right100curr.right=self.TreeToBinaryTree(forest[i])37101returnrootNode102###########################103#先序遍历二叉树104###########################105defPreOrder(self,root):106ifrootisNone:107return[]108stack=[root]109output=[]110whilelen(stack)>0:111output.append(root.value)112ifroot.right:113stack.append(root.right)114ifroot.left:115stack.append(root.left)116root=stack.pop()117returnoutput118###########################119#遍历树--Children120###########################121defTreeTraverseChildren(self,root):122ifrootisNone:123return[]124stack=[root]125output=[]38126whilelen(stack)>0:127output.append(root.value)128ifroot.children!=None:129forchinroot.children:130stack.append(ch)131root=stack.pop()132returnoutput133###########################134#遍历树--child_list135###########################136defTreeTraverseChildrenList(self,root):137ifrootisNone:138return[]139stack=[root]140output=[]141whilelen(stack)>0:142output.append(root.value)143ifroot.child_list!=None:144forchinroot.child_list:145stack.append(ch)146root=stack.pop()147returnoutput148###########################149#添加结点A，并将森林转换为树150###########################39151defForestToTree(self,forest):152ifforestisNone:153return[]154rootNode=TreeNode("A")155rootNode.child_list=forest156returnrootNode157158########################159#输出函数160########################161defPrintOut(self):162print('创建一棵树')163tree=self.CreateTree()#（2）创建一棵树树164bi_tree=self.TreeToBinaryTree(tree)#（3）将普通树转为二叉树165forests=self.BinaryTreeToForest(tree)#（4）将二叉树转为森林166forest_to_bi_tree=self.ForestToBinaryTree(forests)#(5)将森林转换为二叉树167168#(6)比较(3)和(5)两个序列是否相同169print("(6):先序遍历(3)和(5)中所得二叉树")170print(self.PreOrder(bi_tree))171print(self.PreOrder(forest_to_bi_tree))172print("先序比较遍历(3)和(5)中所得二叉树结果为：",self.PreOrder(bi_tree)==self.PreOrder(forest_to_bi_tree))17340174bi_to_tree=self.BinaryTreeToTree(bi_tree)#(7)将(3)中所得二叉树转换为树175176#(8)比较(2)和(7)两个序列是否相同177print("(8):先序遍历(2)和(7)中所得二叉树")178print(self.TreeTraverseChildrenList(tree))179print(self.TreeTraverseChildren(bi_to_tree))180print("遍历比较(2)和(7)中所得结果为：",self.TreeTraverseChildrenList(tree)==self.TreeTraverseChildren(bi_to_tree))181182forest_to_tree=self.ForestToTree(forests)#(9)将(4)中所得森林加上根结点A，进而转换为树183184#(10)先序遍历并比较(2)和(9)两个输出序列是否相同185print("(10):先序遍历(2)和(7)中所得二叉树")186print(self.TreeTraverseChildrenList(tree))187print(self.TreeTraverseChildrenList(forest_to_tree))188189if__name__=='__main__':190T=Tree()191T.PrintOut()5.2综合实验415.2.1非递归先序遍历二叉树综合实验1综合实验25.2.25.2.3二叉树的反序列化使用栈和二叉树对中缀表达式求值综合实验35.2.4哈夫曼编码综合实验4

综合实验1非递归先序遍历二叉树42深入理解顺序表的存储结构，熟练掌握顺序表的基本操作。实验目的实验背景递归算法最大的好处就是将复杂问题简单化，本章曾多次用到递归算法，如创建二叉树或遍历二叉树。由于递归算法的空间复杂度和时间复杂度都比较高，因此我们可将递归算法转换为非递归算法。在介绍二叉树的遍历时，我们不仅介绍了每种遍历的递归算法，还介绍了与之对应的非递归算法。事实上，由递归算法转换而来的非递归算法并不唯一，以先序遍历二叉树为例，与算法5-7不同的非递归遍历算法的思路如下。（1）使用一个栈存储二叉树的所有结点，首先将根结点入栈。（2）若栈不为空，重复执行（3）～（5）直至栈为空。（3）将栈顶结点TreeNode弹出并访问之。（4）若TreeNode有右孩子，将TreeNode的右孩子入栈。（5）若TreeNode有左孩子，将TreeNode的左孩子入栈。43实验内容100defPrintOut(self):101#创建一棵二叉树102print("**************************************************")创建名为ex050602_01.py的文件，在其中编写非递归遍历二叉树的程序，具体如下。（1）创建一棵图5-4（主教材P269图5-51）所示的二叉树。（2）仿照上述思路实现非递归先序、中序、后序遍历二叉树。（3）输出先序序列、中序序列和后序序列。图5-4（主教材图5-51）一棵二叉树实验代码44103print("**********综合实验1非递归先序遍历二叉树**********")104print('创建一棵树')105print('A')106print('/\\')107print('BC')108print('/\\/\\')109print('DEFG')110print('/\/')111print('HIJ')112print('ABDH###E#I##CFJ###G##')113print('请按上述序列输入二叉树中各结点的值（#表示空结点），每输入一个值按回车换行：')114btrn.CreateBinaryTree(BinaryTreeNode)115print('对二叉树进行非递归前序遍历：’)116#前序遍历二叉树117btrn.PreOrderNonRecursive(BinaryTreeNode)118print('\n对二叉树进行非递归中序遍历：’)119#中序遍历二叉树120btrn.InOrderNonRecursive(BinaryTreeNode)121print('\n对二叉树进行非递归后序遍历：’)122#后序遍历二叉树123btrn.PostOrderNonRecursive(BinaryTreeNode)

综合实验2二叉树的反序列化45熟练掌握二叉树的遍历和构造方法。实验目的实验背景在进行网络传输和数据存储时，若处理对象的数据结构为二叉树，可先对其序列化。二叉树序列化是指遍历二叉树时得到由该树中所有结点值组成的线性序列的过程。二叉树序列化所得的线性序列（简称“二叉序列”）记录了空结点的值（通常将空结点的值设为特殊字符）。我们可由二叉序列创建一棵二叉树，这一过程被称为二叉树反序列化。46实验内容创建名为ex050602_02.py的文件，在其中编写由先序序列化结果（即先序遍历二叉树时所有结点值组成的线性序列）创建一棵二叉树的程序，具体如下。（1）用户输入一个先序序列化结果，如“ABD##EG###C#F##”（‘#’代表空结点的值）。（2）由先序序列化结果创建一棵二叉树。（3）二叉树序列化，验证所建二叉树是否正确。实验代码51defPrintOut(self):52print("************************************************")53print("***********综合实验2二叉树的反序列化***********")54print("(1)由下列先序序列化结果创建一棵二叉树")55print('451##2##6#7##')56print('请输入二叉树中各结点的值(#表示空结点)，每输入一个值按回车换行：')57self.CreateBinaryTree(BinaryTreeNode)58print('(2)二叉树序列化,验证所建二叉树是否正确：’)59self.PreOrder(BinaryTreeNode)

综合实验3使用栈和二叉树对中缀表达式求值47熟练掌握二叉树的构造和遍历方法。实验目的实验背景我们通常所见的算术表达式为中缀表达式，对其进行计算时，须根据运算优先级并按照从左到右的顺序来进行。对于计算机来说，直接对中缀表达式进行计算比较困难，而对后缀表达式进行计算较为容易。那么如何将中缀表达式转换为后缀表达式呢？首先借助于二叉树和栈由给定的中缀表达式创建二叉树，然后对二叉树进行后序遍历得到后缀表达式。48实验内容创建名为ex050602_03.py的文件，在其中编写使用栈和二叉树对中缀表达式求值的程序，具体如下。（1）用户输入一个中缀表达式“3+2*9-6/2”。（2）由该中缀表达式非递归创建一棵二叉树。（3）非递归后序遍历该二叉树得到后缀表达式。（4）借助栈对这一后缀表达式求值并将结果输出。实验代码183defPrintOut(self):184print("*********************************************************")185print("********综合实验3使用栈和二叉树对中缀表达式求值********")186expression='3+2*9-6/2'187print('题目所给中缀表达式为：')188print(expression)189iexpression=InfixExpression(expression)190iexpression.InfixToPostfix()191print('转换之后的后缀表达式为：')192print(''.join(iexpression.PostfixExpression))193print('（1）由中缀表达式非递归创建二叉树')49194bt=BinaryTree(expression)195root=BinaryTreeNode()196bt.CreateBinaryTree(root)197print('（2）非递归后序遍历该二叉树得到的后缀表达式如下：')198bt.PostOrderNonRecursive(root)199postpression=PostfixExpression()200postpression.GetValue(iexpression.PostfixExpression)201print('\n（3）后缀表达式求值结果为：'+str(postpression.result))

综合实验4哈夫曼编码50熟练掌握哈夫曼树的基本操作和二叉树的遍历方法。实验目的实验背景哈夫曼编码多用于数据压缩中。在实际通信时，若甲方需传输一个文件F给乙方，为了实现数据压缩，甲方先根据F中每个字符出现的频率设计哈夫曼编码H，再对F进行处理得到文件HF，然后将文件HF和哈夫曼编码H同时发送给乙方，最后乙方将根据哈夫曼编码H对文件HF进行还原。51实验内容创建名为ex050602_04.py的文件，在其中编写处理程序，具体如下。（1）打开ex050602_04.txt。（2）统计文件中各字符出现的概率。（3）将文件中的字符作为叶子结点的值，并将字符出现的概率作为叶子结点的权值。创建叶子结点，将它们存入同一集合中，并使它们按照权值的升序排列。（4）由叶子结点创建哈夫曼树。（5）为所有叶子结点设计哈夫曼编码。（6）将ex050602_04.txt中的所有字符全部转换为其对应的哈夫曼编码，得到文件ex050602_05.txt。（7）对ex050602_05.txt进行还原，并将还原后的内容存入ex050602_06.txt，比较ex050602_04.txt和ex050602_06.txt的内容是否一致。实验代码196defPrintOut(self,root):197file_ori="ex050602_04.txt"#请注意路径是否一致198rate,fluency=self.OpenTxtFile(file_ori)#（1）&（2）52199#(3)将字符出现的概率作为叶子结点的权值200weight_list=self.CreateLeafWeight(rate,fluency)201print(str(weight_list))202203#(4)由叶子结点创建哈夫曼树204huffman_nodes=self.create_prim_nodes(weight_list)205206#(5）设计哈夫曼编码207root=self.create_HF_tree(huffman_nodes)#创建huffman树208huffman_codes=self.get_huffman_code(huffman_nodes)209forkeyinhuffman_codes.keys():210print(key,':',huffman_codes[key])211212#（6）将ex050602_04.txt中的所有字符全部转换为其对应的哈夫曼编码213self.replaceTextToHaffmanCode(file_ori,huffman_codes)214215#（7）对哈夫曼编码进行解码并将解码后的内容与原始内容比较216file_encoded="ex050602_05.txt"#请注意路径是否一致217output_file_decode="ex050602_06.txt"#请注意路径是否一致53218self.HaffmanDecode(huffman_codes,file_encoded,output_file_decode)219self.CompareOrigDecoderText(file_ori,output_file_decode)5.3习题解答54一、选择题1~5ACBBC【解析】1.满m叉树第n层结点数是前一层m倍，所以第k层结点数为mk-1。参考主教材P213~214。2.深度h取最小值时为完全二叉树的情况。根据完全二叉树的定义（参考主教材P221），有n个结点的二叉树，当且仅当其每一个结点都与深度为h的满二叉树一一对应时，称为完全二叉树。因此该完全二叉树的总结点数目2h-1>=1028，h至少为11才能满足上式。深度h取最大值时为单结点二叉树的情况，此时h为1028。3.二叉树的要求是度不超过2，就是说度也可以是1或者0。参考主教材P220。4.依题意，该满二叉树深度为3，第一层为根结点A，第二层从左往右是分别是结点BC，第三层从左往右分别是结点DEFG。因此先序遍历结果为ABDECFG。参考主教材P221。5.若在任意一棵二叉树中，有n个叶子结点，有n₂个度为2的结点，则必有n₀=n₂+1，可以得到，叶子结点的数目等于度为2的结点的数目加1，即n₀==7，故选C。参考主教材P224。5.3习题解答55一、选择题1~5BCCA