《数据结构(第3版)》课程第6章实验选题

1、数据结构(C+版)(第3版2014-2015-1 学期 叶核亚授课对象：软件131、软件卓越 131 树和二叉树操作实验目的：验证教材中二叉树和树的基本操作，设计实现指定操作算法，并做算法分析。实验要求：使用C+语言，采用类模板和函数模板，算法效率为一次遍历。 实验题目如下，每位学生所选题不重复，如何分配由各班自行决定。1. 二叉树(二叉链表存储结构)成员函数，递归算法以下各题对二叉链表存储的二叉树进行操作，BinaryTreevT类增加成员函数，实现递归算法。 BinaryTree(T prelist,T inlist, int n)/以先根和中根序列构造二叉树BinaryNode* sea

2、rch(T key)/查找先根次序遍历首次出现的关键字为key结点，T重载=BinaryNode* parent(BinaryNode* node) / 返 回 node 的父母结点intlevel(Tkey)返回key结点所在的层次booloperator=(BinaryTree&bitree)/重载=，比较两棵二叉树是否相等boolisSubtree(BinaryTreevT& bitree)/判断 bitree 是否是当前二叉树的子树BinaryTree(BinaryTree&bitree)/拷贝构造函数，深拷贝成员函数，使用栈的非递归算法 使用栈将以下BinaryTreevT类的成员函

3、数实现为非递归算法。intn)postOrder()genlist)intn)postOrder()genlist)printGenList()/以标明空子树的先根序列构造二叉树void /输出后根次序遍历序列BinaryTree(MyString/以广义表表示构造二叉树iv.voidiv./输出二叉树的广义表表示intheight。/返回二叉树的高度BinaryNode* parent(BinaryNode* node) / 返 回 node 的父母结点intlevel(Tkey)返回key结点所在的层次booloperator=(BinaryTree&bitree)/重载=，比较两棵二叉树

4、是否相等boolisSubtree(BinaryTreevT& bitree)/判断 bitree 是否是当前二叉树的子树BinaryTree(BinaryTreevT&bitree)/拷贝构造函数，深拷贝全局函数，递归算法 以下各题对二叉链表存储的二叉树进行操作，全局函数，实现递归算法。void swap(BinaryTree &bitree)/ 交换二叉树结点的左右子树。讨论 3种遍历次序算法的可行性。voidproperty3(BinaryTree&bitree)验证二叉树性质3, n = n +102voidprintDiameter(BinaryTreevT& bitree)/输出二

5、叉树的一条直径及其路径长度void printAncestors(BinaryTree &bitree, T key) / 输 出 bitree 二叉树中关键字为 key 结点的所有祖先结点全局函数，使用栈的非递归算法 以下各题对二叉链表存储的二叉树进行操作，全局函数，使用栈实现非递归算法。voidproperty3(BinaryTree&bitree)验证二叉树性质3, n = n +102voidprintDiameter(BinaryTree&bitree)/输出二叉树的一条直径及其路径长度void printAncestors(BinaryTree &bitree, T key) /

6、输 出 bitree 二叉树中关键字为 key 结点的所有祖先结点增加属性二叉树增加层次属性,求结点所在的层次。完全二叉树实现完全二叉树类(声明见教材实验 6-3),继承二叉树 类,提供按层次遍历序列构造二叉链表结构存储的完全二叉树。void create(T levellist, int n)/以层次序列构造完全二叉树。使用队列的非递归算法二叉树(三叉链表存储结构)成员函数,递归算法以下各题对三叉链表存储的二叉树进行操作，TriBinaryTreevT类增加成员函数，实现递归算法。TriBinaryTree(T prelist, Tinlist, int n)/以先根和中根序列构造二叉树Tr

7、iBinaryNode* search(T key) /查找先根次序遍历首次出现的关键字为key结点，T重载=TriBinaryNode* parent(TriBinaryNode* node) /返回 node 的父母结点intlevel(Tkey)返回key结点所在的层次booloperator=(TriBinaryTree&bitree)/重载=，比较两棵二叉树是否相等boolisSubtree(TriBinaryTreevT& bitree)/判断 bitree 是否是当前二叉树的子树TriBinaryTree(TriBinaryTree&bitree)/拷贝构造函数，深拷贝成员函数，

8、使用栈的非递归算法使用栈将以下TriBinaryTreevT类的成员函数实现为非递归算法。TriBinaryTree(Tprelist,intn)/以标明空子树的先根序列构造二叉树postOrder()genlist)printGenList();postOrder()genlist)printGenList();height()/输出后根次序遍历序列TriBinaryTree(MyString/以广义表表示构造二叉树void/输出二叉树的广义表表示int/返回二叉树的高度TriBinaryNode* parent(TriBinaryNode* node)/返回 node 的父母结点intle

9、vel(Tkey)返回key结点所在的层次booloperator=(TriBinaryTree&bitree)/重载=，比较两棵二叉树是否相等boolisSubtree(TriBinaryTree&bitree)/判断 bitree 是否是当前二叉树的子树TriBinaryTree(TriBinaryTree&bitree)/拷贝构造函数，深拷贝全局函数，递归算法 以下各题对三叉链表存储的二叉树进行操作，全局函数，实现递归算法。voidswap(TriBinaryTree&bitree)/交换二叉树结点的左右子树。讨论 3 种遍历次序算法的可行性。voidproperty3(TriBinar

10、yTree&bitree)验证二叉树性质3， n = n +102void printDiameter(TriBinaryTree &bitree) /输出二叉树的一条直径及其路径长度全局函数，使用栈的非递归算法以下各题对三叉链表存储的二叉树进行操作，全局函数，实现递归算法和使用栈的非递归算法。void property3(TriBinaryTree &bitree)验证二叉树性质3, n = n +102void printDiameter(TriBinaryTree &bitree) /输出二叉树的一条直径及其路径长度增加属性i. 二叉树增加层次属性，求结点所在的层次。完全二叉树类实现完全

11、二叉树类，继承二叉树类，提供按层次遍历序 列构造三叉链表结构存储的完全二叉树。void create(T levellist, int n)/以层次序列构造完全二叉树。使用队列的非递归算法中序线索二叉树i.调用求结点在中根遍历次序下的前驱结点算法，按中根次序遍历一棵中序线索二叉树。按后根次序遍历中序线索二叉树。使用栈实现二叉树中序线索化的非递归算法。深拷贝中序线索二叉树。由一棵二叉树深拷贝构造一棵中序线索二叉树。树(孩子兄弟链表存储)a) 成员函数，递归算法以下各题对采用孩子兄弟链表存储的树TreevT类进行操作，增加成员函数，实现递归算法。intheight()/返回树的高度voidpost

