头文件：
#ifndef TREE_H
#define TREE_H
namespace wyp{
template<class T>
class SearchTree;
template<class T>
class TreeNode{
public:
TreeNode() : data(NULL){
}
TreeNode(T data, TreeNode<T> *left, TreeNode<T> *right)
: data(data), left(left), right(right){
}
friend class SearchTree<T>;
private:
T data;
TreeNode<T> *left;
TreeNode<T> *right;
};
template<class T>
class SearchTree{
public:
SearchTree() : root(NULL){
}
virtual ~SearchTree();
void insert(T item);
bool inTree(T item) const;
void inorderShow() const;
private:
void insert(T item, TreeNode<T> *& subTreeRoot);
bool inTree(T item, TreeNode<T> *subTreeRoot) const;
void deleteSubTree(TreeNode<T> *&subTreeRoot);
void inorderShow(TreeNode<T> *subTreeRoot) const;
TreeNode<T> *root;
};
}
#endif
实现：
#include "tree.h"
#include <iostream>
using namespace std;
namespace wyp{
template<class T>
void SearchTree<T>::insert(T item, TreeNode<T> *& subTreeRoot){
if(subTreeRoot == NULL){
subTreeRoot = new TreeNode<T>(item, NULL, NULL);
}else if(item < subTreeRoot->data){
insert(item, subTreeRoot->left);
}else{
insert(item, subTreeRoot->right);
}
}
template<class T>
void SearchTree<T>::insert(T item){
insert(item, root);
}
template<class T>
bool SearchTree<T>::inTree(T item, TreeNode<T> *subTreeRoot) const{
if(subTreeRoot == NULL){
return false;
}else if(subTreeRoot->data == item){
return true;
}else if(subTreeRoot->data > item){
inTree(item, subTreeRoot->right);
}else{
inTree(item, subTreeRoot->left);
}
}
template<class T>
bool SearchTree<T>::inTree(T item) const{
inTree(item, root);
}
template<class T>
void SearchTree<T>::deleteSubTree(TreeNode<T> *&subTreeRoot){
if(subTreeRoot != NULL){
deleteSubTree(subTreeRoot->left);
deleteSubTree(subTreeRoot->right);
delete subTreeRoot;
subTreeRoot = NULL;
}
}
template<class T>
void SearchTree<T>::inorderShow(TreeNode<T> *subTreeRoot) const{
if(subTreeRoot != NULL){
inorderShow(subTreeRoot->left);
cout << subTreeRoot->data << "\t";
inorderShow(subTreeRoot->right);
}
}
template<class T>
void SearchTree<T>::inorderShow() const{
inorderShow(root);
}
template<class T>
SearchTree<T>::~SearchTree(){
deleteSubTree(root);
}
}
利用：
#include <iostream>
#include "tree.h"
#include "tree.cpp"
using namespace std;
using wyp::SearchTree;
int main(){
SearchTree<int> t;
cout << "Enter the number \n";
int next;
cin >> next;
while(next >= 0){
t.insert(next);
cin >> next;
}
cout << "Show tree\n";
t.inorderShow();
cout << endl;
return 0;
}