Python数据结构实验树和二叉树实验（三）

2024-03-29 11:46:06
开发
15

一、实验目的

1．掌握二叉树的层次遍历过程和算法设计方法；

2．掌握二叉树的构造方法，包括由先序/中序序列或后序/中序序列构造二叉树的算法设计方法；

3．了解二叉树与树、森林之间的转换过程和方法。

二、实验环境

1．Windows操作系统的计算机

2．Python3.7环境平台和PyCharm编辑器

三、实验说明

1．实现二叉树层次遍历和二叉树构造的算法程序设计。
2．实验中如无特别说明，均要求使用脚本（.py）方式编写代码。

3．自主编写程序，必要时参考相关资料。

4．实验学时：2学时

四、实验内容和步骤

1．实验内容

假设二叉树采用二叉链存储，每个结点值为单个字符，并且所有结点值不相同。编写一个实验程序，由二叉树的中序序列和后序序列构造二叉树，实现查找、求高度、先序遍历、中序遍历、后序遍历算法和层次遍历算法，用相关数据进行测试。

参考思路：

from collections import deque



class BTNode:  #二叉链中结点类

    def __init__(self,d=None):       #构造方法

        ……

   

class BTree:                                                      #二叉树类

    def __init__(self,d=None):        #构造方法

        ……



    def DispBTree(self):    #返回二叉链的括号表示串

        ……



    def _DispBTree1(self,t):                #被DispBTree方法调用

        ……



    def FindNode(self,x):                            #查找值为x的结点算法

        ……



    def _FindNode1(self,t,x):                               #被FindNode方法调用

        …….



    def Height(self):     #求二叉树高度的算法

        ……



    def _Height1(self,t):                                       #被Height方法调用

        ……



    def PreOrder(bt):     #先序遍历的递归算法

         …….

   

     def _PreOrder(t):                                           #被PreOrder方法调用

          ……



    def InOrder(bt):                                #中序遍历的递归算法

         ……



    def _InOrder(t):                                      #被InOrder方法调用

         ……



    def PostOrder(bt):                        #后序遍历的递归算法

         ……



    def _PostOrder(t):                                           #被PostOrder方法调用

         ……



    def LevelOrder(bt):              #层次遍历的算法

         ……



    def CreateBTree2(posts,ins):              #由后序序列posts和中序序列ins构造二叉链

         ……

    

    def _CreateBTree2(posts,i,ins,j,n):     #被CreateBTree2方法调用

         ……









#主程序

ins=[……]

posts=[……]

print()

print("  中序:",end=' '); print(ins)

print("  后序:",end=' '); print(posts)

print("  构造二叉树bt")

bt= ___ ___ ___ ___

bt= ___ ___ ___ ___

print("  bt:",end=' '); print(bt.DispBTree())

x= ___ ___ ___ ___

p=bt.FindNode(x)

if p!=None: print("  bt中存在"+x)

else: print("  bt中不存在"+x)

print("  bt的高度=%d" %(bt.Height()))

print("  先序序列:",end=' '); _ ___ ___ ___;print()

print("  中序序列:",end=' '); _ ___ ___ ___;print()

print("  后序序列:",end=' '); _ ___ ___ ___;print()

print("  层次序列:",end=' '); _ ___ ___ ___;print()

2．实验步骤

（1）分析实验内容，写出程序大致框架或完整的程序代码。

（2）进入Python集成环境。

（3）编辑程序并进行保存。

（4）运行程序，若有错误，修改错误后再次运行，如此反复进行到不显示出错为止。

（5）检查程序输出结果。

五、实验代码与结果（程序运行代码及其结果）

1．（1）给出算法的基本设计思想。

（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。

from collections import deque

class BTNode:  #二叉链中结点类

    def __init__(self,d=None):       #构造方法

        self.data=d #结点值

        self.lchild=None #左孩子指针

        self.rchild=None #右孩子指针



