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

《数据结构（C++版）（第3版）》 2014-2015-1学期 叶核亚 授课对象：软件131、软件卓越131 树和二叉树操作 实验目的：验证教材中二叉树和树的基本操作，设计实现指定操作算法，并做算法分析。 实验要求：使用C++语言，采用类模板和函数模板，算法效率为一次遍历。 实验题目如下，每位学生所选题不重复，如何分配由各班自行决定。 二叉树（二叉链表存储结构） 成员函数，递归算法 以下各题对二叉链表存储的二叉树进行操作，BinaryTreeT类增加成员函数，实现递归算法。 (BinaryTree(T prelist[], T inlist[], int n) //以先根和中根序列构造二叉树 BinaryNodeT* search(T key) //查找先根次序遍历首次出现的关键字为key结点，T重载== BinaryNodeT* parent(BinaryNodeT* node) //返回node的父母结点 int level(T key) //返回key结点所在的层次 bool operator==(BinaryTreeT bitree) //重载==，比较两棵二叉树是否相等 (bool isSubtree(BinaryTreeT bitree) //判断bitree是否是当前二叉树的子树 BinaryTree(BinaryTreeT bitree) //拷贝构造函数，深拷贝 成员函数，使用栈的非递归算法 使用栈将以下BinaryTreeT类的成员函数实现为非递归算法。 (BinaryTree(T prelist[], int n) //以标明空子树的先根序列构造二叉树 (void postOrder() //输出后根次序遍历序列 ((BinaryTree(MyString genlist) //以广义表表示构造二叉树 ((void printGenList() //输出二叉树的广义表表示 (int height() //返回二叉树的高度 BinaryNodeT* parent(BinaryNodeT* node) //返回node的父母结点 int level(T key) //返回key结点所在的层次 bool operator==(BinaryTreeT bitree) //重载==，比较两棵二叉树是否相等 (bool isSubtree(BinaryTreeT bitree) //判断bitree是否是当前二叉树的子树 ((BinaryTree(BinaryTreeT bitree) //拷贝构造函数，深拷贝 全局函数，递归算法 以下各题对二叉链表存储的二叉树进行操作，全局函数，实现递归算法。 void swap(BinaryTreeT bitree) //交换二叉树结点的左右子树。讨论3种遍历次序算法的可行性。 void property3(BinaryTreeT bitree) //验证二叉树性质3， (void printDiameter(BinaryTreeT bitree) //输出二叉树的一条直径及其路径长度 void printAncestors(BinaryTreeT bitree, T key) //输出bitree二叉树中关键字为key结点的所有祖先结点 全局函数，使用栈的非递归算法 以下各题对二叉链表存储的二叉树进行操作，全局函数，使用栈实现非递归算法。 void property3(BinaryTreeT bitree) //验证二叉树性质3， (void printDiameter(BinaryTreeT bitree) //输出二叉树的一条直径及其路径长度 void printAncestors(BinaryTreeT bitree, T key) //输出bitree二叉树中关键字为key结点的所有祖先结点 增加属性 二叉树增加层次属性，求结点所在的层次。 完全二叉树 实现完全