欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一个二分查找树的实现

程序员文章站 2022-07-12 09:35:00
...
源自c++数据结构与算法一书
#include <iostream>
using namespace std;

template<class Comparable>
class BinarySearchTree
{
        public:
                BinarySearchTree(){ root = NULL; }
                BinarySearchTree(const BinarySearchTree &rhs);
                ~BinarySearchTree() { makeEmpty(); }
                const Comparable& findMin() const;
                const Comparable& findMax() const;
                bool contains(const Comparable &x) const;
                bool isEmpty() const;
                void printTree(ostream &out) const;
                void makeEmpty();
                void insert(const Comparable &x);
                void remove(const Comparable &x);
                const BinarySearchTree & operator=(BinarySearchTree &rhs);

        private:
                struct BinaryNode
                {
                        Comparable element;
                        BinaryNode *left;
                        BinaryNode *right;
                        BinaryNode(const Comparable &elt, BinaryNode *lt, BinaryNode *rt) : element(elt),left(lt),right(rt) {}
                } *root;

                void _insert(const Comparable &x, BinaryNode * &t);
                void _remove(const Comparable &x, BinaryNode * &t);
                bool _contains(const Comparable &x, BinaryNode *t) const;
                void _makeEmpty(BinaryNode * &t);
                void _printTree(BinaryNode *t, ostream &out) const;
                BinaryNode* _findMin(BinaryNode *t);
                BinaryNode& _findMax(BinaryNode *t);

};

template<class Comparable>
void BinarySearchTree<Comparable>::insert(const Comparable &x)
{
        _insert(x,root);
}

/**
 * Interal method to insert into a subtree.
 * @x is the item to insert.
 * @t is the node that roots the subtree
 * set the new root of the subtree(using reference specialty).
 * */
template<class Comparable>
void BinarySearchTree<Comparable>::_insert(const Comparable &x, BinaryNode * &t)
{
        if(t == NULL)
                t = new BinaryNode(x,NULL,NULL);
        else if(x < t->element)
                _insert(x, t->left);
        else if(x > t->element)
                _insert(x, t->right);
        else
                ;//duplicate, do nothing;
}

/**
 * Returns true if x is found in the tree.
 */
template<class Comparable>
bool BinarySearchTree<Comparable>::contains(const Comparable &x) const
{
        return _contains(x,root);
}

template<class Comparable>
bool BinarySearchTree<Comparable>::_contains(const Comparable &x, BinaryNode *t) const
{
        if(t == NULL)
                return false;

        if(t->element == x)
         return true;//matched
      else if(x < t->element)
          _contains(x, t->left);
      else
          _contains(x,t->right);  
}
template<class Comparable>bool BinarySearchTree<Comparable>::isEmpty() const{ if(root == NULL) return true; else return false;}/* destroy the binary tree */template<class Comparable>void BinarySearchTree<Comparable>::makeEmpty(){ _makeEmpty(root);}/** * 后序遍历: 先销毁左子树,再销毁右子树,最后销毁父节点 */template<class Comparable>void BinarySearchTree<Comparable>::_makeEmpty(BinaryNode * &t){ if(t != NULL) { _makeEmpty(t->left); cout << t->element << "...\n"; _makeEmpty(t->right); cout << t->element << "---\n"; delete t; } t = NULL;}/* print the binary tree */template<class Comparable>void BinarySearchTree<Comparable>::printTree(ostream &out = cout) const{ if(isEmpty()) out << "Empty tree" << endl; else _printTree(root, out);}/** * Print the tree in sorted order * 中序遍历: 能够按照排列顺序输出 */template<class Comparable>void BinarySearchTree<Comparable>::_printTree(BinaryNode *t, ostream &out) const{ if(t != NULL) { _printTree(t->left, out); out << t->element << endl; _printTree(t->right, out); }}int main(){ int array[] = {9,2,5,7,4,3,8}; BinarySearchTree<int> btree; for(int i=0;i<sizeof(array)/sizeof(int); i++) btree.insert(array[i]); if(btree.contains(8)) cout << "found" << endl; else cout << "not found" << endl; btree.printTree(cout);}