以下为《数据结构上机实验5》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

上机报告

学 期 ： 2021-2022-1

课 程 名 称 ： 数据结构

实验项目名称： 树的操作实验

学 号： ***215

学 生 姓 名： 汪某某

班 级： 信科2班

专 业： 信息与计算科学

指 导 老 师： 康某某

年 月 日

一、实验目的

1. 理解树的存储结构，并掌握树的基本操作。

2. 理解二叉树的链式存储结构，并掌握二叉树的基本操作。

二、实验平台或环境

Windows 10、Python3.7.2。

三、实验内容和要求

实验5.1：实验内容和要求：创建名为“姓名全拼sj51.py ”的文件，在文件中定义两个类，一个是树的结点类，该 类包含结点的相关信息（如结点的值和所有的子树）；另一个是树的类，该类包含树的 定义及其基本操作。请按以下步骤测试树的基本操作的实现是否正确。代码参考详见实验指导书P109，实验5.1.1 基础实验1。具体程序步骤如下。

（1）初始化一个结点。

（2）以（1）中结点作为根结点，使用递归算法创建一棵图 5-1（主教材 P267 图 5-48）所示的树，其中字母用自己名字不重复的字母依次填充。

（3）对树执行先序遍历，并将先序序列输出。

（4）对树执行后序遍历，并将后序序列输出。

（5）对树执行层次遍历，并将所得序列输出。

（6）计算树的深度并输出。

（7）插入值为树中不存在的排序第一的结点，使其是值为“编号为4”的结点的第一个孩子结点。

实验5.2：实验内容和要求：创建名为“姓名全拼sj52.py ”的文件，在文件中定义两个类，一个是二叉树的结点类， 该类包含结点的相关信息（如结点的值和左、右子树）；另一个是二叉树的类，该类包 含二叉树的定义及其基本操作。请按以下步骤测试二叉树的基本操作的实现是否正确。代码参考详见实验指导书P112，实验5.1.2 基础实验2。具体程序步骤如下。

（1）初始化一个结点。

（2）以（1）中结点作为根结点并使用链式存储结构，递归创建一棵图 5-2（教材 P267 图 5-49）所示的二叉树，其中字母用自己名字不重复的字母依次填充。

（3）对二叉树执行先序遍历，并将先序序列输出。

（4）对二叉树执行中序遍历，并将中序序列输出。

（5）对二叉树执行后序遍历，并将后序序列输出。

（6）对二叉树执行层次遍历，并将所得序列输出。

（7）获取“编号为6”的结点，并将其值修改为树中不存在的排序第一的结点。

（8）为“编号为7”结点添加右孩子，令其值为树中不存在的排序第二的结点。

每个实验的实验步骤和实验小结分别填写，由学生自己书写，实验小结部分要写明做实验时的心得体会或者遇到的问题，解决的办法等等。

四、实验步骤和结果

1

class TreeNode(object):

def __init__(self):

self.data = '#'

self.pFirstChild = None

self.pNextSibling = None

class Tree(object):

def CreateTree(self, Root):

data = input('->')

if data == '#':

Root = None

else:

Root.data = data

Root.pFirstChild = TreeNode()

self.CreateTree(Root.pFirstChild)

Root.pNextSibling = TreeNode()

self.CreateTree(Root.pNextSibling)

def PreOrder(self, Root):

if Root is not None:

self.VisitTreeNode(Root)

self.PreOrder(Root.pFirstChild)

self.PreOrder(Root.pNextSibling)

def PostOrder(self, Root):

if Root is not None:

self.PostOrder(Root.pFirstChild)

self.VisitTreeNode(Root)

self.PostOrder(Root.pNextSibling)

def FloorOrder(self, Root):

if Root is not None:

self.VisitTreeNode(Root)

self.FloorOrder(Root.pNextSibling)

self.FloorOrder(Root.pFirstChild)

def VisitTreeNode(self, TreeNode):

if TreeNode.data is not '#':

print(TreeNode.data, end="")

if __name__ =='__main__':

TN = TreeNode()

T = Tree()

print ('创建一棵树')

print (' A')

print (' / | \\')

print (' B C D')

print (' | | |')

print (' E F G')

print ('A B E # # C F # # D G # # #')

#创建一棵二叉树

print('请输入树中各结点的值（#表示空结点），每输入一个值按回车换行：')

T.CreateTree(TN)

print ('对树进行前序遍历:')

#前序遍历树

T.PreOrder(TN)

print ('\n 对树进行层次遍历:')

#层次遍历树

T.FloorOrder(TN)

print ('\n 对树进行后序遍历:')

#后序遍历树

T.PostOrder(TN)

2

class BinaryTreeNode(object):

def __init__(self):

self.data = '#'

self.LeftChild = None

self.RightChild = None

class CircularSequenceQueue:

def __init__(self):

self.MaxQueueSize=4

self.s=[None for x in range(0,self.MaxQueueSize)]

