注册 登录
编程论坛 → 数据结构与算法

发自己写的二叉树的抽象数据类型以及相关算法的实现(采用OOP实现的),大家多交流。

geninsf009 发布于 2008-12-04 21:56， 6421 次点击
类的声明及其相关结构的定义：
所有成员函数都通过测试了，大家只要通过CreateBinaryTree()函数用广义表字符串创建广义表后，就可以调用我写的任何一个成员函数了，可能还有其他更多的关于二叉树的算法，正在补充中，大家参考，共同学习共同交流。
呵呵，这也是我写的最长的抽象数据类型的实现了。
#ifndef BINARYTREE_H
#define BINARYTREE_H

#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include"LinkedStack.h"
#include"LinkedQueue.h"
#include<string.h>

//////////////////////////////////////////////////
//二叉树结点类模板的定义
//////////////////////////////////////////////////
template<class T>
struct BinTreeNode
{
    T data;                     //数据域
    BinTreeNode<T>* leftChild;  //左子结点地址
    BinTreeNode<T>* rightChild; //右子结点地址

    BinTreeNode()               //构造函数
    {
        leftChild=NULL;
        rightChild=NULL;
    };
    BinTreeNode(T x,BinTreeNode<T>* l=NULL
        ,BinTreeNode<T>* r=NULL)               
    {                           //带参数的构造函数
        data=x;
        leftChild=l;
        rightChild=r;
    };
};
////////////////////////////////结点类模板定义结束

//////////////////////////////////////////////////
//stkNode结构
//后序非递归遍历中堆栈结点结构的定义
//////////////////////////////////////////////////
template<class T>
struct stkNode
{
    //指向树结点的指针
    BinTreeNode<T>* ptr;
    //该结点所处的左右子树的标志0:左1:右
    int tag;
    //构造函数
    stkNode(BinTreeNode<T>* N=NULL)
        :ptr(NULL),tag(1){};
};
///////////////////////////////stkNode结构定义结束

//////////////////////////////////////////////////
//二叉树类模板BinaryTree的声明和定义
//用二叉链表实现二叉树的抽象数据类型
//////////////////////////////////////////////////
template<class T>
class BinaryTree
{
public:
    //空构造函数
    BinaryTree():root(NULL){};
    //带参数的构造函数
    BinaryTree(T value):RefValue(value),root(NULL){};
    //以描述字符串为参数的构造函数
    BinaryTree(char* s,T value);
    //复制构造函数
    BinaryTree(BinaryTree<T>& bt);
    //析构函数
    ~BinaryTree()
    {Destroy(root);
    cout<<endl<<"二叉树内存空间释放完毕!"<<endl;};
    //判断二叉树是否为空
    bool IsEmpty(){return root==NULL;};
    //得到当前结点的根结点
    BinTreeNode<T>* getRoot()
    {return root;};
    //得到当前current结点的父结点
    BinTreeNode<T>* Parent(BinTreeNode<T>* current)
    {return (root==NULL||root==current)?
          NULL:Parent(root,current);};
    //返回当前结点的左子结点的指针
    BinTreeNode<T>* LeftChild(BinTreeNode<T>* current)
    {return (current->leftChild==NULL)?
            NULL:current->leftChild;};
    //返回当前结点的右子结点的指针
    BinTreeNode<T>* rightChild(BinTreeNode<T>* current)
    {return (current->rightChild==NULL)?
            NULL:current->rightChild;};
    //返回当前树的高度
    int Height()
    {return Height(root);};
    //返回当前树的总结点数
    int Size()
    {return Size(root);};
    //得到当前二叉树的树根
    BinTreeNode<T>* getRoot()const{return root;};
    //前序遍历当前二叉树
    void preOrder(void(*visit)(BinTreeNode<T>* p))
    {cout<<"前序遍历:";preOrder(root,visit);};
    //前序遍历的非递归算法1
    void preOd1();
    //前序遍历的非递归算法2
    void preOd2();
    //前序遍历的非递归算法3
    void preOd3();
    //中序遍历当前二叉树
    void inOrder(void(*visit)(BinTreeNode<T>* p))
    {cout<<"中序遍历:";inOrder(root,visit);};
    //中序非递归遍历的算法
    void inOd1(void(*visit)(BinTreeNode<T>* p));
    //后序遍历当前二叉树
    void postOrder(void(*visit)(BinTreeNode<T>* p))
    {cout<<"后序遍历:";postOrder(root,visit);};
    //后序非递归遍历二叉树的算法实现
    void postOd(void(*visit)(BinTreeNode<T>* p));
    //按层次顺遍历当前二叉树
    void levelOrder(void(*visit)(BinTreeNode<T>* p));
    //在二叉树中item元素下，插入新元素item2
    bool Insert(const T item1,const T item2,char c);
    //在当前的二叉树中搜索值为T的结点,返回该结点的指针
    BinTreeNode<T>* Find(T item)const;
    //显示二叉树的广义表形式
    void PrintBinaryTree()
    {PrintBinaryTree(root);};
    //判断指定的结点在当前二叉树中是否存在
    bool Exist(const T& x)
    {return Exist(root,x);};
    //利用前序遍历递归创建一棵二叉树
    void CreateBinaryTree(istream& in)
    {CreateBinaryTree(in,root);};
    //通过二叉树的前序序列和中序序列建立一棵二叉树
    void CreateByprein(T* pre,T* in,int n);
    //统计二叉树中所有结点的个数
    int CountNode(){return CountNode(root);};
    //交换每个结点的左右子树
    void ChangeChild();
    //通过数组w[]中的数据元素建立一棵完全二叉树
    void CreateComBinTree(T* w,int n);
    //在当前的二叉树中寻找值为elem的结点的指针,并显示所有的父结点
    BinTreeNode<T>* FindAncestor(T elem)
    {return FindAncestor(root,elem);};
    //统计子当前二叉树中度为1的结点的个数
    int oneDegree()
    {return oneDegree(root);};
    //统计子当前二叉树中度为1的结点的个数
    int towDegree()
    {return twoDegree(root);};
    //统计子当前二叉树中度为0的结点的个数
    int zeroDegree()
    {return zeroDegree(root);};
    //计算指定结点p在当前二叉树中的深度
    int Depth(BinTreeNode<T>* p)
    {return Depth(p,root);};
    //计算当前二叉树的宽度
    int Width();
    //删除当前二叉树所有的叶子结点
    void deleteLeaf()
    {deleteLeaf(root);};
    //展出当前二叉树中的最大值
    T maxVal()
    {return maxVal(root);};
    //以前序方式显示当前二叉树中所有结点所在的层次
    void preDepth()
    {preDepth(root);};
    //双序遍历一棵二叉树
    void DoubleOrder()
    {DoubleOrder(root);};
    //前序显示二叉树每个结点及其深度
    void PrintDepth()
    {PrintDepth(root,1);};
    void SearchpreOrder(int k)
    {cout<<SearchpreOrder(k,root)->data;};
    //判断一棵二叉树是否是完全二叉树
    bool IsCompleteBinTree();
    //递归:求子二叉树subTree的宽度
    void FindWidth(BinTreeNode<T>* subTree
        ,int* count,int i);
    //求当前二叉树的宽度
    int FindWidth();
    //递归:求解指定结点的子孙的个数
    int NumOfSons(BinTreeNode<T>* p);
    //调用上面的函数
    int NumOfSons()
    {return NumOfSons(root);};
    //递归:通过前序遍历来统计二叉树中结点总个数
    int PreOrderCount(BinTreeNode<T>* subTree);
    //调用上面的函数
    int PreOrderCount()
    {return PreOrderCount(root);};
    //递归:通过前序序列来创建一棵二叉树
    int PreOrderCreate(char* s,
        int start,BinTreeNode<T>*& subTree);
    void PreOrderCreate(char* s)
    {PreOrderCreate(s,0,root);};
protected:
    //二叉树的根结点指针
    BinTreeNode<T>* root;
    //数据输入停止的标志
    T RefValue;
    
