2010数据结构实验指导书48

4、根据实验要求设计并完成程序，把理论的基本操作知识转化到实际的实践应用中。

【实验原理】

由于树的定义是递归的，对树的处理原则上也应是用递归的方式。二叉树是一种非常重要的类型。针

对二叉树的操作主要有三种遍历（先序遍历、中序遍历、后序遍历），遍历二叉树是二叉树中各种运算的基础。

【实验要求】（实验课题一必做，课题二、三选做）

实验课题一：将下图中的二叉树用二叉链表表示：

1 用三种遍历算法遍历该二叉树，给出对应的输出结果；

2 写一个函数对二叉树搜索，若给出一个结点，根据其是否属于该树，输出true或者false。 3 写函数完成习题4.31（C++版）或4.28（C版教科书）。

实验课题二：构造表达式树。

可参考教科书§4.2.2（具体规则用C++描述教材的见p.122，用C描述教材的见p.87）。

实验课题3：哈夫曼编码的生成

当哈夫曼树生成后，对由根节点到各叶结点（对应于待编码的符号）的路径作0-1编码就得到相应的哈夫曼编码。任何一棵满二叉树（a full binary tree）都可以看作是一棵哈夫曼树，所以本课题要求：造一棵满二叉树，根据这棵二叉树生成相应的哈夫曼编码。

2010数据结构实验指导书48

附录：二叉树的ADT接口

用C++描述的教科书中没有给出一个二叉树的ADT接口，我们在这里给出一个二叉树类模板，供同学们使用。

// Binary tree node abstract class

template <class Object> class BinaryNode { public:

// Return the node's element virtual Object& val() = 0; // Set the node's element

virtual void setVal(const Object&) = 0; // Return the node's left child virtual BinaryNode* left() const = 0; // Set the node's left child

virtual void setLeft(BinaryNode*) = 0; // Return the node's right child virtual BinaryNode* right() const = 0; // Set the node's right child

virtual void setRight(BinaryNode*) = 0; // Return true iff the node is a leaf virtual bool isLeaf() = 0; };

// Binary tree node class, an implementation of the abstract class BinaryNode template <class Object>

class BinNode : public BinaryNode<Object> { private:

Object it; // The node's value BinNode* lc; // Pointer to left child BinNode* rc; // Pointer to right child public:

// Two constructors -- with and without initial values BinNode() : lc(NULL), rc(NULL) { }

BinNode(Object e, BinNode* l =NULL, BinNode* r =NULL) : it(e), lc(l), rc(r) { }

~BinNode () {} // Destructor Object& val () { return it; }