冬日飘雪

二叉树


#include<iostream>

using namespace std;

struct _node 
{
    int data;
    _node* left;
    _node* right;
}node;

typedef _node T;

class BinaryTree
{
public:
    BinaryTree(){root = NULL;m_nSize=0;}
    ~BinaryTree(){}

    bool IsEmpty(){return root==NULL;}
    int Size(){return m_nSize;}
    //清空
    bool Clear(T* root)
    {
        if (root==NULL) return true;            //根节点为空
        else
        {
            if (root->left)
            {
                Clear(root->left);
            }
            if (root->right)
            {
                Clear(root->right);
            }
            Delete(root->data);
        }
        return true;
    }
    //插入
    bool Insert(int data)
    {
        if (root == NULL)
        {
            root = new T();
            root->data = data;
            root->left = NULL;
            root->right = NULL;
            m_nSize++;
            return true;
        }
        else                                //root != NULL
        {
            T* parent = NULL;
            T* temp = root;
            while (true)
            {
                if (temp->data < data)
                {
                    while (temp && temp->data < data)
                    {
                        parent = temp;
                        temp = temp->right;
                    }
                    if (!temp)
                    {
                        temp = new T();
                        temp->data = data;
                        temp->left = NULL;
                        temp->right = NULL;
                        parent->right = temp;
                        m_nSize++;
                        return true;
                    }    
                }
                else                    //temp->data > data
                {
                    while (temp && temp->data > data)
                    {
                        parent = temp;
                        temp = temp->left;
                    }
                    if (!temp)
                    {
                        temp = new T();
                        temp->data = data;
                        temp->left = NULL;
                        temp->right = NULL;
                        parent->left = temp;
                        m_nSize++;
                        return true;
                    }
                }
            }
            
        }
    }

    //int DeleteC(T* item, int data)
    //{
    //    if (item == NULL)
    //    {
    //        return NULL;
    //    }
    //    else
    //    {
    //        int side = 0;
    //        if (item->data < data)
    //        {
    //            side = 1;                                        //1 -> right
    //            DeleteC(item->right);
    //        }
    //        else if (item->data > data)
    //        {
    //            DeleteC(item->left);
    //        }
    //        else                //item->data == data
    //        {
    //            if (Size() == 1)
    //            {
    //                delete root;
    //                root = NULL;
    //                m_nSize--;
    //                return data;
    //            }

    //        }
    //    }
    //}

    //删除
    int Delete(int data)
    {
        if (root == NULL)
        {
            return NULL;        //NULL
        }
        else                    //root != NULL
        {
            T* parent = root;
            T* temp = root;
            int side = 0;
            while (true)
            {
                while(temp && temp->data < data)                //1 -> right
                {
                    parent = temp;
                    temp = temp->right;
                    side = 1;
                }
                while (temp && temp->data > data)
                {
                    parent = temp;
                    temp = temp->left;
                    side = 2;
                }
                if (!temp)
                {
                    return NULL;
                }
                if (temp->data == data)
                {
                    if (Size()==1)
                    {
                        delete root;
                        root = NULL;
                        m_nSize--;
                        return data;
                    }
                    if (!temp->left && !temp->right)            //left == NULL && right == NULL
                    {
                        if (side == 1)
                            parent->right = NULL;
                        else
                            parent->left = NULL;
                        delete temp;
                        temp = NULL;
                        m_nSize--;
                        return data;
                    }
                    else if (!temp->left)                        //left == NULL && right != NULL
                    {
                        if (side == 1)
                        {
                            parent->right = temp->right;
                            delete temp;
                            temp = NULL;
                            m_nSize--;
                            return data;
                        }
                        else
                        {
                            parent->left = temp->right;
                            delete temp;
                            temp = NULL;
                            m_nSize--;
                            return data;
                        }
                    }
                    else if (!temp->right)                    //left!=NULL && right == NULL
                    {
                        if (side == 1)
                        {
                            parent->right = temp->left;
                            delete temp;
                            temp = NULL;
                            m_nSize--;
                            return data;
                        }
                        else
                        {
                            parent->left = temp->left;
                            delete temp;
                            temp = NULL;
                            m_nSize--;
                            return data;
                        }
                    }
                    else if (temp->left && temp->right)    //left!=NULL && right != NULL
                    {
                        T* p = NULL;
                        T* q = NULL;
                        if (side == 1)
                        {
                            p = temp->left->right;
                            temp->left->right = temp->right;
                            parent->right = temp->left;
                            q = temp->right;
                            while (q->left)
                            {
                                q = q->left;
                            }
                            //q->left == NULL
                            q->left = p;
                            delete temp;
                            temp = NULL;
                            m_nSize--;
                            return data;
                        }
                        else                        //side == 2
                        {
                            p = temp->left->right;
                            temp->left->right = temp->right;
                            parent->left = temp->left;
                            q = temp->right;
                            while (q->left)
                            {
                                q = q->left;
                            }
                            q->left = p;
                            delete temp;
                            temp = NULL;
                            m_nSize--;
                            return data;
                        }
                    }
                }
            }

        }
    }

    T* GetRoot()
    {
        return root;
    }

    bool Show(T* root)
    {
        if (root == NULL)
        {
            return true;
        }
        if (root->left)
        {
            Show(root->left);
        }
        cout<<root->data<<" ";
        if (root->right)
        {
            Show(root->right);
        }
        return true;
    }

private:
    T* root;                    //根节点
    int m_nSize;                //节点数
};

posted on 2010-08-05 13:09 Bomb 阅读(253) 评论(0)  编辑 收藏 引用 所属分类: C++


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


My Links

Blog Stats

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