    //读入描述字符串建立二叉树
    void CreateBinTree(char* BinStr
        ,BinTreeNode<T>*& subTree);
    //用输描述字符串s递归创建一个二叉树
    void CreateBinaryTree(istream& in
        ,BinTreeNode<T>*& subTree);
    //删除子树操作
    void Destroy(BinTreeNode<T>*& subTree);
    //在指定的子树中查找元素x是否存在
    bool Exist(BinTreeNode<T>* subTree,const T& x);
    //复制操作
    BinTreeNode<T>* Copy(BinTreeNode<T>* orignode);
    //返回树subTree的高度
    int Height(BinTreeNode<T>* subTree);
    //返回树的总结点数
    int Size(BinTreeNode<T>* subTree);
    //返回树subTree中,current结点的父结点
    BinTreeNode<T>* Parent(BinTreeNode<T>* subTree
        ,BinTreeNode<T>* current);
    //在子树subTree中搜索值为x的结点的指针
    BinTreeNode<T>* Find(BinTreeNode<T>* subTree
        ,const T& x)const;    
    //搜索并前序遍历输出
    void Traverse(BinTreeNode<T>* subTree
        ,ostream& out);
    //前序遍历
    void preOrder(BinTreeNode<T>* subTree
        ,void(*visit)(BinTreeNode<T>* p));
    //中序遍历
    void inOrder(BinTreeNode<T>* subTree
        ,void(*visit)(BinTreeNode<T>* p));
    //后序遍历
    void postOrder(BinTreeNode<T>* subTree
        ,void(*visit)(BinTreeNode<T>* p));
    //显示二叉树的广义表形式
    void PrintBinaryTree(BinTreeNode<T>* subTree);
    //通过前序序列和中序序列建立一棵二叉树
    BinTreeNode<T>* CreateByprein1(T* pre,T* in,int n);
    //统计二叉树subTree子树中所有结点的个数
    int CountNode(BinTreeNode<T>* subTree);
    //把所有的结点读入到一个数组中
    void GetNode(BinTreeNode<T>**);
    //找具有指定值Elem的结点的指针,并显示其所有祖先结点
    BinTreeNode<T>* FindAncestor(
        BinTreeNode<T>* subTree,T elem);
    //递归统计子树subTree中度为1的结点的个数
    int oneDegree(BinTreeNode<T>* subTree);
    //递归统计子树subTree中度为2的结点的个数
    int twoDegree(BinTreeNode<T>* subTree);
    //递归统计子树subTree中度为0的结点的个数
    int zeroDegree(BinTreeNode<T>* subTree);
    //计算指定结点p在子树subTree中的深度
    int Depth(BinTreeNode<T>* p
        ,BinTreeNode<T>* subTree);
    //递归删除子树subTree里叶子结点
    void deleteLeaf(BinTreeNode<T>* subTree);
    //递归找出子树subTree中数据最大值
    T maxVal(BinTreeNode<T>* subTree);
    //以前序的序列显示每个结点所在的层次
    void preDepth(BinTreeNode<T>* subTree);
    //双序遍历一棵二叉树
    void DoubleOrder(BinTreeNode<T>* subTree);
    //以前序方式显示每个结点及其深度
    void PrintDepth(BinTreeNode<T>* subTree
        ,int depth);
    //递归:得到中序序列中第k个结点的指针
    BinTreeNode<T>* SearchpreOrder(int k
        ,BinTreeNode<T>* subTree);
    //递归:给定前序序列,创建所有可能的二叉树
    void CtreateBypre(char* s,int begin,int end);
    //递归:通过带#的前序序列来创建一棵二叉树
   
    //友元重载>>输入运算符输入二叉树
    friend istream& operator>>(istream& in
        ,BinaryTree<T>& Tree);
    //友元重载<<输出运算符输出二叉树
    friend ostream& operator<<(ostream& out
        ,BinaryTree<T>& Tree);
    //友元函数,判断两棵二叉树是否相等
    friend bool Equal(BinTreeNode<T>* a
        ,BinTreeNode<T>* b);
    //友元函数,判断两棵二叉树是否相等
    friend bool BinTreeEqual(BinaryTree<T>& BT1
        ,BinaryTree<T>& BT2);
    //友元重载==运算符
    friend bool operator==(BinaryTree<T>& BT1
        ,BinaryTree<T>& BT2);
};
////////////////////////////////BinaryTree声明结束

[[it] 本帖最后由 geninsf009 于 2008-12-4 22:18 编辑 [/it]]
49 回复
#2
geninsf0092008-12-04 21:57
构造函数：
//////////////////////////////////////////////////
//以描述字符串为参数的构造函数
//////////////////////////////////////////////////
template<class T>
BinaryTree<T>::BinaryTree(char* s,T value)
{
    //通过描述字符串创建一棵二叉树,
    //把根结点放入root
    CreateBinTree(s,root);
    RefValue=value;
};
//////////////////////////////////////构造函数结束

