liyuxia713

蹒跚前行者

常用链接

统计

Algorithms

C++

最新评论

二叉排序树

 1//BTreeNode.h 二叉树结点抽象类型
 2
 3#ifndef BTREENODE_H
 4#define BTREENODE_H
 5
 6#include <cstdlib>
 7//template<class T> class BTree;
 8template<class T> class SortBTree;
 9
10template<class T> class BTreeNode
11{
12    //friend class BTree<T>;
13    friend class SortBTree<T>;
14public:
15    BTreeNode():lchild(NULL),rchild(NULL){    };
16    BTreeNode(const T&dt, BTreeNode<T> *lch =NULL , BTreeNode<T> *rch = NULL)
17        :data(dt),lchild(lch),rchild(rch){};
18
19    T get_data()const {return data;    };    
20    BTreeNode<T>* get_lchild()const {return lchild;    };
21    BTreeNode<T>* get_rchild()const {return rchild;    };
22    void set_data(const T& d) { data = d;};    
23protected:
24private:
25    T data;
26    BTreeNode<T> *lchild, *rchild;
27};
28
29#endif
  1/************************************************************************
  2* SortBTree.h
  3* 根据给定的字符串构造一个排序二叉树
  4* 从排序二叉树中寻找最大值，最小值，不存在时抛出invalid_argument异常
  5* 从排序二叉树中删除某一元素，不存在时抛出invalid_argument 异常
  6* 往排序二叉树中添加一个新元素                                                                     
  7************************************************************************/
  8
  9#ifndef SORTBTREE_H
 10#define SORTBTREE_H
 11
 12#include "BTreeNode.h"
 13#include <cstdlib>
 14#include <stdexcept>
 15
 16template<class T>
 17class SortBTree
 18{
 19public:
 20    SortBTree(T* p , int n);
 21    
 22    const T& max()const; // return the maximum
 23    const T& min()const; // return the minimum
 24    
 25    BTreeNode<T>* find_data(const T& data)const; //return the node of data, if data is not exist, throw error
 26    void delete_data(const T& data) { delete_data(root,data); }; //delete the node of data, if data is not exist, throw error
 27    void insert_data(const T& data) { insert_data(root,data); };
 28
 29    BTreeNode<T>* get_root()const {return root; }; // return the root of tree
 30    void display()const    { display(root,visit); cout << endl;};    // print the data of tree
 31    
 32protected:
 33    static void insert_data(BTreeNode<T> * &root, const T& ndata); //这里必须是对指针的引用,切记，切记    
 34    static BTreeNode<T>* find_data(BTreeNode<T>* r,const T& data);
 35    static void delete_node(BTreeNode<T> * &p);
 36    static void delete_data(BTreeNode<T>* &r, const T& data);
 37    static void display(BTreeNode<T>*p, void visit(BTreeNode<T>* p));    
 38private:
 39    BTreeNode<T> *root;    
 40};
 41
 42//construction function
 43template<class T>
 44SortBTree<T>::SortBTree(T* p, int n)
 45{
 46    root = new BTreeNode<T>;
 47    root = NULL; //注意这行很必要，BTreeNode没有默认设置为NULL的构造函数
 48    for(int i = 0; i != n; ++i)
 49    {        
 50        insert_data(root,p[i]);
 51    }
 52}
 53
 54// insert a new data 
 55template<class T>
 56void SortBTree<T>::insert_data(BTreeNode<T> *&rt,const T& ndata)
 57{
 58    if(rt == NULL) 
 59    {
 60        rt = new BTreeNode<T>(ndata,NULL,NULL);
 61        //rt->data = ndata; //这三条语句不等于上面那条
 62        //rt->lchild = NULL; //用这三条语句是错的
 63        //rt->rchild = NULL;
 64    }
 65    else if(rt->data == ndata) return;
 66    else if(rt->data > ndata) insert_data(rt->lchild, ndata);
 67    else insert_data(rt->rchild, ndata);
 68}
 69
 70// delete a node from tree(improved)
 71// 如果p没有左子树，则让p的右子树的根代替p即可。
 72// 如果p有左子树，找出左子树中结点值最大的节点temp(最右下角的结点，也是中序遍历最后一个结点，他没有右子树)
 73// 用temp的结点值替换下p的结点值
 74// 删除temp(因为temp的右子树为空，从而直接用其左子树根代替本身就可达到删除结点的目的)
 75// 注： 一般的方法用temp替换p，但是这样可能导致树很不平衡。
 76template<class T>
 77void SortBTree<T>::delete_node(BTreeNode<T> * &p)
 78{
 79    if(p == NULL) cout << "There is not this node." <<endl;
 80    else if(p->lchild == NULL) p = p->rchild;
 81    else
 82    {
 83        BTreeNode<T>* temp = p;
 84        //记录左子树中序遍历的最后一个结点（值最大的点）
 85        while(temp->rchild != NULL)
 86            temp = temp->rchild;    
 87        //删除这个结点，等价于用这个结点的做子树代替这个结点（因为这个结点没有右子树）
 88        BTreeNode<T>* parent;
 89        parent = temp;
 90        while(parent->rchild != NULL)
 91        {
 92            parent = temp;
 93            temp = temp->rchild;
 94        }
 95        parent = temp->lchild;
 96        p->set_data(temp->data);        
 97    }
 98}
 99
