# 用类创建二叉搜索树

Node.h:

``````#ifndef NODE_H
#define NODE_H

template <typename T>
class Node
{
public:
T content;
Node *left;
Node *right;
};

#endif``````

Tree.h:

``````/********************************************************************
*@Program: come true the two search tree 注：英语欠佳有些注释用的中文
*@Author: kingduo
*@Date: 2015/5/17 First Release
**********************************************************************/
#ifndef TREE_H
#define TREE_H
#include "Node.h"

class Tree
{
public:
Tree();
~Tree();
void Insert(int content);
void Remove(int content);
int Find(int content);
int FindMax();
int FindMin();
void Print();
void Clear();
private:
Node <int> *root;
void Print(const Node<int> *node);
const int FindMax(const Node<int> *node);
const int FindMin(const Node<int> *node);
Node<int> *Find(int content, Node<int> *node);
void Remove(int content, Node<int> *&node);
void Clear(Node<int> *node);
};

#endif``````

Tree.cpp:
``````#include "Tree.h"
#include <iostream>

using namespace std;

Tree::Tree()
{
root = NULL;
}

Tree::~Tree()
{
Clear(root);
root = NULL;
}

/*the function is insert the content to tree*/
void Tree::Insert(int value)
{
Node<int> *newnode = new Node<int>;
newnode->content = value;
newnode->left = NULL;
newnode->right = NULL;
if (root == NULL)
root = newnode;
else
{
Node<int> *loopnode = root;
while (loopnode != NULL)
{
if (value == loopnode->content)
{
cout<<"The value is exist!"<<endl;
break;
} else
{
if (value < loopnode->content)
{
if (loopnode->left == NULL)
{
loopnode->left = newnode;
break;
}
loopnode = loopnode->left;
} else
{
if (loopnode->right == NULL)
{
loopnode->right = newnode;
break;
}
loopnode = loopnode->right;
}
}
}
}
}

/*********************************************************************************************************************

**********************************************************************************************************************/
void Tree::Remove(int value)
{
if (root == NULL)
cout<<"The tree is empty."<<endl;
else
Remove(value, root);
}

/**********************************************************************************************************************
the function is remove the content by recursion

**********************************************************************************************************************/
void Tree::Remove(int value, Node<int> *&node)
{
if (node != NULL)
{
if (value == node->content)
{
if (node->left != NULL && node->right != NULL)
{
node->content = FindMin(node->right);
Remove(node->content, node->right);
} else
{
Node<int> * delnode = node;
node = node->left? node->left : node->right;
delete delnode;
}
} else
{
if (value < node->content)
Remove(value, node->left);
else
Remove(value, node->right);
}
} else
cout<<"No find it."<<endl;
}

/* the function is print the min number by recursion */
const int Tree::FindMax(const Node<int> *node)
{
if (node->right == NULL)
return node->content;
else
FindMax(node->right);
}

int Tree::FindMax()
{
if (root == NULL)
{
cout<<"The Tree is empty!"<<endl;
return -1;
} else
return FindMax(root);
}

/* the function is print the min unmber by recursion */
const int Tree::FindMin(const Node<int> *node)
{
if (node->left == NULL)
return node->content;
else
FindMin(node->left);
}

int Tree::FindMin()
{
if (root == NULL)
{
cout<<"The tree is empty!"<<endl;
return -1;
} else
return FindMin(root);
}

int Tree::Find(int value)
{
if (root == NULL)
{
cout<<"The tree is empty."<<endl;
return -1;
} else
{
Node<int> *node = Find(value, root);
if (node == NULL)
return -1;
else
return node->content;
}
}

/* the function is find the content in tree*/
Node<int> *Tree::Find(int value, Node<int> *node)
{
if (node == NULL)
{
cout<<"Can't find it.The node is not exist."<<endl;
return NULL;
} else
{
if (value == node->content)
return node;
else if (value < node->content)
Find(value, node->left);
else
Find(value, node->right);
}
}

/* the function is print all the tree by recursion and use infix*/
void Tree::Print(const Node<int> *node)
{
if (node == NULL)
return;
else
{
Print(node->left);
cout<<node->content<<endl;
Print(node->right);
}
}

/* print the tree by Print(Node<int> *) function */
void Tree::Print()
{
if (root == NULL)
cout<<"The tree is empty!"<<endl;
else
Print(root);
}

/* clear the tree */
void Tree::Clear(Node<int> *node)
{
if (node !=  NULL)
{
Clear(node->left);
Clear(node->right);
delete node;
}
}

void Tree::Clear()
{
Clear(root);
root = NULL;
}``````

;