//////////////////////////////////////////////////
//复制构造函数
//通过已经存在的二叉树bt构造新二叉树
//////////////////////////////////////////////////
template<class T>
BinaryTree<T>::BinaryTree(BinaryTree<T>& bt)
{
    //复制二叉树root
    root=bt.Copy(bt.root);
    //结束符的复制
    RefValue=bt.RefValue;
};
//////////////////////////////////复制构造函数结束
#3
geninsf0092008-12-04 21:58
前序遍历就写了好几种：
//////////////////////////////////////////////////
//preOd1()公又成员函数
//前序遍历的非递归算法的实现
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::preOd1()
{
    //遍历过程中回溯用的堆栈
    LinkedStack<BinTreeNode<T>* > LS;
    //把空指针放入堆栈底部
    LS.Push(NULL);
    //结点指针
    BinTreeNode<T>* p=root;
    //前序遍历的过程
    cout<<"前序非递归遍历方法1:";
    while(p!=NULL)
    {
        //显示结点
        cout<<p->data<<" ";
        //左不空,右不空
        if(p->leftChild!=NULL
            && p->rightChild!=NULL)
        {
            //把右子结点压入堆栈
            LS.Push(p->rightChild);
            //进入左子树
            p=p->leftChild;
        }
        //左不空,右空
        else if(p->leftChild!=NULL
            && p->rightChild==NULL)
            //进入左子树
            p=p->leftChild;
        //左空,右不空
        else if(p->leftChild==NULL
            && p->rightChild!=NULL)
            //进入右子树
            p=p->rightChild;
        //左空,右空
        else if(p->leftChild==NULL
            && p->rightChild==NULL)
            //回溯
            LS.Pop(p);
    }    
};
//////////////////////////////////preOd1()函数结束
#4
geninsf0092008-12-04 21:58
//////////////////////////////////////////////////
//公有成员函数preOd2()
//第二种非递归前序遍历的算法
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::preOd2()
{
    //回溯用的堆栈
    LinkedStack<BinTreeNode<T>* > LS;
    //结点遍历指针
    BinTreeNode<T>* p=root;
    //先把空指针入堆栈
    LS.Push(NULL);
    //遍历的过程
    cout<<"前序非递归遍历方法2:";
    while(p!=NULL)
    {
        cout<<p->data<<" ";         //访问当前结点
        if(p->rightChild!=NULL)     //如果右子结点不空
            LS.Push(p->rightChild); //把由子结点指针入栈
        
        if(p->leftChild!=NULL)      //如果左子结点不空
            p=p->leftChild;         //进入左子树
        else                        //如果左子树为空
            LS.Pop(p);              //回溯到右子树
    }
};
//////////////////////////////////preOd2()函数结束
#5
geninsf0092008-12-04 21:59
//////////////////////////////////////////////////
//公有成员函数preOd3()
//第三种非递归前序遍历的算法
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::preOd3()
{
    //回溯用的堆栈
    LinkedStack<BinTreeNode<T>* > LS;
    //结点遍历指针
    BinTreeNode<T>* p;
    //先把根结点指针入堆栈
    LS.Push(root);
    //遍历的过程
    cout<<"前序非递归遍历方法3:";
    while(!LS.IsEmpty())
    {
        //从堆栈取一个元素
        LS.Pop(p);
        //访问p结点
        cout<<p->data<<" ";
        //若右子树不空则入栈
        if(p->rightChild!=NULL)
            LS.Push(p->rightChild);
        //若左子树不空则入栈
        if(p->leftChild!=NULL)
            LS.Push(p->leftChild);
    };    
};
//////////////////////////////////////preOd3()函数
#6
geninsf0092008-12-04 21:59
//////////////////////////////////////////////////
//公有成员函数levelOrder()函数
//按层次顺遍历当前二叉树
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::levelOrder(
        void(*visit)(BinTreeNode<T>* p))
{
    //层次遍原始历用的队列
    LinkedQueue<BinTreeNode<T>* > Q;
    //指针
    BinTreeNode<T>* p=root;
    //先把根结点入栈
    Q.EnQueue(p);
    //层次遍历
    while(!Q.IsEmpty())
    {
        //先从队列中读取一个元素
        Q.DeQueue(p);
        //访问该结点
        visit(p);
        //把左子结点入队列
        if(p->leftChild!=NULL)
            Q.EnQueue(p->leftChild);
        //把右子结点入队列
        if(p->rightChild!=NULL)
            Q.EnQueue(p->rightChild);
    };
};
//////////////////////////////levelOrder()函数结束
#7
geninsf0092008-12-04 22:00
//////////////////////////////////////////////////
//公又成员函数inOd1()
//非递归遍历二叉树的算法
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::inOd1(
     void(*visit)(BinTreeNode<T>* p))
{
    //递归工作堆栈
    LinkedStack<BinTreeNode<T>* > LS;
    //结点指针变量
    BinTreeNode<T>* p=root;

    //遍历的过程
    cout<<"非递归中序遍历的第1种方法:";
    do
    {
        //向左递归
        while(p!=NULL)
        {
            //压入堆栈
            LS.Push(p);
            p=p->leftChild;
        };

        //如果堆栈不空
        if(!LS.IsEmpty())
        {
            //弹出堆栈
            LS.Pop(p);
            //访问结点
            visit(p);
            //进入右子树
            p=p->rightChild;
        };
    }
    while(p!=NULL || !LS.IsEmpty());
};
///////////////////////////////////inOd1()函数结束
#8
geninsf0092008-12-04 22:00
//////////////////////////////////////////////////
//公又成员函数postOd()函数
//后序遍历二叉树的算法实现
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::postOd(
        void(*visit)(BinTreeNode<T>* p))
{
    LinkedStack<stkNode<T> > S;      //回溯用的堆栈
    stkNode<T> w;                    //结点变量
    BinTreeNode<T>* p=root;          //遍历用的指针

    do
    {
        while(p!=NULL)               //左子树经过的结点加标志"L"入栈
        {
            w.ptr=p;                 
            w.tag=0;
            S.Push(w);
            p=p->leftChild;          //向左子树的方向走下去
        };
        int continue1=1;             //继续循环的标志,用于R
        while(continue1!=0 && !S.IsEmpty())
        {
            S.Pop(w);p=w.ptr;        //堆栈不空就退栈
            switch(w.tag)            //判断从堆栈弹出元素的标志
            {
            case 0:
                w.tag=1;            
                S.Push(w);           //从左子树退回，修改tag
                continue1=0;
                p=p->rightChild;     //从右子树往下走
                break;
            case 1:
                visit(p);            //从右子树退回访问根结点
                break;
            }
        }
    }while(!S.IsEmpty());
    cout<<endl;
};
//////////////////////////////////postOd()函数结束
#9
geninsf0092008-12-04 22:00
//////////////////////////////////////////////////
//Find()公有成员函数
//在当前的二叉树中搜索值为T的结点,返回该结点的指针
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::Find(T item)const
{
    //寻找以root树根的子树中item项结点的指针
    return Find(root,item);
};
////////////////////////////////////Find()函数结束

