叶老师版数据结构二叉树各种函数

//二叉树类#includeBinaryNode.h//二叉树的二叉链表结点类#includeSeqStack.h//顺序栈#includeLinkedStack.h//链式栈#includeSeqQueue.h//顺序循环队列//#includeLinkedQueue.h//链式队列templateclassTclassBinaryTree//二叉树类{public:BinaryNodeT*root;//指向根结点BinaryTree();//构造空二叉树BinaryTree(Tprelist[],intn);//以标明空子树的先根序列构造一棵二叉树BinaryTree(Tprelist[],Tinlist[],intn);//以先根和中根序列构造二叉树~BinaryTree();//析构函数boolisEmpty();//判断是否空二叉树voidpreOrder();//先根次序遍历二叉树voidinOrder();//中根次序遍历二叉树voidpostOrder();//后根次序遍历二叉树intcount();//返回二叉树的结点个数intheight();//返回二叉树的高度BinaryNodeT*search(Tvalue);//查找首次出现的值为value的结点BinaryNodeT*getParent(BinaryNodeT*node);//返回node结点的父母结点BinaryNodeT*insert(BinaryNodeT*p,Tvalue,boolleftChild=true);//插入value作为p结点的孩子voidremove(BinaryNodeT*p,boolleftChild=true);//删除p结点的左或右子树voidprintGList();//以广义表表示输出二叉树voidinOrderTraverse();//中根次序遍历二叉树的非递归算法voidlevelOrder();//按层次遍历二叉树private:voidpreOrder(BinaryNodeT*p);//先根次序遍历以p结点为根的子树voidinOrder(BinaryNodeT*p);//中根次序遍历以p结点为根的子树voidpostOrder(BinaryNodeT*p);//后根次序遍历以p结点为根的子树voiddestroy(BinaryNodeT*p);//撤销二叉树BinaryNodeT*create(Tprelist[],intn,int&i);//以标明空子树的先根遍历序列创建子树BinaryNodeT*create(Tprelist[],Tinlist[],intpreStart,intinStart,intn);//以先根和中根序列创建一棵子树intcount(BinaryNodeT*p);//返回以p结点为根的子树结点个数intheight(BinaryNodeT*p);//返回以p结点为根的子树高度BinaryNodeT*search(BinaryNodeT*p,Tvalue);//在以p为根的子树中查找首次出现的值为value的结点BinaryNodeT*getParent(BinaryNodeT*p,BinaryNodeT*node);voidprintGList(BinaryNodeT*p);//以广义表表示输出以p结点为根的子树//第6章习题public:voidleaf();//遍历输出叶子结点intcountLeaf();//返回二叉树的叶子结点数boolreplace(Told,Tvalue);//将首次出现的值为old结点值替换为valuevoidreplaceAll(Told,Tvalue);//将值为old的结点全部替换为valueintoperator==(BinaryTreeT&bitree);//比较两棵二叉树是否相等，重载运算符==BinaryTree(BinaryTreeT&bitree);//由已知的bitree构造二叉树voidpreOrderTraverse();//先根次序遍历二叉树的非递归算法boolisSorted();//判断一棵二叉树是否为二叉排序树private:voidleaf(BinaryNodeT*p);//输出以p结点为根的子树的所有叶子结点intcountLeaf(BinaryNodeT*p);//返回以p结点为根的子树的叶子结点个数voidreplaceAll(BinaryNodeT*p,Told,Tvalue);//在以p为根的子树中实现全部替换boolequals(BinaryNodeT*p,BinaryNodeT*q);//判断以p和q结点为根的两棵子树是否相等BinaryNodeT*copy(BinaryNodeT*p);//复制以p根的子二叉树//第8章习题boolisSorted(BinaryNodeT*p);};templateclassTBinaryTreeT::BinaryTree()//构造空二叉树{root=NULL;}templateclassTboolBinaryTreeT::isEmpty()//判断是否空二叉树{returnroot==NULL;}//3.二叉树的先根、中根和后根次序遍历算法templateclassTvoidBinaryTreeT::preOrder()//先根次序遍历二叉树{cout先根次序遍历二叉树:;preOrder(root);//调用先根次序遍历二叉树的递归函数coutendl;}templateclassTvoidBinaryTreeT::preOrder(BinaryNodeT*p)//先根次序遍历以p结点为根的子树，递归函数{if(p!=NULL)//若二叉树不空{coutp-data;//访问当前结点preOrder(p-left);//按先根次序遍历当前结点的左子树，递归调用preOrder(p-right);//按先根次序遍历当前结点的右子树，递归调用}}templateclassTvoidBinaryTreeT::inOrder()//中根次序遍历二叉树{cout中根次序遍历二叉树:;inOrder(root);//调用中根次序遍历二叉树的递归函数coutendl;}templateclassTvoidBinaryTreeT::inOrder(BinaryNodeT*p)//中根次序遍历以p结点为根的子树，递归函数{if(p!=NULL){inOrder(p-left);coutp-data;inOrder(p-right);}}templateclassTvoidBinaryTreeT::postOrder()//后根次序遍历二叉树{cout后根次序遍历二叉树:;postOrder(root);//调用后根次序遍历二叉树的递归函数coutendl;}templateclassTvoidBinaryTreeT::postOrder(BinaryNodeT*p)//后根次序遍历以p结点为根的子树，递归函数{if(p!=NULL){postOrder(p-left);postOrder(p-right);coutp-data;}}//4.基于遍历的操作templateclassTBinaryTreeT::~BinaryTree()//析构函数{cout撤销二叉树:;destroy(root);coutendl;}templateclassTvoidBinaryTreeT::destroy(BinaryNodeT*p)//撤销以p结点为根的子树，后根次序遍历{if(p!=NULL){destroy(p-left);destroy(p-right);coutp-data;//显示撤销结点的次序deletep;}}//【例6.1】构造并遍历二叉树。templateclassTintBinaryTreeT::count()//返回二叉树的结点个数{returncount(root);}templateclassTintBinaryTreeT::count(BinaryNodeT*p)//返回以p结点为根的子树结点个数{if(p==NULL)return0;elsereturn1+count(p-left)+count(p-right);}templateclassTintBinaryTreeT::height()//返回二叉树的高度{returnheight(root);}templateclassTintBinaryTreeT::height(BinaryNodeT*p)//返回以p结点为根的子树高度，后根次序遍历{if(p!=NULL){intlh=height(p-left);//求左子树的高度intrh=height(p-right);return(lh=rh)?lh+1:rh+1;}return0;}templateclassTBinaryNodeT*BinaryTreeT::search(Tvalue)//查找首次出现的值为value结点{returnsearch(root,value);}templateclassTBinaryNodeT*BinaryTreeT::search(BinaryNodeT*p,Tvalue)//在以p为根的子树中查找{//先根次序遍历查找值为value的结点，返回首次出现结点指针，若未找到返回NULLBinaryNodeT*find=NULL;//记载找到结点if(p!=NULL){if(p-data==value)returnp;//查找成功，返回结点指针find=search(p-left,value);//在左子树中查找，find指向找到结点，递归调用if(find==NULL)//若在左子树中未找到find=search(p-right,value);//则继续在右子树中查找，递归调用}returnfind;//返回查找结果}templateclassTBinaryNodeT*BinaryTreeT::getParent(BinaryNodeT*node)//返回node结点的父母结点指针{//若空树、未找到或node为根，返回NULLif(root==NULL||node==NULL||node==root)returnNULL;returngetParent(root,node);}templateclassTBinaryNodeT*BinaryTreeT::getParent(BinaryNodeT*p,BinaryNodeT*node){//在以p为根的子树中查找并返回node结点的父母结点指针BinaryNodeT*find=NULL;if(p!=NULL){if(p-left==node||p-right==node)returnp;find=getParent(p-left,node);if(find==NULL)find=getParent(p-right,node);}returnfind;}//5.构造二叉树templateclassTBinaryTreeT::BinaryTree(Tprelist[],Tinlist[],intn)//以先根和中根序列构造二叉树{//n指定序列长度root=create(prelist,inlist,0,0,n);}templateclassTBinaryNodeT*BinaryTreeT::cre