二叉树实验代码

1. 掌握二叉树的链式存储结构的定义及实现方法。 2. 掌握二叉树的先序、中序和后序遍历方法。 3. 掌握二叉树的结点个数和树的深度的计算方法。 实验内容：

1. 建立一棵含有n个结点的二叉树，采用二叉链表存储。 2. 分别用前序、中序和后序遍历该二叉树，输出访问到的结点。 3. 计算该二叉树的结点个数和二叉树的深度，输出计算结果。

//参考代码

#include #include #include template

struct BinTreeNode {//二叉树结点类定义 T data; //数据域

BinTreeNode *leftChild, *rightChild; //左子女、右子女链域

BinTreeNode ():leftChild(NULL),rightChild(NULL){} //构造函数 BinTreeNode (T x, BinTreeNode *l = NULL, BinTreeNode *r = NULL) { data = x; leftChild = l; rightChild = r; }}; template class BinaryTree { //二叉树类定义 public:

BinaryTree (T value) : RefValue(value), root(NULL) //构造函数 { CreateBinTree (cin,root); } BinaryTree (BinaryTree& s); //复制构造函数

~BinaryTree () { destroy(root); } //析构函数 bool IsEmpty () { return root == NULL;}//判二叉树空否 int Height () { return Height(root); } //求树高度 int Size (){ return Size(root); } //求结点数 BinTreeNode *getRoot () const { return root; }//取根

void preOrder (void (*visit) (BinTreeNode *p)) //前序遍历 { preOrder (root, visit); } void inOrder (void (*visit) (BinTreeNode *p)) //中序遍历 { inOrder (root, visit); } void postOrder (void (*visit) (BinTreeNode *p)) //后序遍历 { postOrder (root, visit); } protected:

BinTreeNode *root; //二叉树的根指针 T RefValue; //数据输入停止标志

void CreateBinTree (istream& in,BinTreeNode *& subTree); //从文件读入建树 void destroy (BinTreeNode * subTree); void preOrder (BinTreeNode* subTree, void (*visit) (BinTreeNode *p)); //前序遍历

void inOrder (BinTreeNode* subTree, void (*visit) (BinTreeNode *p)); //中序遍历 void postOrder (BinTreeNode* subTree, void (*visit) (BinTreeNode *p)); //后序遍历

int Size (BinTreeNode *subTree) const; //返回结点数 int Height ( BinTreeNode * subTree);//返回树高度 //其他函数略 };

template

void BinaryTree::destroy (BinTreeNode * subTree) { //删除根为subTree的子树 if (subTree != NULL) {

destroy (subTree->leftChild); //删除左子树 destroy (subTree->rightChild); //删除右子树 delete subTree; //删除根结点 } }

template

void BinaryTree::CreateBinTree (istream& in, BinTreeNode *& subTree) { T item;

if ( !in.eof () ) { //未读完, 读入并建树

in >> item; //读入根结点的值 if (item != RefValue) {

subTree = new BinTreeNode(item); //建立根结点 if (subTree == NULL) {cerr << \"存储分配错!\"<< endl; exit (1);}

CreateBinTree (in, subTree->leftChild); //递归建立左子树 CreateBinTree (in, subTree->rightChild); //递归建立右子树 } else subTree = NULL; //封闭指向空子树的指针 } }

template //前序

void BinaryTree::preOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *p)) {

if (subTree!= NULL) { visit (subTree); //访问根结点 preOrder (subTree->leftChild, visit); //遍历左子树 preOrder (subTree->rightChild, visit); //遍历右子树 } }

template //中序

void BinaryTree::inOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *p)) {

if (subTree != NULL) {

inOrder (subTree->leftChild, visit); //遍历左子树 visit (subTree); //访问根结点

inOrder (subTree->rightChild, visit); //遍历右子树 } }

template //后序

void BinaryTree::postOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *p)) {

if (subTree != NULL ) {

postOrder (subTree->leftChild, visit);//遍历左子树 postOrder (subTree->rightChild, visit); //遍历右子树 visit (subTree); //访问根结点 } }

template

int BinaryTree::Size (BinTreeNode * subTree) const { if (subTree == NULL) return 0; //空树

else return 1+Size (subTree->leftChild)+ Size (subTree->rightChild); }

template

int BinaryTree::Height ( BinTreeNode * subTree){ if (subTree == NULL) return 0; //空树高度为0 else {

int i = Height (subTree->leftChild); int j = Height (subTree->rightChild); return (i < j) ? j+1 : i+1; } }

void print(BinTreeNode *p) {

cout<data; }

void main() { BinaryTree T('#'); cout<<\"前序遍历结果为：\"; T.preOrder(print); cout<}

测试数据：

abdce 输入：ab##cd##e## 输出：

说明：输入中的#号是分支结束的标志。