//////////////////////////////////////////////////
//Insert()私有成员函数
//在二叉树中item元素下，插入新元素item2
//////////////////////////////////////////////////
template<class T>
bool BinaryTree<T>::Insert(const T item1,const T item2,char c)
{
    //找到item1的结点的指针
    BinTreeNode<T>* p=Find(item1);
    if(p==NULL)
    {
        cout<<"没有找到item1对应的结点!"<<endl;
        return false;
    }
    else
    {
        //在左子树位置插入
        if(c=='l')
        {
            //左子树为空可以插入
            if(p->leftChild==NULL)
            {
                BinTreeNode<T>* l=new
                    BinTreeNode<T>(item2);
                p->leftChild=l;
                return true;
            }
            else
            {
                cout<<"左子树不空，无法插入!"<<endl;
                return false;
            }
        }
        //在右子树的位置插入
        else if(c=='r')
        {
            //右子树为空可以插入
            if(p->rightChild==NULL)
            {
                BinTreeNode<T>* r=new
                    BinTreeNode<T>(item2);
                p->rightChild=r;
                return true;
            }
            else
            {
                cout<<"右子树不空,无法插入!"<<endl;
                return false;
            }
        }
        else
        {
            cout<<"位提示在左还是右插入!"<<endl;
            return false;
        }
    }
};
//////////////////////////////Insert()私有函数结束
#10
geninsf0092008-12-04 22:00
//////////////////////////////////////////////////
//CreateBinTree()私有成员函数
//通过广义表描述字符串建立一棵二叉树,通过指针返回
//例如A(B,C(E,F))#
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::CreateBinTree(char* BinStr
            ,BinTreeNode<T>*& subTree)
{
    //逐个读取字符串
    int i=0;               //游标
    int k=0;               //处理标志,0表示根结点,1表示左子树,2表示
    char s;                //存放每次取出的字符
    LinkedStack<BinTreeNode<char>*> LS;
                           //创建二叉树过程中用到的结点指针堆栈
    BinTreeNode<char>* p;  //结点指针变量
    BinTreeNode<char>* t;  //存放从堆栈中弹出的内容
    BinTreeNode<char>* top;//用于存放从堆栈中取出的栈顶元素
         
    while(BinStr[i]!='#')
    {
        s=BinStr[i];
        switch(s)
        {
        case '(':
            LS.Push(p);  //把当前p的内容入栈
            k=1;         //进入左子树的处理
            break;
        case ',':
            k=2;         //进入右子树的处理
            break;
        case ')':
            LS.Pop(t);   //弹出堆栈的内容
            break;
        default:
            //如果取出的字母
            {
                //如果处理的是根结点
                if(k==0)
                {
                    //新建一个结点
                    p=new BinTreeNode<char>(s);
                    //把该指针作为树的指针返回
                    subTree=p;
                }
                //如果处理的是右子树
                else if(k==1)
                {
                    //新建一个接点
                    p=new BinTreeNode<char>(s);
                    //取得栈顶结点
                    LS.getTop(top);
                    //把该结点挂入栈顶的左指针域
                    top->leftChild=p;
                }
                //如果处理的是左子树
                else
                {
                    //新建一个接点
                    p=new BinTreeNode<char>(s);
                    //取得栈顶结点
                    LS.getTop(top);
                    //把该结点挂入栈顶的左指针域
                    top->rightChild=p;
                };
                break;
            };
        };
        i++;
    }
};
///////////////////////////////CreateBinTree()结束
#11
geninsf0092008-12-04 22:01
//////////////////////////////////////////////////
//CreateBinaryTree()私有成员函数
//用输描述字符流递归递归创建一个二叉树
//输入的字符流必须是前序序列的二叉树
//每个叶子结点后都要加上两个#的结束符号结点
//////////////////////////////////////////////////
template<class T>
void CreateBinaryTree(istream& in
            ,BinTreeNode<T>* subTree)
{
    T item;
    //递归建立二叉树
    if(!in.eof())
    {
        in>>item;               //输入字符
        if(item!=RefValue)      //如果没有到结束符号
        {
            subTree=new BinTreeNode<T>(item);
                                //新建子树的根结点
            if(subTree==NULL)
            {cout<<"根结点内存分配失败!"<<endl;exit(1);}
            
            CreateBinaryTree(in,subTree->leftChild);
                                //递归建立左子树
            CreateBinaryTree(in,subTree->rightChild);
                                //递归建立右子树
        }
        else
            return NULL;
    }
};
////////////////////////CreateBinaryTree()函数结束
#12
geninsf0092008-12-04 22:01
//////////////////////////////////////////////////
//私有成员函数Destroy() 释放二叉树的存储空间
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::Destroy(BinTreeNode<T>*& subTree)
{
    if(subTree!=NULL)
    {
        //递归释放左子树
        Destroy(subTree->leftChild);
        //递归释放右子树
        Destroy(subTree->rightChild);
        //释放当前结点的空间
        delete subTree;
    };
};
/////////////////////////////////Destroy()函数结束
#13
geninsf0092008-12-04 22:02
//////////////////////////////////////////////////
//Exist()私有成员函数
//在指定的子树中查找元素x是否存在
//////////////////////////////////////////////////
template<class T>
bool BinaryTree<T>::Exist(BinTreeNode<T>* subTree
                ,const T& x)
{
    //若子树不空
    if(subTree!=NULL)
    {
        //如果结点元素相等
        if(subTree->data==x)
            return true;
        else
            //递归比较左右子树
            return Exist(subTree->leftChild,x)
            ||Exist(subTree->rightChild,x);
    }
    else
        return false;
};
///////////////////////////////////Exist()函数结束
#14
geninsf0092008-12-04 22:02
//////////////////////////////////////////////////
//私有成员函数Copy()   二叉树的复制
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::Copy(
            BinTreeNode<T>* orignode)
{
    if(orignode!=NULL)
    {
        //依据orignode的内容,新建一个结点
        BinTreeNode<char>* p=new
            BinTreeNode<char>(orignode->data);
        //递归复制orignode的左子树
        p->leftChild=Copy(orignode->leftChild);
        //递归复制orignode的右子树
        p->rightChild=Copy(orignode->rightChild);
        return p;
    }
    else
        return NULL;
};
////////////////////////////////////Copy()函数结束
#15
geninsf0092008-12-04 22:02
//////////////////////////////////////////////////
//Height()私有成员函数
//返回树subTree的高度
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::Height(BinTreeNode<T>* subTree)
{
    //如果树为空则返回0
    if(subTree==NULL)
        return 0;
    else
    {
        //左子树深度
        int p1=Height(subTree->leftChild);
        // 右子树深度
        int p2=Height(subTree->rightChild);
        if(p1>=p2)
            return 1+p1;
        else
            return 1+p2;
    };
};
//////////////////////////////////Height()函数结束
#16
geninsf0092008-12-04 22:03
//////////////////////////////////////////////////
//私有成员函数Size()
//得到二叉树的总接点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::Size(BinTreeNode<T>* subTree)
{
    //子树为空,则结点数为0
    if(subTree==NULL)
        return 0;
    else
        return 1+Size(subTree->leftChild)
        +Size(subTree->rightChild);
};
////////////////////////////////////Size()函数结束
#17
geninsf0092008-12-04 22:03
//////////////////////////////////////////////////
//Parent()私有成员函数
//返回树subTree中,current结点的父结点
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::Parent(
                     BinTreeNode<T>* subTree
                    ,BinTreeNode<T>* current)
{
    if(subTree!=NULL)
    {
        //如果subTree就是current的父结点
        if(subTree->leftChild==current
            || subTree->rightChild==current)
            return subTree;
        else
        {
            BinTreeNode<T> *pl,*pr;
            //递归搜索左子树
            pl=Parent(subTree->leftChild,current);
            //递归搜索右子树
            pr=Parent(subTree->rightChild,current);
            //只要其中一个不空就返回
            if(pl!=NULL)
                return pl;
            else if(pr!=NULL)
                return pr;
            else
                return NULL;
        }
    }
    else
        return NULL;
};
//////////////////////////////////Parent()函数结束
#18
geninsf0092008-12-04 22:03
//////////////////////////////////////////////////
//Find()私有成员函数
//在子树subTree中搜索值为x的结点的指针
//如果不存在该结点就返回NULL
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::Find(
            BinTreeNode<T>* subTree
                    ,const T& x)const
{
    if(subTree!=NULL)
    {
        //如果subTree里的内容就是x
        if(subTree->data==x)
            return subTree;
        //如果不是
        else
        {
            BinTreeNode<T>* pl=
                Find(subTree->leftChild,x);
            BinTreeNode<T>* pr=
                Find(subTree->rightChild,x);
            //递归搜索左右子树
            if(pl!=NULL)
                return pl;
            else if(pr!=NULL)
                return pr;
            //左右子树中都没有x结点就返回NULL
            else
                return NULL;
        }
    }
    else
        return NULL;
};
////////////////////////////////////Find()函数结束
#19
geninsf0092008-12-04 22:04
//////////////////////////////////////////////////
//私有成员函数Traverse()
//搜索并前序遍历输出
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::Traverse(BinTreeNode<T>* subTree
                ,ostream& out)
{
    if(subTree!=NULL)
    {
        //显示结点信息
        out<<subTree->data<<" ";
        //递归遍历左右子树
        Traverse(subTree->leftChild,out);
        Traverse(subTree->rightChild,out);
    }
};
////////////////////////////////Traverse()函数结束
#20
geninsf0092008-12-04 22:04
//////////////////////////////////////////////////
//友元重载>>输入运算符输入二叉树
//////////////////////////////////////////////////
template<class T>
istream& operator>>(istream& in,BinaryTree<T>& Tree)
{
    //输入儿茶树的描述字符串
    char s[50];
    in>>s;
    BinTreeNode<T>* r;
    Tree.CreateBinTree(s,r);
    Tree.root=r;
    return in;
};
///////////////////////////////////////友元重载结束