12、Order()/输出树的后根次序遍历序列TreeNode*search(Tkey)/查找关键字为 key 结点intlevel(Tkey)返回关键字为key元素所在的层次booloperator=(Tree&tree)/重载=运算符，比较两棵树是否相等boolisSubtree(TreevT& tree)/判断 tree 是否是当前树的子树Tree(Tree&tree)/拷贝构造函数，深拷贝Tree&operator=(Tree&tree)/重载=赋值运算符，深拷贝TreeNodevT*insert(TreeNodevT*p,TreevT&sub,int i)/复制 sub 子树插入为 p 第

13、 i 棵子树细oidprintGenList()/输出树(森林)的广义表表示Tree(MyString &genlist)/ 以广义表表示构造树，T必须有MyString类参数的构造函数voidprintDiameter(TreevT& tree)/输出树的一条直径及其路径长度以树的横向凹入表示法构造一棵树。b) 成员函数，使用栈的非递归算法以下各题对采用孩子兄弟链表存储的树TreevT类进行操作，增加成员函数，使用栈实现非递归算法。voidpreOrderTraverse()/先根次序遍历树的非递归算法intheight()/返回树的高度voidpostOrder()/输出树的后根次序遍历序

14、列TreeNode*search(Tkey)/查找关键字为 key 结点intlevel(Tkey)返回关键字为key元素所在的层次booloperator=(Tree&tree)/重载=运算符，比较两棵树是否相等boolisSubtree(Tree&tree)/判断 tree 是否是当前树的子树Tree(Tree&tree)/拷贝构造函数，深拷贝Tree&operator=(Tree&tree)/重载=赋值运算符，深拷贝TreeNode*insert(TreeNode*p,Tree&sub,int i)/复制 sub 子树插入为 p 第 i 棵子树voidprintGenList()/输出树

