二叉树的建立、输出、结点、高度、叶结点的输出.doc

7 二叉树的操作 【实验简介】二叉树是树形结构的一种重要类型。通过本次实验，熟悉二叉树结点的结构，掌握二叉树的基本操作以及具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 【实验内容】 编写程序，实现对二叉树的以下操作： 建立二叉树。 按任一种遍历次序输出二叉树中的所有结点。 求二叉树的深度。 求二叉树中的所有节点数。 求二叉树中的所有叶子节点数。 清除二叉树，使之编程一只空树。 【主要代码】#includeiostream using namespace std; template class T struct BinTreeNode //二叉树结点类定义 { T data; //数据域 BinTreeNodeT *leftChild, *rightChild; //左子女、右子女链域 BinTreeNode () //构造函数 { leftChild=NULL;rightChild=NULL; } BinTreeNode (T x,BinTreeNodeT *left=NULL,BinTreeNodeT *right=NULL) { data=x; leftChild=left;rightChild=right; } }; template class T class BinaryTree { //二叉树类定义 public: BinaryTree() {root=NULL;} //构造函数 BinaryTree (T value) //构造函数 {RefValue=value;root=NULL;} ~BinaryTree(){destroy(root);} //析构函数 bool IsEmpty(){ return root==NULL;} //判二叉树空否 int Height(){ return Height(root);} //求树高度 int Size() { return Size(root); } //求结点数 BinTreeNodeT *getRoot() { return root; } BinTreeNodeT *LeftChild (BinTreeNodeT *cur) //返回左子女 { return (cur!=NULL)?cur-leftChild:NULL; } BinTreeNodeT *RightChild (BinTreeNodeT *cur) //返回右子女 { return (cur!=NULL)?cur-rightChild:NULL; } void Output (BinTreeNodeT * subtree); //输出结点 void BinaryTreeCount(BinTreeNodeT* BT,int m1,int m2); //输出结点数和叶结点数 void SetRefValue(T M){RefValue=M;} //设置数据输入停止标志 void Setroot(BinTreeNodeT* N){root=N;} //设置根节点 void CreateBinTree (BinTreeNodeT * subTree); protected: BinTreeNodeT *root; //二叉树的根指针 T RefValue; //数据输入停止标志 //void CreateBinTree (istream in, BinTreeNodeT * subTree); //从文件读入建树 void destroy (BinTreeNodeT * subTree); //删除 int Height (BinTreeNodeT *subTree)const; //返回树高度 int Size(BinTreeNodeT *subTree)const; //返回结点数 BinTreeNodeT *Parent (BinTreeNodeT * su