100//delete a data
101template<class T>
102void SortBTree<T>::delete_data(BTreeNode<T>* &root, const T& data)
103{
104    if(root == NULL)
105        throw std::invalid_argument("This data is not exsit.");
106    else if(root->data == data) delete_node(root);
107    else if(root->data > data) delete_data(root->lchild,data);
108    else delete_data(root->rchild,data);
109}
110
111// find a specific data
112template<class T>
113BTreeNode<T>*  SortBTree<T>::find_data(BTreeNode<T>* r,const T& data)
114{
115    if(r == NULL) return r;
116    else if(r->data == data) return r; //注意这两行是不能合并在一起的，不然可能会出现NULL->data呢
117    else if(r->data > data) return find_data(r->lchild,data);
118    else return find_data(r->rchild,data);
119}
120// find a specific data in tree
121template<class T>
122BTreeNode<T>* SortBTree<T>::find_data(const T& data)const
123{
124    if(find_data(root,data) == NULL)
125        throw std::invalid_argument("This data is not exist.");
126    else 
127        return find_data(root,data);
128}
129
130// return the maximum value 
131template<class T>
132const T& SortBTree<T>::max()const
133{
134    if(root == NULL)
135        throw std::invalid_argument("This is an empty Tree.");
136    else
137    {
138        BTreeNode<T> *q = root;
139        while(q->rchild != NULL)
140            q = q->rchild;
141        return q->data;
142    }
143}
144
145//return the minimum value
146template<class T>
147const T& SortBTree<T>::min()const
148{
149    if(root == NULL)
150        throw std::invalid_argument("This is an empty Tree.");
151    else
152    {
153        BTreeNode<T> *q = root;
154        while(q->lchild != NULL)
155            q = q->lchild;
156        return q->data;
157    }
158}
159
160//print the sort tree
161template <class T>
162void SortBTree<T>::display(BTreeNode<T>*p, void visit(BTreeNode<T>* p))
163{
164    if(p != NULL)
165    {
166        display(p->lchild,visit);
167        visit(p);
168        display(p->rchild,visit);
169    }    
170}
171#endif

 1//SortBTree_Test.cpp
 2
 3#include "SortBTree.h"
 4#include <iostream>
 5#include "string"
 6
 7using std::cout;
 8using std::endl;
 9using std::invalid_argument;
10//谓词函数predicate
11void visit(BTreeNode<char> *p) { std::cout << p->get_data() << " ";};
12
13int main()
14{
15    char *str = "19382";
16    SortBTree<char> sbtr(str,5);
17    SortBTree<char> empty_tree(str,0);
18    cout << "The original sort binary tree is: ";
19    sbtr.display();
20    try
21    {
22        sbtr.find_data('5');
23    }
24    catch (invalid_argument& err)
25    {
26        cout << err.what() <<endl;
27    }
28
29    try
30    {
31        cout << "max = " << sbtr.max() <<endl;
32        cout << "min = " << sbtr.min() <<endl;
33        cout << "max of empty tree = " << empty_tree.max() <<endl;
34    }
35    catch(invalid_argument& err)
36    {
37        cout << err.what() <<endl;
38    }
39
40    try
41    {        
42        sbtr.insert_data('6');
43        sbtr.delete_data('8');
44        sbtr.display();
45        sbtr.delete_data('5');
46        sbtr.display();        
47    }
48    catch (invalid_argument& err)
49    {
50        cout << err.what() <<endl;
51    }
52    
53    return 0;
54}

posted on 2009-04-27 20:57 幸运草 阅读(1708) 评论(0)  编辑 收藏 引用 所属分类: Data Structure


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