链表实验

一、实验目的

1.掌握常用的链表的用法。

2.掌握链表在树型结构的应用。

二、实验设备与器件

PC机、TempoAI平台

三、相关知识

为了完成本关任务，你需要掌握：

·      树的基本概念，

·      二叉树的基本概念，

·      二叉树结点的链式存储。

树的基本概念

如图1所示就是一棵树，它是若干结点的集合，是由唯一的根（A 结点）和若干棵互不相交的子树组成。其中每一棵子树又是一棵树，也是由唯一的根结点和若干棵互不相交的子树组成。当树的结点数为 0 时，这棵树称为一棵空树。
结点的度是结点拥有的子树个数或者分支的个数。度为 0 的结点为叶子结点，如图中的 F 、J 、L 、K 、O 、P 结点。结点的子树的根为该结点的孩子，如图中 A 结点的孩子为 B、 C。同时，A 结点也称为 B 、C 结点的双亲结点。

图1 - 树

二叉树的基本概念

二叉树是在树的基础上加上如下两个限制条件：

1.    每个结点最多只有两棵子树，即二叉树中结点的度只能为0、1、20、1、2；

2.    子树有左右之分，不能颠倒。

根据二叉树的定义，可以知道二叉树共有 5 种基本的形态，如下面图2所示。

图2 - 二叉树的 5 种基本形态

（1）空二叉树
（2）只有根结点
（3）只有左子树，右子树为空
（4）只有右子树，左子树为空
（5）既有左子树，又有右子树

二叉树结点的链式存储

二叉树中的每个结点用一个链结点来存放。每个链结点保存该结点的数据项，以及指向左右子树的链接。结点结构如图3所示。

图3 - 二叉树的结点结构

定义 BinaryTree 类，初始化根结点数据项以及指向左右子树的链接。示例如下：

class BinaryTree:

    def __init__(self,rootObj):

        self.key = rootObj     # 成员key保存根结点数据项

        self.leftChild = None  # 成员leftChild保存指向左子树的引用

        self.rightChild = None # 成员rightChild保存指向右子树的引用

当我们插入一个新的左子结点到树中时：

1.                              若根结点的左子树为 None ，我们需要创建另一个 BinaryTree 的实例，并修改根结点的self.leftChild使之指向新的树。示例如下：

self.leftChild = BinaryTree(newNode)

1.                              若根结点的左子树不为 None，我们将原来根的左子树作为新结点的左子树，并且也修改根结点的self.leftChild使之指向新的树。示例如下：

t = BinaryTree(newNode)     # 创建一个BinaryTree类型的新结点t

t.leftChild = self.leftChild

self.leftChild = t

编程要求

请在右侧Begin-End区域中补全代码完成以下任务：

·                         参考 BinaryTree 类中的__init__、insertLeft方法，补充insertRight、setRootVal、getRightChild、getLeftChild和getRootVal方法。

测试说明

在按编程要求完成操作后，请点击评测按钮，系统会自动对你的操作进行评测。
当你的结果与预期输出一致时，即为通过。

测试输入：

a,b,c

预期输出：

a

b

c

a

b

hello

输入说明：
后台将接收输入字符串，该字符串中以逗号分隔的字符为创建二叉树的结点。我们对二叉树中的结点按照从上到下、从左到右的顺序编号。根据输入结点a、b、c，按编号顺序创建二叉树，创建的过程如下：

1. 创建结点 a；

2. 将 b 插入到 a 的左子树；

3. 将 c 插入到 a 的右子树。

输出说明：
前三行输出：对创建的二叉树按编号顺序输出结点。
后三行输出：代码最后利用setRootVal方法将根结点的右孩子的值设为 hello。在修改根结点的右孩子的值为 hello 后，对修改后新的二叉树按编号顺序输出结点。

创建的二叉树如下面图4所示：

图4 - 测试案例创建的二叉树