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

7 二叉树的操作【实验简介】二叉树是树形结构的一种重要类型。通过本次实验，熟悉二叉树结点的结构，掌握二叉树的基本操作以及具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。【实验内容】 编写程序，实现对二叉树的以下操作：1 建立二叉树。2 按任一种遍历次序输出二叉树中的所有结点。3 求二叉树的深度。4 求二叉树中的所有节点数。5 求二叉树中的所有叶子节点数。6 清除二叉树，使之编程一只空树。【主要代码】#includeusing namespace std;template 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 (T value) /构造函数 RefValue=value;root=NULL; BinaryTree()destroy(root); /析构函数 bool IsEmpty() return root=NULL; /判二叉树空否 int Height() return Height(root); /求树高度 int Size() return Size(root); /求结点数 BinTreeNode *getRoot() return root; BinTreeNode *LeftChild (BinTreeNode *cur) /返回左子女 return (cur!=NULL)?cur-leftChild:NULL; BinTreeNode *RightChild (BinTreeNode *cur) /返回右子女 return (cur!=NULL)?cur-rightChild:NULL; void Output (BinTreeNode * subtree); /输出结点void BinaryTreeCount(BinTreeNode* BT,int& m1,int& m2); /输出结点数和叶结点数void SetRefValue(T& M)RefValue=M; /设置数据输入停止标志void Setroot(BinTreeNode* N)root=N; /设置根节点void CreateBinTree (BinTreeNode *& subTree);protected: BinTreeNode *root; /二叉树的根指针 T RefValue; /数据输入停止标志 /void CreateBinTree (istream& in, BinTreeNode *& subTree); /从文件读入建树void destroy (BinTreeNode *& subTree);/删除int Height (BinTreeNode *subTree)const; /返回树高度int Size(BinTreeNode *subTree)const; /返回结点数BinTreeNode *Parent (BinTreeNode * subTree, BinTreeNode *cur); /返回父结点friend ostream& operator(ostream& out,BinaryTree& Tree);template void BinaryTree:destroy (BinTreeNode *& subTree) /私有函数: 删除根为subTree的子树 if (subTree!=NULL) destroy (subTree-leftChild); /删除左子树 destroy (subTree-rightChild); /删除右子树 delete subTree; /删除根结点 ;template void BinaryTree:CreateBinTree(BinTreeNode *& subTree) T item; cinitem; /读入根结点的值 if(item!=RefValue) subTree=new BinTreeNode(item); /建立根结点 if (subTree=NULL) cerr 存储分配错! leftChild); /递归建立左子 CreateBinTree (subTree-rightChild);/递归建立右子树 else subTree=NULL; /封闭指向空子树的指针;template int BinaryTree:Height(BinTreeNode *subTree)const /私有函数：利用二叉树后序遍历算法计算二叉树的高度或深度； if (subTree=NULL) return 0; /空树高度为0； else int i=Height(subTree-leftChild); int j=Height(subTree-rightChild); return (ij)?j+1:i+1; ;template void BinaryTree:BinaryTreeCount(BinTreeNode* BT,int& m1,int& m2) /分别统计出二叉树中所有结点数和叶子结点数 if(BT!=NULL) m1+;/统计所有结点 if(BT-leftChild=NULL&BT-rightChild=NULL) m2+; /统计叶子结点数 BinaryTreeCount(BT-leftChild,m1,m2); BinaryTreeCount(BT-rightChild,m1,m2); else return;return; ;template void BinaryTree:Output (BinTreeNode *subtree) /私有函数：利用二叉树后序遍历算法输出二叉树的结点if (subtree!=NULL)coutdataleftChild); /遍历Output(subtree-rightChild);return;void main()BinaryTree a;int m=0,n=0,p=0;BinTreeNode *b;b=a.getRoot();a.SetRefValue(p); /设置结束标志cout请输入要建立的二叉树的整型数,输入0结束，0应比数字多1：;a.CreateBinTree(b); /创建二叉树cout二叉树的所有结点为：;a.Output(b);coutn; /输出所有结点a.Setroot(b);