随笔-13  评论-0  文章-2  trackbacks-0
二查查找树的实现(链式) Alpha1.0
 1/**
 2        Binary Search Tree
 3        Version: 1.0
 4        Member function as follow:
 5        size()
 6        push_back(T)        // inset an elm
 7        erase(T)        // delete an elm
 8        empty()         // if it is an empty list
 9        print()
10        find(T&)          // find an elm
11
12        Use C++ template
13**/
14#include<iostream>
15
16#ifndef BST_H
17#define BST_H
18
19template<typename T>
20struct Node
21{
22    T data;
23    Node<T>* left,*right;
24    Node():left(NULL),right(NULL){}
25    Node(T data):left(NULL),right(NULL){}
26};
27
28template<typename T>
29class BST
30{
31public:
32    BST():root(NULL){}
33    ~BST(){};
34    bool find(const T& x)const;
35    const T & min() const;
36    const T & max() const;
37    void insert(const T& x);
38    //const T & successor(const T&) const;
39    //const T & predecessor(const T&) const;
40    // void delete(const T&);
41private:
42    Node<T> * root;
43};
44
45template<typename T> bool BST<T>::find(const T& x) const
46{
47    Node<T>* p = new Node<T>;
48    p = root;
49    while(p!= NULL && x != p->data)
50    {
51        if(p->data > x) p = p->right;
52        else p = p->left;
53    }
54    return  x == p->data;
55}
56
57template<typename T> const T & BST<T>::min() const
58{
59    Node<T>* p = new Node<T>;
60    p = root;
61    while(p->left != NULL)
62    p = p->left;
63    return p->data;
64}
65
66template<typename T> const T & BST<T>::max() const
67{
68    Node<T>* p = new Node<T>;
69    p = root;
70    while(p->right != NULL)
71    p = p->right;
72    return p->data;
73}
74
75template<typename T> void BST<T>::insert(const T& one)
76{
77
78    Node<T> * p = new Node<T>;
79    Node<T> * temp = new Node<T>;
80    temp = NULL;
81    p = root;
82    while( p != NULL )
83    {
84        temp = p;
85        if(p->data > one) p = p->left;
86        else if( p->data < one)p = p->right;
87        else { std::cout << "has the same treeNode!!" << std::endl; return; }
88    }
89    if(temp == NULL)
90    {
91        root = new Node<T>;
92        root->data = one;
93    }
94    else if (one > p->data) p = p->right;
95    else p = p->left;
96}
97
98#endif

// Test Function
int main()
{
    using namespace std;
    BST<int> tree;
    cout << "---------------Binary Search Tree--------------------" << endl;
    cout << "1.Create the Binary Search Tree"<< endl;
    cout << "please input the number of nodes you want to add" << endl;
    int num, temp;
    cin >> num;
    cout << "then input the number " << endl ;
    while(num--)
    {
        cin >> temp;
        tree.insert(temp);
    }
    cout << "Ok, the tree is builded" << endl;
    cout << "2.Find an element you want to search" << endl;
    cout << "which number you want to find?" << endl;
    cin >> temp;
    if(tree.find(temp))
    cout << "Yeah,it's in the tree" << endl;
    else
    cout << "Sorry, it's not in the tree" << endl;
    cout << "3.Show the max and min element" << endl;
    cin.get();
    cout << "Max:" << tree.max() <<" Min:" << tree.min() << endl;
    system("pause");

    return 0;
}

// PS: It's my worst version code about binary search tree. delete function is not implement, i will fix it in the next version.
posted on 2009-03-24 00:13 亦夏 阅读(229) 评论(0)  编辑 收藏 引用 所属分类: DataStruct

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


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 亦夏