二叉树的实现.doc

二叉树的实现.txt32因为爱心，流浪的人们才能重返家园；因为爱心，疲惫的灵魂才能活力如初。渴望爱心，如同星光渴望彼此辉映；渴望爱心，如同世纪之歌渴望永远被唱下去。#include#includeusing namespace std;#define NULL 0/二叉树的结点类class BinaryTreeNodefriend class BinaryTree;private:char element;BinaryTreeNode *left;BinaryTreeNode *right;public:BinaryTreeNode();BinaryTreeNode(const char &ele,BinaryTreeNode * l=NULL,BinaryTreeNode *r=NULL)element=ele;left=l;right=r;BinaryTreeNode *leftchild()constreturn left;BinaryTreeNode *rightchild()constreturn right;char value() const;/二叉树类的定义class BinaryTreeprivate:BinaryTreeNode * root;BinaryTreeNode *GetParent(BinaryTreeNode *root,BinaryTreeNode *current);public:/构造函数BinaryTree()root=NULL;BinaryTree(char x,BinaryTreeNode *l=NULL,BinaryTreeNode *r=NULL)root=new BinaryTreeNode(x,l,r);/void DeleteBinaryTree(BinaryTreeNode *root);/BinaryTree()DeleteBinaryTree(root);/析构函数BinaryTreeNode * Root()return root;/取根结点的值BinaryTreeNode * Root1()return &root;/取根结点的地址值，主要是为建立树的时候使用void CreateTree(const char & elem,BinaryTree &leftTree,BinaryTree & rightTree);bool isEmpty()const;BinaryTreeNode *Parent(BinaryTreeNode * current);void BuildTree(BinaryTreeNode *root);/前序访问void PreOrder(BinaryTreeNode *root)const;/中序遍历void InOrder(BinaryTreeNode *root)const;/后序遍历void PostOrder(BinaryTreeNode *root)const;/层序遍历void LevelOrder(BinaryTreeNode *root)const;/统计叶结点个数void CountLeaf(BinaryTreeNode * root,int &);int BtDepth(BinaryTreeNode *root)const;/判断是否为空树bool BinaryTree:isEmpty()constreturn(root)?true:false);/取父结点BinaryTreeNode * BinaryTree:GetParent(BinaryTreeNode *root,BinaryTreeNode *current)BinaryTreeNode *temp;if(root=NULL)return NULL;if(root-leftchild()=current)|(root-rightchild()=current)return root;if(temp=GetParent(root-leftchild(),current)!=NULL)return temp;else return GetParent(root-rightchild(),current);/BinaryTreeNode * BinaryTree:Parent(BinaryTreeNode * current)if(current=NULL)|(current=root)return NULL;return GetParent(root,current);/删除树void BinaryTree:DeleteBinaryTree(BinaryTreeNode *root)if(root)DeleteBinaryTree(root-left);DeleteBinaryTree(root-right);delete root;/创建一棵二叉树void BinaryTree:BuildTree(BinaryTreeNode *current)/采用前序遍历的方法建立一棵树，传递的参数为一个指向结点的指针的指针，目的是为了解决传值的问题/输入符号的时候，表示一棵子树结束BinaryTreeNode *current1;char ch;coutch;if(ch=) *current=NULL;/current=NULL;elsecurrent1=new BinaryTreeNode(ch);if(root=NULL)root=current1;* current=current1;BuildTree(&(*current)-left);BuildTree(&(*current)-right);/定义结束/前序访问void BinaryTree:PreOrder(BinaryTreeNode *current)constif(current!=NULL)coutelementleftchild();PreOrder(current-rightchild();/中序遍历void BinaryTree:InOrder(BinaryTreeNode *current)constif(current!=NULL)InOrder(current-leftchild();coutelementrightchild();/后序遍历void BinaryTree:PostOrder(BinaryTreeNode *current)constif(current!=NULL)PostOrder(current-leftchild();PostOrder(current-rightchild();coutelement ;/层序遍历void BinaryTree:LevelOrder(BinaryTreeNode *current)constqueueaQueue;BinaryTreeNode *pointer=current;if(pointer)aQueue.push(pointer);while(!aQueue.empty()pointer=aQueue.front();coutelementleftchild()aQueue.push(pointer-leftchild();if(pointer-rightchild()aQueue.push(pointer-rightchild();/统计叶结点个数void BinaryTree:CountLeaf(BinaryTreeNode * root,int &count)if(root!=NULL)if(root-leftchild()=NULL)&(root-rightchild()=NULL) count+;CountLeaf(root-leftchild(),count);CountLeaf(root-rightchild(),count);/计算树的高度int BinaryTree:BtDepth(BinaryTreeNode * current)const/int leftdep,rightdepreturn 0;void main()BinaryT