题目是：有一系列的数，把他们插入到树里面，并且查找一个数，看它是否在这个树里面
參考答案:#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
#include <vector>
using std::vector;
using std::ostream;
using std::cout;
#define NDEBUG
#ifndef NDEBUG
#define TRACE(os, m) os << m
#else
#define TRACE(os, m)
#endif
template <typename T>
class BinaryTree {
public:
BinaryTree();
BinaryTree(const BinaryTree &tree);
public:
enum PrintType {INORDER, PREORDER, POSTORDER};
typedef typename vector<T>::size_type size_type;
public:
void insert(const T &elem);
T *find(const T &elem) const;
void clear();
void print(ostream &os, PrintType pt) const;
size_type size() const;
BinaryTree &operator=(BinaryTree &tree);
private:
class _Node {
public:
_Node();
_Node(const T &elem);
T _elem;
int _count;
bool _used;
};
private:
void _print_inorder(size_type index, ostream &os) const;
void _print_preorder(size_type index, ostream &os) const;
void _print_postorder(size_type index, ostream &os) const;
private:
size_type _size;
/* left: 2n+1, right: 2n+2, parent, (n-1)/2 */
vector<_Node> _array;
};
template<typename T>
inline
BinaryTree<T>::_Node::_Node()
: _count(0), _used(false) {
TRACE(cout, "BinaryTree::_Node::_Node()\n");
}
template<typename T>
inline
BinaryTree<T>::BinaryTree(): _size(0) {
TRACE(cout, "BinaryTree::BinaryTree()\n");
}
template<typename T>
inline
BinaryTree<T>::BinaryTree(const BinaryTree &tree)
: _array(tree._array), _size(tree._size) {}
template<typename T>
inline void
BinaryTree<T>::insert(const T &elem) {
TRACE(cout, "BinaryTree::insert(const T &)\n");
size_type index = 0;
const size_type size = _array.size();
while ((size>index) && (_array[index]._used)) {
if (elem < _array[index]._elem)
index = 2*index + 1;
else if (elem > _array[index]._elem)
index = 2*index + 2;
else {
++_array[index]._count;
return;
}
}
if (size <= index)
_array.resize(index+1);
_array[index]._elem = elem;
_array[index]._count = 1;
_array[index]._used = true;
++_size;
}
template<typename T>
inline void
BinaryTree<T>::_print_preorder(size_type index, ostream &os) const {
TRACE(cout, "BinaryTree::_print_preorder()\n");
const size_type cap = _array.size();
os << _array[index]._elem << " ";
if (2*index+1<cap && _array[2*index+1]._used)
_print_inorder(2*index+1, os);
if (2*index+2<cap && _array[2*index+2]._used)
_print_inorder(2*index+2, os);
}
template<typename T>
inline void
BinaryTree<T>::_print_inorder(size_type index, ostream &os) const {
TRACE(cout, "BinaryTree::_print_inorder()\n");
const size_type cap = _array.size();
if (2*index+1<cap && _array[2*index+1]._used)
_print_inorder(2*index+1, os);
if (2*index+2<cap && _array[2*index+2]._used)
_print_inorder(2*index+2, os);
os << _array[index]._elem << " ";
}
template<typename T>
inline void
BinaryTree<T>::_print_postorder(size_type index, ostream &os) const {
TRACE(cout, "BinaryTree::_print_postorder()\n");
const size_type cap = _array.size();
if (2*index+1<cap && _array[2*index+1]._used)
_print_inorder(2*index+1, os);
os << _array[index]._elem << " ";
if (2*index+2<cap && _array[2*index+2]._used)
_print_inorder(2*index+2, os);
}
template<typename T>
inline T *
BinaryTree<T>::find(const T &elem) const {
TRACE(cout, "BinaryTree::find(const T)\n");
size_type index = 0;
const size_type cap = _array.size();
while ((cap>index) && (_array[index]._used)) {
if (elem < _array[index]._elem)
index = 2*index + 1;
else if (elem > _array[index]._elem)
index = 2*index + 2;
else
return &_array[index];
}
return NULL;
}
template<typename T>
inline void
BinaryTree<T>::print(ostream &os, BinaryTree::PrintType pt) const {
TRACE(cout, "BinaryTree::print(BinaryTree::PrintType)\n");
void (BinaryTree<T>::*print_ptr[])(size_type, ostream &) const = {
&BinaryTree<T>::_print_inorder,
&BinaryTree<T>::_print_preorder,
&BinaryTree<T>::_print_postorder};
(this->*print_ptr[pt])(0, os);
}
template<typename T>
inline typename BinaryTree<T>::size_type
BinaryTree<T>::size() const {
TRACE(cout, "BinaryTree::size()\n");
return _size;
}
template<typename T>
inline void
BinaryTree<T>::clear() {
TRACE(cout, "BinaryTree::clear()\n");
_array.clear();
_size = 0;
}
template<typename T>
inline BinaryTree<T> &
BinaryTree<T>::operator=(BinaryTree &tree) {
_array = tree._array;
_size = tree._size;
return *this;
}
#endif
这是我以前写的一段C++的二叉树实现（缺少删除结点），没经过完整调试，但基本可以用了
BinaryTree<int> bt;
srand(time(NULL)); // 注意time不属于C 标准
for (int i=0; i<100; ++i)
bt.insert(rand()%100);
cout << (bt.find(50)?"Found 50":"Could not find 50") << " in this binary tree" << endl;
大体如此.
BinaryTree 使用g++ -ansi -pedantic -W -Wall 编译通过，版本是3.4.6