///////////////////////////////////////////////////
//友元重载<<输出运算符输出二叉树
///////////////////////////////////////////////////
template<class T>
ostream& operator<<(ostream& out,BinaryTree<T>& Tree)
{
    Tree.Traverse(Tree.root,out);
    return out;
};
///////////////////////////////////////友元重载结束
#21
geninsf0092008-12-04 22:05
///////////////////////////////////////////////////
//友元函数Equal()
//比较以a,b为根结点的二叉树是否相等
///////////////////////////////////////////////////
template<class T>
bool Equal(BinTreeNode<T>* a,BinTreeNode<T>* b)
{
    //先比较子树的根结点
    if(a==NULL && b==NULL)
        return true;
    //根结点相等而且左右子树递归相等
    else if(a!=NULL && b!=NULL && a->data==b->data
            && Equal(a->leftChild,b->leftChild)
            && Equal(a->rightChild,b->rightChild))
    {
            return true;
    }
    else
        //不相等就返回false
        return false;
};
///////////////////////////友元函数Equanl()函数结束
#22
geninsf0092008-12-04 22:05
///////////////////////////////////////////////////
//友元函数BinTreeEqual()
//比较两个二叉树是否相等
///////////////////////////////////////////////////
template<class T>
bool BinTreeEqual(BinaryTree<T>& BT1,BinaryTree<T>& BT2)
{
    //调用Equal(BinTreeNode<T>* a,BinTreeNode<T>* b)
    //递归函数
    return Equal(BT1.root,BT2.root);
};
////////////////////////////友元函数Equal()函数结束
#23
geninsf0092008-12-04 22:06
///////////////////////////////////////////////////
//CreateByprein()公有成员函数
//通过二叉树的前序序列和中序序列建立一棵二叉树
///////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::CreateByprein(T* pre,T* in,int n)
{
    root=CreateByprein1(pre,in,n);
};
////////////////////////////CreateByprein()函数结束

