Localhost8080

知行合一，自强不息

 

二分查找树-BST

 

#include <iostream>
using namespace std;

class Node
{
public:
        Node()
        {
                value =-1;
                pLC = NULL;
                pRC = NULL;
        }
        ~Node(){}
        int value;
        Node *pLC;
        Node *pRC;
};
class BST
{
public:
        BST()
        {
                m_pRoot = NULL;
        }
        ~BST()
        {
                KillBST();
        }
        Node *InsertBST(int value)
        {
                return m_pRoot = Insert(m_pRoot, value);
        }
        Node *SearchBST(int value)
        {
                return Search(m_pRoot, value);
        }
        Node *DelBST(int value)
        {
                return Delete(m_pRoot,value);
        }
        void KillBST()
        {
                Kill(m_pRoot);
        }
        void ShowTree()
        {
                Show(m_pRoot);
        }
        void PreOrder_ShowBST()
        {
                PreOrder_Show(m_pRoot);
        }
        void PostOrder_ShowBST()
        {
                PostOrder_Show(m_pRoot);
        }
private:
        Node *Search(Node *pNode, int value)
        {
                if (pNode == NULL) return NULL;

                if (value == pNode->value)
                {
                        return pNode;
                }
                else if (value < pNode->value)
                {
                        return Search(pNode->pLC, value);
                }
                else 
                {
                        return Search(pNode->pRC, value);
                }
        }
        Node *Insert(Node* pRoot, int value)
        {
                if (pRoot == NULL)
                {
                        Node * pInsert = new Node();
                        pInsert->value = value;
                        pInsert->pLC = NULL;
                        pInsert->pRC = NULL;
                        return pInsert;
                }

                if (value <pRoot->value)
                {
                        pRoot->pLC = Insert(pRoot->pLC, value);
                }
                else
                {
                        pRoot->pRC = Insert(pRoot->pRC,value);
                }
                return pRoot;
        }
        Node *Delete(Node *pRoot, int value)
        {
                Node *p, *q;

                if (pRoot->value == value)
                {
                        if (pRoot->pLC ==NULL &&pRoot->pRC ==NULL)
                        {
                                delete pRoot;
                                return NULL;
                        }
                        else if (pRoot->pLC == NULL)
                        {
                                p = pRoot->pRC;
                                delete pRoot;
                                return p; 
                        }
                        else if (pRoot->pRC == NULL)
                        {
                                p = pRoot->pLC;
                                delete pRoot;
                                return p;
                        }
                        else
                        {
                                p = q = pRoot->pRC;
                                while (p->pLC != NULL)
                                {
                                        p = p->pLC;
                                }
                                p->pLC = pRoot->pLC;
                                delete pRoot;
                                return q;
                        }
                }

                if(pRoot->value >value &&pRoot->pLC !=NULL)
                {
                        pRoot->pLC = Delete(pRoot->pLC, value);
                }
                if(pRoot->value <value &&pRoot->pRC !=NULL)
                {
                        pRoot->pRC = Delete(pRoot->pRC, value);
                }
                return pRoot;
        }
        void Kill(Node *pRoot)
        {
                if (pRoot!=NULL)
                {
                        Kill(pRoot->pLC);
                        Kill(pRoot->pRC);
                        delete pRoot;
                }
        }
        void Show(Node *pRoot)
        {
                if (pRoot != NULL)
                {
                        Show(pRoot->pLC);
                        cout << pRoot->value << " ";
                        Show(pRoot->pRC);
                }
        }
        void PreOrder_Show(Node *pRoot)
        {
                if (pRoot != NULL)
                {
                        cout << pRoot->value << " ";
                        Show(pRoot->pLC);
                        Show(pRoot->pRC);
                }
        }
        void PostOrder_Show(Node *pRoot)
        {
                if (pRoot != NULL)
                {
                        Show(pRoot->pLC);
                        Show(pRoot->pRC);
                        cout << pRoot->value << " ";
                }
        }
public:
        Node *m_pRoot;
};

int main()
{
        BST *pBST = new BST();
        for(int i=9;i>0;i--)
        {
                pBST->InsertBST(i);
        }
        pBST->ShowTree();
        cout<<endl;
        Node *pNode = pBST->SearchBST(3);
        pBST->DelBST(2);
        pBST->ShowTree();
        cout<<endl;
        delete pBST;
        return 0;

}

posted on 2010-04-23 00:14 superKiki 阅读(643) 评论(0)  编辑 收藏 引用


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


导航

统计

常用链接

留言簿

随笔档案

文章分类

我的好友

一些常去的网站

搜索

最新评论

阅读排行榜

评论排行榜