【数据结构】二叉查找树

#include <iostream>
#include <queue>
#include <stack>
using namespace std;
#define MAX 10
struct BinTreeNode
{
    int m_data;
    BinTreeNode *lchild,*rchild;
    BinTreeNode(int item,BinTreeNode *left=NULL,BinTreeNode *right=NULL)
        :m_data(item),lchild(left),rchild(right) {}
};
class BinaryTree
{
    private:
        BinTreeNode *root;
    public:
        BinaryTree()
        {
            root=NULL;
        }
        BinTreeNode *GetRoot()
        {
            return root;
        }
        void Insert(const int node)
        {
            BinTreeNode *currentpointer;
            BinTreeNode *parentpointer;
            BinTreeNode *newpointer;
            BinTreeNode *ptr = root;
            newpointer = new BinTreeNode(node);
            if(root==NULL)
            {
                root=newpointer;
            }
            else
            {
                currentpointer=ptr;
                while(currentpointer!=NULL)
                {
                    parentpointer=currentpointer;
                    if(currentpointer->m_data>node)
                    {
                        currentpointer=currentpointer->lchild;
                    }
                    else
                    {
                        currentpointer=currentpointer->rchild;
                    }
                }
                if(parentpointer->m_data>node)
                {
                    parentpointer->lchild=newpointer;
                }
                else
                {
                    parentpointer->rchild=newpointer;
                }
            }
        }
        BinTreeNode *Creat(int data[],int len)
        {
            for(int i=0; i<len; i++)
            {
                Insert(data[i]);
            }
            return root;
        }
        void PreOrder(BinTreeNode *p)
        {
            if(p!=NULL)
            {
                cout<<p->m_data<<',';
                PreOrder(p->lchild);
                PreOrder(p->rchild);
            }
        }
        void PreOrder2(BinTreeNode *p)//非递归版
        {
            stack<BinTreeNode*>S;
            S.push(p);
            while(!S.empty())
            {
                p=S.top();
                while(p)
                {
                    cout<<p->m_data<<',';
                    S.push(p->lchild);
                    p=p->lchild;
                }
                S.pop();
                if(!S.empty())
                {
                    p=S.top();
                    S.pop();
                    S.push(p->rchild);
                }
            }
            
        }
        void InOrder(BinTreeNode *p)
        {
            if(p!=NULL)
            {
                InOrder(p->lchild);
                cout<<p->m_data<<',';
                InOrder(p->rchild);
            }
        }
        void InOrder2(BinTreeNode *p)//非递归版
        {
            stack<BinTreeNode*>S;
            S.push(p);
            while(!S.empty())
            {
                p=S.top();
                while(p)
                {
                    S.push(p->lchild);
                    p=p->lchild;
                }
                S.pop();
                if(!S.empty())
                {
                    p=S.top();
                    S.pop();
                    cout<<p->m_data<<',';
                    S.push(p->rchild);
                }
            }
            
        }
        void PostOrder(BinTreeNode *p)
        {
            if(p!=NULL)
            {
                PostOrder(p->lchild);
                PostOrder(p->rchild);
                cout<<p->m_data<<',';
            }
        }
        void layerOrder(BinTreeNode *p)
        {
            if(p!=NULL)
            {
                queue<BinTreeNode *>st;
                st.push(p);
                while(!st.empty())
                {
                    BinTreeNode*now=st.front();
                        st.pop();
                    cout<<now->m_data<<',';
                    if(now->lchild!=NULL)
                    {
                        st.push(now->lchild);
                    }
                    if(now->rchild!=NULL)
                    {
                        st.push(now->rchild);       
                    }   
                }
            }
        }
        BinTreeNode *Find(const int &c)
        {
            BinTreeNode *pCurrent =root;
            if(pCurrent!=NULL)
            {
                while(pCurrent!=NULL)
                {
                    if(pCurrent->m_data==c)
                    {
                        return pCurrent;
                    }
                    else
                    {
                        if(c > pCurrent->m_data)
                            pCurrent=pCurrent->rchild;
                        else
                            pCurrent=pCurrent->lchild;
                    }
                }
            }
            return NULL;
        }
        bool DeleteBT(const int &key)
        {
            BinTreeNode *q,*s;
            BinTreeNode *current=root;
            BinTreeNode *prt=NULL;
            while((NULL!=current)&&(current->m_data!=key))
            {
                prt=current;
                if(current->m_data>key)
                    current=current->lchild;
                else
                    current=current->rchild;
            }
            if(current==NULL)
            {
                cout<<"没有此节点"<<endl;
                return false;
            }
            //删除叶子节点
            if(current->lchild==NULL&¤t->rchild==NULL)
            {
                if(current==root)
                {
                    root=NULL;
                }
                else
                {
                    if(current==prt->lchild)
                    {
                        prt->lchild=NULL;
                    }
                    else
                    {
                        prt->rchild=NULL;
                    }
                }
            }
            //右边有人
            if(current->lchild==NULL&¤t->rchild!=NULL)
            {
                if(current==root)
                {
                    current=current->rchild;
                }
                else
                {
                    if(current==prt->lchild)
                    {
                        prt->lchild=current->rchild;
                    }
                    else
                    {
                        prt->rchild=current->rchild;
                    }
                }
            }
            //左边有人
            if(current->rchild==NULL&¤t->lchild!=NULL)
            {
                if(current==root)
                {
                    current=current->lchild;
                }
                else
                {
                    if(current==prt->lchild)
                    {
                        prt->lchild=current->lchild;
                    }
                    else
                    {
                        prt->rchild=current->lchild;
                    }
                }
            }
            //两边都有人
            if(current->lchild!=NULL&¤t->rchild!=NULL)
            {
                q=current;
                s=current;
                current=current->lchild;
                while(current->rchild)
                {
                    s=current;
                    current=current->rchild;
                }
                q->m_data=current->m_data;
                if(q!=s)
                    s->rchild=current->lchild;
                else
                    q->lchild=current->lchild;
            }
            delete current;
            current=NULL;
            return true;
        }
        void destroy(BinTreeNode *current)
        {
            if(current!=NULL)
            {
                destroy(current->lchild);
                destroy(current->rchild);
                delete current;
                current = NULL;
            }
        }
        ~BinaryTree()
        {
            destroy(root);
        }
        int CountLeafs(BinTreeNode *current)//叶子节点
        {
            if(current==NULL)
            {
                return 0;
            }
            else
            {
                if(current->rchild==NULL&¤t->rchild==NULL)
                {
                    return 1;
                }
                else
                {
                    int num1=CountLeafs(current->lchild);
                    int num2=CountLeafs(current->rchild);
                    return num1+num2;
                }
            }
        }