15、(森林)的广义表表示Tree(MyString &genlist)/以广义表表示构造树，T必须有MyString类参数的构造函数voidprintDiameter(Tree&tree)/输出树的一条直径及其路径长度以树的横向凹入表示法构造一棵树。c) 使用队列i.voidlevelOrder()/输出树的层次遍历序列树(父母孩子兄弟链表存储)a) 成员函数，递归算法以下各题对采用父母孩子兄弟链表存储的树TreevT类进行操作，增加成员函数，实现递归算法。height()/返回树的高度ii.voidpostOrder()/输出树的后根次序遍历序列iii.TreeNodevT*searc

16、h(Tkey)/查找关键字为 key 结点int level(T key) 返回关键字为key元素所在的层次booloperator=(Tree&tree)/重载=运算符，比较两棵树是否相等boolisSubtree(TreevT& tree)/判断 tree 是否是当前树的子树Tree(Tree&tree)/拷贝构造函数，深拷贝Tree&operator=(Tree&tree)/重载=赋值运算符，深拷贝TreeNodevT*insert(TreeNodevT*p,TreevT&sub,int i)/复制 sub 子树插入为 p 第 i 棵子树细oidprintGenList()/输出树(森林

17、)的广义表表示Tree(MyString &genlist)/ 以广义表表示构造树，T必须有MyString类参数的构造函数voidprintDiameter(TreevT&tree)/输出树的一条直径及其路径长度b) 成员函数，使用栈的非递归算法以下各题对采用父母孩子兄弟链表存储的树TreevT类进行操作，增加成员函数，使用栈实现非递归算法。voidpreOrderTraverse()/先根次序遍历树的非递归算法intheight()/返回树的高度voidpostOrder()/输出树的后根次序遍历序列TreeNode*search(Tkey)/查找关键字为 key 结点intlevel(T

18、key)返回关键字为key元素所在的层次booloperator=(Tree&tree)/重载=运算符，比较两棵树是否相等boolisSubtree(Tree&tree)/判断 tree 是否是当前树的子树Tree(Tree&tree)/拷贝构造函数，深拷贝Tree&operator=(Tree&tree)/重载=赋值运算符，深拷贝TreeNode*insert(TreeNode*p,Tree&sub,int i)/复制 sub 子树插入为 p 第 i 棵子树voidprintGenList()/输出树(森林)的广义表表示Tree(MyString &genlist)/以广义表表示构造树，T必

19、须有MyString类参数的构造函数voidprintDiameter(Tree&tree)输出树的一条直径及其路径长度c) 使用队列i. void levelOrder() /输出树的层次遍历序列树(父母孩子链表存储)a) 成员函数，递归算法以下各题对采用父母孩子链表存储的树TreevT类进行操作，使用顺序表作为成员变量存储数目不定的孩子 结点，增加成员函数，实现递归算法。intheight。/返回树的高度voidpostOrder()/输出树的后根次序遍历序列TreeNode*search(Tkey)/查找关键字为 key 结点intlevel(Tkey)/返回关键字为 key 元素所在的

20、层次booloperator=(Tree&tree)/重载=运算符，比较两棵树是否相等boolisSubtree(Tree&tree)/判断 tree 是否是当前树的子树Tree(Tree&tree)/拷贝构造函数，深拷贝Tree&operator=(Tree&tree)/重载=赋值运算符，深拷贝TreeNode*insert(TreeNode*p,Tree&sub,int i)/复制 sub 子树插入为 p 第 i 棵子树voidprintGenList()/输出树(森林)的广义表表示Tree(MyString &genlist)/以广义表表示构造树， T 必须有 MyString 类参数的构造函数voidprintDiameter(Tree&