self.front=0

self.rear=0

def InitQueue(self,Max):

self.MaxQueueSize=Max

self.s=[None for x in range(0,self.MaxQueueSize)]

self.front=0

self.rear=0

def IsEmptyQueue(self):

if self.front==self.rear:

iQueue=True

else:

iQueue=False

return iQueue

def EnQueue(self,x):

if (self.rear+1)%self.MaxQueueSize!=self.front:

self.rear=(self.rear+1)%self.MaxQueueSize

self.s[self.rear]=x

else:

print("队列已满，无法入队")

return

def DeQueue(self):

if self.IsEmptyQueue():

print("队列为空，无法出队")

return

else:

self.front=(self.front+1)%self.MaxQueueSize

return self.s[self.front]

class BinaryTree(object):

def CreateBinaryTree(self, Root):

data = input('->')

if data == '#':

Root = None

else:

Root.data = data

Root.LeftChild = BinaryTreeNode()

self.CreateBinaryTree(Root.LeftChild)

Root.RightChild = BinaryTreeNode()

self.CreateBinaryTree(Root.RightChild)

def PreOrder(self, Root):

if Root is not None:

self.VisitBinaryTreeNode(Root)

self.PreOrder(Root.LeftChild)

self.PreOrder(Root.RightChild)

def InOrder(self, Root):

if Root is not None:

self.InOrder(Root.LeftChild)

self.VisitBinaryTreeNode(Root)

self.InOrder(Root.RightChild)

def PostOrder(self, Root):

if Root is not None:

self.PostOrder(Root.LeftChild)

self.PostOrder(Root.RightChild)

self.VisitBinaryTreeNode(Root)

def LevelOrder(self,Root):

tSequenceQueue = CircularSequenceQueue()

tSequenceQueue.InitQueue(100)

tSequenceQueue.EnQueue(Root)

tTreeNode = None

while tSequenceQueue.IsEmptyQueue() == False:

tTreeNode = tSequenceQueue.DeQueue()

self.VisitBinaryTreeNode(tTreeNode)

if tTreeNode.LeftChild is not None:

tSequenceQueue.EnQueue(tTreeNode.LeftChild)

if tTreeNode.RightChild is not None:

tSequenceQueue.EnQueue(tTreeNode.RightChild)

def VisitBinaryTreeNode(self, BinaryTreeNode):

if BinaryTreeNode.data is not '#':

print(BinaryTreeNode.data, end="")

def ModifyNode(self, Root):

if Root is not None:

self.FindNodeF(Root)

self.ModifyNode(Root.LeftChild)

self.ModifyNode(Root.RightChild)

def FindNodeF(self, BinaryTreeNode):

if BinaryTreeNode.data == 'F':

BinaryTreeNode.data = 'Z'

def InsertNode(self, Root):

if Root is not None:

self.FindNodeG(Root)

self.InsertNode(Root.LeftChild)

self.InsertNode(Root.RightChild)

def FindNodeG(self, Node):

if Node.data == 'G':

Node.RightChild = BinaryTreeNode()

Node.RightChild.data = 'K'

def PrintOut(self):

print("***********************************************************")

print("***************基础实验 2 实现二叉树的各种基本操作*************")

print("\n(1)初始化根结点:", end="")

try:

self.__init__()

print("树初始化成功！")

except:

print("树初始化失败！")

print("\n(2)递归算法创建一棵树。")

print('创建一棵二叉树\n')

print(' A')

print(' / \\')

print(' B C')

print(' / \\ / \\')

print(' D E F G ')

print(' / \\/')

print(' H IJ ')

print('A B D H # # # E # I # # C F J # # # G # # ')

print('请仿照上述序列，输入某一二叉树中各结点的值（#表示空结点），每输入一个值按回车换行：')

try:

self.CreateBinaryTree(bTN)

print("二叉树创建完成!")

except ValueError:

print("输入有误，请重新输入!")

self.CreateBinaryTree(bTN)

print("\n(3)对二叉树进行前序遍历:")

try:

self.PreOrder(bTN)

except ValueError:

print("遍历出错!")

print("\n\n(4)对二叉树进行中序遍历:")

try:

self.InOrder(bTN)

except ValueError:

print("遍历出错!")

print("\n\n(5)对二叉树进行后序遍历:")

try:

self.Post 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 ry:

self.ModifyNode(bTN)

except ValueError:

print("修改出错!")

print("修改 F 后的二叉树前序遍历结果为:")

self.PreOrder(bTN)

print("\n\n(8)为值为 G 的结点添加右孩子，令其值为 K。")

try:

self.InsertNode(bTN)

except ValueError:

print("插入出错!")

print("插入后的二叉树前序遍历结果为:")

self.PreOrder(bTN)

if __name__ == '__main__':

bTN = BinaryTreeNode()

bT = BinaryTree()

bT.PrintOut()

实验小结

收获很多。

[文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]

以上为《数据结构上机实验5》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。