///////////////////////////////////////////////////
//私有成员函数CreateByprein()
//通过前序序列和中序序列建立一棵二叉树
//输入的前序和中序序列必须一'#'结束
//pre是前序序列,in是中序序列,n为二叉树结点个数
///////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::CreateByprein1(T* pre
                        ,T* in,int n)
{
    //创建的子树的根结点指针
    BinTreeNode<T>* p;

    //递归结束的条件
    if(n==0)
        //如果二叉树长度为0,返回空
        return NULL;

    T s=pre[0];             //在前序中的第一个元素就是根结点
    p=new BinTreeNode<T>(s);//根据取出的根结点元素创建根结点

    //在根据前序得到的根结点拆分中序序列的过程
    for(int m=0;m<n;m++)    //在中序的序列中查找根结点的位置
    {
        if(in[m]==s)        //m就是根结点在中序中的位置
            break;
    };

    //得到左子树的前序和中序
    T* lp=new T[m];             //得到左子树的前序
    for(int i=0;i<m;i++)
        lp[i]=pre[i+1];

    T* li=new T[m];             //得到左子树的中序
    for(i=0;i<m;i++)
        li[i]=in[i];

    T* rp=new T[n-m+1];         //得到右子树的前序
    for(i=0;i<n-m+1;i++)
        rp[i]=pre[i+m+1];

    T* ri=new T[n-m+1];         //得到右子树的中序
    for(i=0;i<n-m+1;i++)
        ri[i]=in[i+m+1];

    //递归创建左子树
    p->leftChild=CreateByprein1(lp,li,m);
    //递归创建右子树
    p->rightChild=CreateByprein1(rp,ri,n-m-1);

    //释放内存空间
    delete lp;
    delete li;
    delete rp;
    delete ri;
    //返回当前根结点的指针
    return p;
};
////////////////////////////CreateByprein()函数结束
#24
geninsf0092008-12-04 22:06
///////////////////////////////////////////////////
//友元重载==运算符
///////////////////////////////////////////////////
template<class T>    
bool operator==(BinaryTree<T>& BT1
                ,BinaryTree<T>& BT2)
{
    //判断两个二叉树是否相等
    return BinTreeEqual(BT1,BT2);
};
///////////////////////////////////////友元重载结束
#25
geninsf0092008-12-04 22:07
//////////////////////////////////////////////////
//私有成员函数PrintBinaryTree()函数
//递归显示二叉树的广义表形式
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::PrintBinaryTree(
                BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        //显示根结点的内容
        cout<<subTree->data;
        //如果不是叶子结点就递归显示子树的内容
        if(subTree->leftChild!=NULL
            || subTree->rightChild!=NULL)
        {
            //显示左括号
            cout<<"(";
            //递归显示左子树
            PrintBinaryTree(subTree->leftChild);
            //显示,
            cout<<",";
            //递归显示右子树
            PrintBinaryTree(subTree->rightChild);
            //显示右括号
            cout<<")";
        }
    };
};
/////////////////////私有PrintBinaryTree()函数结束
#26
geninsf0092008-12-04 22:07
//////////////////////////////////////////////////
//私有成员函数CountNode()函数
//递归统计以subTree为根的子树的所有的结点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::CountNode(BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
        //返回左右子树结点数之和并加1
        return 1+CountNode(subTree->leftChild)
            +CountNode(subTree->rightChild);
    else
        //如果为空则结点数为0
        return 0;
};
///////////////////////////////CountNode()函数结束
#27
geninsf0092008-12-04 22:07
//////////////////////////////////////////////////
//GetNode()私有成员函数
//把二叉树当前的所有的结点按层次顺序放入一个数组
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::GetNode(BinTreeNode<T>** w)
{
    //数组下标的计数器
    int i=0;
    //层次遍原始历用的队列
    LinkedQueue<BinTreeNode<T>* > Q;
    //指针
    BinTreeNode<T>* p=root;
    //先把根结点入栈
    Q.EnQueue(p);
    //层次遍历
    while(!Q.IsEmpty())
    {
        //先从队列中读取一个元素
        Q.DeQueue(p);
        //把该结点送入数组
        w[i]=p;i++;
        //把左子结点入队列
        if(p->leftChild!=NULL)
            Q.EnQueue(p->leftChild);
        //把右子结点入队列
        if(p->rightChild!=NULL)
            Q.EnQueue(p->rightChild);
    };
};
/////////////////////////////////GetNode()函数结束
#28
geninsf0092008-12-04 22:07
//////////////////////////////////////////////////
//ChangeChild()函数
//交换每个结点的左右子树
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::ChangeChild()
{
    //得到当前二叉树的结点的个数
    int n=CountNode(root);
    //定义一个存放每个结点的数组w[]
    BinTreeNode<T>** w=new BinTreeNode<T>*[n];
    //把所有的结点放入数组w中去
    GetNode(w);
    //交换每个结点的左右子树
    BinTreeNode<T>* tempt;
    for(int i=0;i<n;i++)
    {
        tempt=w[i]->leftChild;
        w[i]->leftChild=w[i]->rightChild;
        w[i]->rightChild=tempt;
    }
};
/////////////////////////////ChangeChild()子树结束
#29
geninsf0092008-12-04 22:08
//////////////////////////////////////////////////
//CreateComBinTree()公有成员函数
//通过数组w[]中的数据元素建立一棵完全二叉树
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::CreateComBinTree(T* w,int n)
{
    //定义一个结点指针数组
    BinTreeNode<T>** pw=new BinTreeNode<T>*[n];
    //把这n个数据封装成结点,并将结点指针放入数组
    cout<<endl;
    for(int i=0;i<n;i++)
        pw[i]=new BinTreeNode<T>(w[i]);
    //根据完全二叉树中父子结点中标号的关系建立二叉链表
    //左右子结点在数组中的下标
    int left,right;
    //遍历所有的分支结点
    for(i=0;i<=int(n/2)-1;i++)
    {
        //得到第i个结点的左右子结点的下标
        left=2*i+1;
        right=2*i+2;
        //把左子结点挂入第i个结点的左子树
        pw[i]->leftChild=pw[left];
        //如果有右子结点就挂入第i个结点的右子树
        if(right<=n-1)
            pw[i]->rightChild=pw[right];
    };
    //把第一个结点作为root
    root=pw[0];
};
////////////////////////CreateComBinTree()函数结束
#30
geninsf0092008-12-04 22:08
//////////////////////////////////////////////////
//FindAcestor()私有成员函数
//找具有指定值Elem的结点的指针,并显示其所有祖先结点
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::FindAncestor(
        BinTreeNode<T>* subTree,T elem)
{
    //如果subTree不空
    if(subTree!=NULL)
    {
        //如果当前结点就含有指定元素值
        if(subTree->data==elem)
            return subTree;
        //在左右子树中进行递归搜索
        BinTreeNode<T>* pl=
            FindAncestor(subTree->leftChild,elem);
        BinTreeNode<T>* pr=
            FindAncestor(subTree->rightChild,elem);
        //如果在左子树中能找到
        if(pl!=NULL)
        {
            //显示作为父结点的当前结点
            cout<<subTree->data<<" ";
            return pl;
        }
        //如果在右子树中能找到
        else if(pr!=NULL)
        {
            //显示作为父结点的当前结点
            cout<<subTree->data<<" ";
            return pr;
        }
        else
            //返回空指针
            return NULL;        
    }
    else
        //返回空空指针
        return NULL;
};
////////////////////////////FindAncestor()函数结束
#31
geninsf0092008-12-04 22:08
//////////////////////////////////////////////////
//oneDegree()私有成员函数
//递归统计子树subTree中度为1的结点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::oneDegree(BinTreeNode<T>* subTree)
{
    //子树不空
    if(subTree!=NULL)
    {
        //如果左右子树都不空
        if(subTree->leftChild!=NULL
            && subTree->rightChild!=NULL)
            //递归统计左右子树,并返回两者的和
            return oneDegree(subTree->leftChild)
            +oneDegree(subTree->rightChild);
        //如果左不空右空,则递归统计左子树,再加上当前结点
        else if(subTree->leftChild!=NULL
            && subTree->rightChild==NULL)
            return oneDegree(subTree->leftChild)+1;
        //如果左空右不空,则递归统计右子树,在加上当前结点
        else if(subTree->leftChild==NULL
            && subTree->rightChild!=NULL)
            return oneDegree(subTree->rightChild)+1;
        //左右子树都是空的说明是叶子结点,返回0
        else
            return 0;
    }
    //空则返回0
    else
        return 0;
};
///////////////////////////////oneDegree()函数结束
#32
geninsf0092008-12-04 22:09
//////////////////////////////////////////////////
//twodegree()私有成员函数
//递归统计子树subTree中度为2的结点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::twoDegree(BinTreeNode<T>* subTree)
{
    //子树不空
    if(subTree!=NULL)
    {
        //如果左右子树都不空
        if(subTree->leftChild!=NULL
            && subTree->rightChild!=NULL)
            //递归统计左右子树,并返回两者的和,并加1
            return 1+twoDegree(subTree->leftChild)
            +twoDegree(subTree->rightChild);
        //如果左空右不空,则递归统计右子树
        else if(subTree->leftChild==NULL
            && subTree->rightChild!=NULL)
            return twoDegree(subTree->rightChild);
        //如果左不空右空,则递归统计左子树
        else if(subTree->leftChild!=NULL
            && subTree->rightChild==NULL)
            return twoDegree(subTree->leftChild);
        //叶子结点
        else
            return 0;
    }
    else
        return 0;
};
///////////////////////////////twoDegree()函数结束
#33
geninsf0092008-12-04 22:09
//////////////////////////////////////////////////
//zeroDegree()私有成员函数
//递归统计子树subTree中度为0的结点的个数
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::zeroDegree(BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        //如果左右子树都不空
        if(subTree->leftChild==NULL
            && subTree->rightChild==NULL)
            //递归统计左右子树,并返回两者的和,并加1
            return 1;
        //如果左空右不空,则递归统计右子树
        else if(subTree->leftChild==NULL
            && subTree->rightChild!=NULL)
            return zeroDegree(subTree->rightChild);
        //如果左不空右空,则递归统计左子树
        else if(subTree->leftChild!=NULL
            && subTree->rightChild==NULL)
            return zeroDegree(subTree->leftChild);
        //叶子结点
        else
            return zeroDegree(subTree->rightChild)
            +zeroDegree(subTree->rightChild);
    }
    else
        return 0;
};
//////////////////////////////zeroDegree()函数结束
#34
geninsf0092008-12-04 22:09
//////////////////////////////////////////////////
//Depth()私有成员
//计算指定结点p在子树subTree中的深度
//////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::Depth(BinTreeNode<T>* p
            ,BinTreeNode<T>* subTree)
{
    //如果子树不空
    if(subTree!=NULL)
    {
        //如果就是根结点则深度为1
        if(p==subTree)
            return 1;
        else
        {
            //递归求p在左子树里的深度
            int ld=Depth(p,subTree->leftChild);
            //递归求p在右子树里的深度
            int rd=Depth(p,subTree->rightChild);
            if(ld!=0)
                //左子树深度加1
                return 1+ld;
            else if(rd!=0)
                //右子树深度加1
                return 1+rd;
            else
                //没有找到则返回0
                return 0;
        }
    }
    else
        //空则深度为0
        return 0;
};
///////////////////////////////////Depth()函数结束
#35
geninsf0092008-12-04 22:10
//////////////////////////////////////////////////
//私有成员函数deleteLeaf()
//删除子树subTree里的所有的叶子结点
//本算法是寻找叶子结点的父结点
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::deleteLeaf(BinTreeNode<T>* subTree)
{
    //如果子树不空
    if(subTree!=NULL)
    {
        //如果当前结点就是叶子结点
        if(subTree->leftChild==NULL
            && subTree->rightChild==NULL)
            return;
        else
        {
            //如果左子结点是叶子结点
            if(subTree->leftChild->leftChild==NULL
                && subTree->leftChild->rightChild==NULL)
                //删除该左子结点
                subTree->leftChild=NULL;
            else
                //递归删除左子树的叶子
                deleteLeaf(subTree->leftChild);
            
            //如果右子结点是叶子结点
            if(subTree->rightChild->leftChild==NULL
                && subTree->rightChild->rightChild==NULL)
                //删除该右子结点
                subTree->rightChild=NULL;
            else
                //递归删除右子树的叶子
                deleteLeaf(subTree->rightChild);
        }
    };
};
//////////////////////////////deleteLeaf()函数结束
#36
geninsf0092008-12-04 22:10
//////////////////////////////////////////////////
//maxVal()私有成员函数
//递归找出子树subTree中结点的最大值
//////////////////////////////////////////////////
template<class T>
T BinaryTree<T>::maxVal(BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        T maxl,maxr;

        //求出左子树的最大值
        maxl=maxVal(subTree->leftChild);
        //求出右子树的最大值
        maxr=maxVal(subTree->rightChild);

        //返回根结点，左子结点,右子结点中最大的那个
        if(subTree->data>maxl && subTree->data>maxr)
            return subTree->data;
        else if(maxl>subTree->data && maxl>maxr)
            return maxl;
        else
            return maxr;
    }
    else
        return 0;
};
//////////////////////////////////maxVal()函数结束
#37
geninsf0092008-12-04 22:10
//////////////////////////////////////////////////
//maxVal()私有成员函数
//递归找出子树subTree中结点的最大值
//////////////////////////////////////////////////
template<class T>
T BinaryTree<T>::maxVal(BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        T maxl,maxr;

        //求出左子树的最大值
        maxl=maxVal(subTree->leftChild);
        //求出右子树的最大值
        maxr=maxVal(subTree->rightChild);

        //返回根结点，左子结点,右子结点中最大的那个
        if(subTree->data>maxl && subTree->data>maxr)
            return subTree->data;
        else if(maxl>subTree->data && maxl>maxr)
            return maxl;
        else
            return maxr;
    }
    else
        return 0;
};
//////////////////////////////////maxVal()函数结束
#38
geninsf0092008-12-04 22:11
//////////////////////////////////////////////////
//DoubleOrder()私有成员函数
//双序遍历一棵二叉树,即先访问子树根结点,
//再双序访问左子树,再次访问子树根结点,
//最后在双序访问右子树
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::DoubleOrder(BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        //先访问根结点
        cout<<subTree->data;
        //访问左子树
        DoubleOrder(subTree->leftChild);
        //再访问根结点
        cout<<subTree->data;
        //最后访问右子树
        DoubleOrder(subTree->rightChild);
    };
};
/////////////////////////////DoubleOrder()函数结束
#39
geninsf0092008-12-04 22:11
//////////////////////////////////////////////////
//PrintDepth()保护成员函数
//以前序的方式显示每个结点,并显示它的深度
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::PrintDepth(BinTreeNode<T>* subTree
                ,int depth)
{
    if(subTree!=NULL)
    {
        //访问根结点
        cout<<subTree->data<<":"<<depth<<"  ";
        //递归访问左右子树
        PrintDepth(subTree->leftChild,depth+1);
        PrintDepth(subTree->rightChild,depth+1);
    };
};
//////////////////////////////PrintDepth()函数结束
#40
geninsf0092008-12-04 22:11
//////////////////////////////////////////////////
//SearchpreOrder()私有成员函数
//得到中序序列中第k个结点的指针
//////////////////////////////////////////////////
template<class T>
BinTreeNode<T>* BinaryTree<T>::SearchpreOrder(int k
            ,BinTreeNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        int T=Size(subTree);             //树的总结点数
        int TL=Size(subTree->leftChild); //树的左子树结点数
        int TR=Size(subTree->rightChild);//树的右子树结点数

        if(k==1)                  //如果k=1,那要找的就是子树根结点
             return subTree;
        else if((k-1)<=TL)        //如果在左子树中
            return SearchpreOrder(k-1
            ,subTree->leftChild);
        else if((k-1)>TL && k<=T) //如果在右子树中
            return SearchpreOrder(k-1-TL
            ,subTree->rightChild);
        else                      //如果超过树的总结点数
            return NULL;
    }
    else
        return NULL;
};
/////////////////////////私有SearchOrder()函数结束
#41
geninsf0092008-12-04 22:12
//////////////////////////////////////////////////
//IsCompleteBinTree()公有成员函数
//判断一棵二叉树是否是完全二叉树
//////////////////////////////////////////////////
template<class T>
bool BinaryTree<T>::IsCompleteBinTree()
{
    LinkedQueue<BinTreeNode<T>*> LQ;     //层次遍历用的队列
    LQ.EnQueue(root);                    //根结点入队列
    BinTreeNode<T>* ptr;                 //游标指针
    int flag=0;                          //0表示遍历的前个结点是数据1:表示前个是空
    while(!LQ.IsEmpty())
    {
        LQ.DeQueue(ptr);                 //从队列中取出一个元素
        
        if(ptr!=NULL)
        {
            if(flag==1)                  //如果当前是数据节点但前个是空
                return false;            //说明不是完全二叉树
            LQ.EnQueue(ptr->leftChild);  //如果是空指针也可以压入队列的
            LQ.EnQueue(ptr->rightChild);
        }
        else
            flag=1;
    };
    return true;
};
///////////////////////IsCompleteBinTree()函数结束
#42
geninsf0092008-12-04 22:12
//////////////////////////////////////////////////
//FindWidth()公有成员函数
//求子树subTree的宽度,二叉树的宽度就是结点数最多
//的那层上的结点的个数,i是层次开始的层次数,
//count数组用于记录各层上的结点个数
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::FindWidth(BinTreeNode<T>* subTree
                             ,int* count,int i=0)
{
    if(subTree!=NULL)
    {
        cout<<++p;
        count[i]++;
        FindWidth(subTree->leftChild,count,i+1);
        FindWidth(subTree->rightChild,count,i+1);
    };
};
///////////////////////////////FindWidth()函数结束

