二叉树的实现.doc

实验三：二叉树的实现班级：2010级数学班 学号：201008101127 姓名：裴志威 【实验目的】（1） 掌握二结构；（2） 掌握二叉树的二叉链表存储结构；（3） 验证二叉树的二叉链表存储及遍历操作。【实验内容】（1） 建立一棵含有n个结点的二叉树，采用二叉树链表存储；（2） 输出前序、中序和后序遍历该二叉树的遍历结果。【实验内容与步骤】#includetemplate struct BinTreeNode /二叉树结点类定义T data; /数据域 BinTreeNode *leftChild, *rightChild; /左子女、右子女链域 BinTreeNode () leftChild = NULL;rightChild = NULL; BinTreeNode (T x, BinTreeNode *left = NULL, BinTreeNode *right = NULL) data = x;leftChild = left; rightChild = right; ; template class BinaryTree /二叉树类定义 public: BinaryTree () root=NULL; /构造函数 BinaryTree (BinTreeNode *&root); /构造函数 BinaryTree (); /析构函数 int CounteBinTree (BinTreeNode *root,int &count); /计算根节点int Size (BinTreeNode *root); /返回结点数int Height (BinTreeNode *root); /返回树高度void Print_PreOrder(BinTreeNode *&root);void Print_InOrder(BinTreeNode *&root);void Print_PostOrder(BinTreeNode *&root);bool IsEmpty() return root=NULL; void Creat(BinTreeNode *&root);/从文件读入建树void Destroy (BinTreeNode *root); /删除根节点protected: BinTreeNode *root; /二叉树的根指针 ;template BinaryTree:BinaryTree (BinTreeNode *&root)Creat(root); template void BinaryTree:Creat(BinTreeNode *&root)char ch; cinch;if(ch=#) root=NULL;elseroot = new BinTreeNode; /建立根结点 root-data=ch;Creat(root-leftChild); /递归建立左子树 Creat(root-rightChild);/递归建立右子树 template BinaryTree:BinaryTree ()Destroy (root); template void BinaryTree:Destroy (BinTreeNode *root)if(root!=NULL)Destroy(root-leftChild); Destroy(root-rightChild); delete root;/root=NULL;template void BinaryTree:Print_PreOrder(BinTreeNode *&root)if(root=NULL) return ;elsecoutdataleftChild); Print_PreOrder(root-rightChild);template void BinaryTree:Print_InOrder(BinTreeNode *&root)if(root=NULL) return ;elsePrint_PreOrder(root-leftChild);coutdatarightChild);template void BinaryTree:Print_PostOrder(BinTreeNode *&root)if(root=NULL) return ;else Print_PreOrder(root-leftChild); Print_PreOrder(root-rightChild);coutdata ;template int BinaryTree:CounteBinTree (BinTreeNode *root,int &count)if(root)if(root-leftChild=NULL&root-rightChild=NULL)count+;CounteBinTree(root-leftChild,count);CounteBinTree(root-rightChild,count);return count; template int BinaryTree:Size (BinTreeNode *root)if (root = NULL) return 0; /空树 elsereturn 1+Size (root-leftChild) + Size (root-rightChild); template int BinaryTree:Height (BinTreeNode *root) int i,j;if(root=NULL) return 0;else i=Height(root-leftChild);j=Height(root-rightChild);return 1+(ij)?j:i); void main() int count=0;/,i,jcout请输入节点元素，以#结束!endl;BinTreeNode*subtree;subtree=new BinTreeNode;BinaryTreehyb(subtree);cout树的前序访问遍序为：endl;hyb.Print_PreOrder(subtree);coutendl;cout树的中序访问遍序为：endl;hyb.Print_InOrder(subtree);coutendl;cout树的后序访问遍序为：endl;hyb.Print_PostOrder(subtree);coutendl;cout树叶结点个数为：hyb.CounteBinTree(subtree,count);coutendl;cout树高度和深度为：hyb.Height(subtre