一个二分查找树的实现
程序员文章站
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);}