        int Depth(BinTreeNode *current)//深度
        {
            int Depthleft;
            int Depthright;
            int dp=0;
            if(current==NULL)
            {
                return 0;
            }
            else
            {
                Depthleft=Depth(current->lchild);
                Depthright=Depth(current->rchild);
                dp=1+(Depthright>=Depthleft ? Depthright:Depthleft);
            }
            return dp;
        }
        BinTreeNode *Copy(BinTreeNode *tree)
        {
            BinTreeNode *pleft;
            BinTreeNode *pright;
            if(!tree)
            {
                return NULL;
            }
            if(tree->lchild!=NULL)
            {
                pleft=Copy(tree->lchild);
            }
            else
            {
                pleft=NULL;
            }
            if(tree->rchild!=NULL)
            {
                pright=Copy(tree->rchild);
            }
            else
            {
                pright=NULL;
            }
            BinTreeNode *cptree=new BinTreeNode(tree->m_data,pleft,pright);
            root=cptree;
            return cptree;
        }
};
int main()
{
    BinaryTree myTree;
    int a[]= {6,3,4,7,8,2,5,9,1};
    /*
         6
        / 
       3   7
      /    
     2   4   8
    /        
   0       5   9
    
     1
    */
    myTree.Creat(a,MAX);  //创建二叉搜索树
    cout<<"先序遍历";myTree.PreOrder(myTree.GetRoot());cout<<endl;
    cout<<"中序遍历";myTree.InOrder(myTree.GetRoot());cout<<endl;
    cout<<"后序遍历";myTree.PostOrder(myTree.GetRoot());cout<<endl;
    cout<<"层序遍历";myTree.layerOrder(myTree.GetRoot());cout<<endl;

    cout<<"非递归先序遍历";myTree.PreOrder2(myTree.GetRoot());cout<<endl;
    cout<<"非递归中序遍历";myTree.InOrder2(myTree.GetRoot());cout<<endl;

    cout<<"树深度";cout<<myTree.Depth(myTree.GetRoot())<<endl;
    cout<<"叶子节点数";cout<<myTree.CountLeafs(myTree.GetRoot())<<endl;
    BinaryTree copyTree;//新建复制树
    copyTree.Copy(myTree.GetRoot());
    cout<<"复制树先序遍历";copyTree.PreOrder(copyTree.GetRoot());
    cout<<"复制树深度"<<copyTree.Depth(copyTree.GetRoot())<<endl;
}