冬日飘雪

二叉树


#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 阅读(196) 评论(0)  编辑 收藏 引用 所属分类: C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