/////////////////////////////////////////////////
//FindWidth()
//找出当前的二叉树的宽度
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::FindWidth()
{
    int dep=Height();             //当前二叉树的深度
    int* count=new int[dep];      //按照当前二叉树的深度来开辟数组
    for(int i=0;i<dep;i++)
        count[i]=0;               //把计数数组先初始化为0
    FindWidth(root,count,0);
    int max=0;
    for(i=0;i<dep;i++)            //找出最大宽度
        if(max<count[i])
            max=count[i];
    return max;
};
//////////////////////////////FindWidth()函数结束
#43
geninsf0092008-12-04 22:12
/////////////////////////////////////////////////
//NumOfSons()公有成员函数
//递归:求解当前指定结点的所有的子孙的个数
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::NumOfSons(BinTreeNode<T>* p)
{
    if(p==NULL)                   //如果指针是空的则停止
        exit(1);
    int count=0;                  //计数器
    if(p->leftChild!=NULL)        //如果左子树不空
        count=count+1+NumOfSons(p->leftChild);
    if(p->rightChild!=NULL)
        count=count+1+NumOfSons(p->rightChild);
    return count;                 //返回子孙接点的个数
};
//////////////////////////////NumOfSons()函数结束
#44
geninsf0092008-12-04 22:13
/////////////////////////////////////////////////
//PreOrderCount()公有成员函数
//通过前序遍历来统计当前二叉树中的结点的个数
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::PreOrderCount(
                BinTreeNode<T>* subTree)
{
    static int count=0;               //静态计数器
    if(subTree!=NULL)                 //当前结点统计加1
    {
        count++;
        if(subTree->leftChild!=NULL)  //如果左子树不空
            PreOrderCount(
                subTree->leftChild);  //递归统计左子树的结点个数
        if(subTree->rightChild!=NULL) //如果右子树不空
            PreOrderCount(
                subTree->rightChild); //递归统计右子树的结点个数
        return count;
    }
    else
        return count;
};
//////////////////////////PreOrderCount()函数结束
#45
geninsf0092008-12-04 22:13
/////////////////////////////////////////////////
//PreOrderCreate()公有成员函数
//递归通过前序序列创建一棵二叉树，前序序列中
//空子树用符号'#'来代替,s是前序序列描述字符串
//返回的是创建结束后字符串停留的当前位置
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::PreOrderCreate(
            char* s,int start,BinTreeNode<T>*& subTree)
{
    if(s[start]!='#')          //如果当前读入的不是空子树
    {
        BinTreeNode<T>* newNode//创建新结点
            =new BinTreeNode<T>(s[start]);
        subTree=newNode;       //新建立的根结点
  
        int k=PreOrderCreate(s,//从start+1位置开始递归创建左子树
            start+1,subTree->leftChild);
        PreOrderCreate(s,k+1,  //递归创建右子树
            subTree->rightChild);
    }
    else
    {
        subTree=NULL;          //创建空子树
        return start;          //当前子树最后一个'#'
    };
};
/////////////////////////PreOrderCreate()函数结束

#endif
#46
leilong2008-12-04 23:19
回复 第10楼 geninsf009 的帖子
楼主 辛苦，写这么多 谢谢了
#47
shuimiu19882008-12-09 19:30
楼主真油！！！！谢谢分享
#48
很远的那颗星2008-12-10 19:12
晕..黑压压的一片,这代码可以卖个好价钱了,呵呵...

对你的遍历真的无话说啊,我从来没这么认真的一起写过,只是偶而写一下,刚学时都是递归,但为以后找工作着想,现在改非递归了..
#49
flylee2010-01-05 23:24
awesome
#50
xunmeng10242010-04-04 15:59
楼主真牛！！！你是偶的偶像
1
©2025, BC-CN.NET
电脑版