class BTree:                        #二叉树类

    def __init__(self,d=None):     #构造方法

        self.b=None                  #根结点指针



    def DispBTree(self):    #返回二叉链的括号表示串

       return self._DispBTree(self.b)





    def _DispBTree(self,t):     #被DispBTree方法调用

        if t==None:                     #空树返回空串

            return ""

        else:

            bstr=t.data #输出根结点值

            if t.lchild!=None or t.rchild!=None:

              bstr+="(" #有孩子结点时输出"("

              bstr+=self._DispBTree(t.lchild) #递归输出左子树

              if t.rchild!=None:

                bstr+="," #有右孩子结点时输出","

              bstr+=self._DispBTree(t.rchild) #递归输出右子树

              bstr+=")" #输出")"

        return bstr



    def FindNode(self,x):                            #查找值为x的结点算法

        return self._FindNode(self.b,x)







    def _FindNode(self,t,x):                               #被FindNode方法调用

       if t==None:

            return None   #t为空时返回None

       elif t.data==x:

             return t   #t所指结点值为x时返回t

       else:

            p=self._FindNode(t.lchild,x)   #在左子树中查找

            if p!=None:

                return p   #在左子树中找到p结点，返回p

            else:

                return self._FindNode(t.rchild,x)   #返回在右子树中查找结果





    def Height(self):     #求二叉树高度的算法

        return self._Height(self.b)





    def _Height(self,t):                                       #被Height方法调用

        if t==None:

            return 0 #空树的高度为0

        else:

             lh=self._Height(t.lchild) #求左子树高度lchildh

             rh=self._Height(t.rchild) #求右子树高度rchildh

             return max(lh,rh)+1





def PreOrder(bt):          #先序遍历的递归算法

     _PreOrder(bt.b)



def _PreOrder(t):               #被PreOrder方法调用

    if t!=None:

        print(t.data,end=' ') #访问根结点

        _PreOrder(t.lchild) #先序遍历左子树

        _PreOrder(t.rchild) #先序遍历右子树



def InOrder(bt):                #中序遍历的递归算法

    _InOrder(bt.b)



def _InOrder(t):                #被InOrder方法调用

  if t!=None:

    _InOrder(t.lchild) #中序遍历左子树

    print(t.data,end=' ') #访问根结点

    _InOrder(t.rchild) #中序遍历右子树





def PostOrder(bt):               #后序遍历的递归算法

    _PostOrder(bt.b)



def _PostOrder(t):               #被PostOrder方法调用

  if t!=None:

    _PostOrder(t.lchild) #后序遍历左子树

    _PostOrder(t.rchild) #后序遍历右子树

    print(t.data,end=' ') #访问根结点



def LevelOrder(bt):              #层次遍历的算法

    qu=deque()                    #将双端队列作为普通队列qu

    qu.append(bt.b) #根结点进队

    while len(qu)>0:              #队不空循环

          p=qu.popleft() #出队一个结点

          print(p.data,end=' ') #访问p结点

          if p.lchild!=None: #有左孩子时将其进队

             qu.append(p.lchild)

          if p.rchild!=None: #有右孩子时将其进队

            qu.append(p.rchild)





def CreateBTree2(posts,ins):              #由后序序列posts和中序序列ins构造二叉链

    bt=BTree()

    bt.b=_CreateBTree2(posts,0,ins,0,len(posts))

    return bt





def _CreateBTree2(posts,i,ins,j,n):     #被CreateBTree2方法调用

    if n<=0: return None

    d=posts[i+n-1]       #取后序序列尾元素即根结点值d

    t=BTNode(d)           #创建根结点(结点值为d)

    p=ins.index(d)                        #在ins中找到根结点的索引

    k=p-j #确定左子树中结点个数k

    t.lchild=_CreateBTree2(posts,i,ins,j,k)  #递归构造左子树

    t.rchild=_CreateBTree2(posts,i+k,ins,p+1,n-k-1)  #递归构造右子树

    return t





#主程序

ins=['H','U','N','G']

posts=['G','N','U','H']

print()

print("  中序:",end=' '); print(ins)

print("  后序:",end=' '); print(posts)

print("  构造二叉树bt")

bt=BTree()

bt= CreateBTree2(posts,ins)

print("  bt:",end=' '); print(bt.DispBTree())

x=input("请输入要查找的元素：")

p=bt.FindNode(x)

if p!=None: print("  bt中存在"+x)

else: print("  bt中不存在"+x)

print("  bt的高度=%d" %(bt.Height()))

print("  先序序列:",end=' '); PreOrder(bt);print()

print("  中序序列:",end=' '); InOrder(bt);print()

print("  后序序列:",end=' '); PostOrder(bt);print()

print("  层次序列:",end=' '); LevelOrder(bt);print()

原文地址:https://blog.csdn.net/Jiangxia13/article/details/137020595 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1773557214926213120.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部

Python数据结构实验 树和二叉树实验（三）

相关推荐

最近更新

热门阅读

Python数据结构实验树和二叉树实验（三）