二叉排序树（Binary Sort Tree）又称二叉查找树,它的特点是:
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值;
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值;
（3）左、右子树也分别为二叉排序树；
但你看到定义可能会奇怪,如果出现相等元素咋整啊.这里我们就假设右子树的结点值大于或等于根结点得了.
在这里我们实现二叉树的如下简单功能:(二叉树结点类为BTreeNode<T>)
void Insert(T val); //往二叉树中插入数据,自然要保证插入数据后仍然是二叉树
BTreeNode<T>* Search(T val); //查找值为val的结点
BTreeNode<T>* SearchMinVal(); //查找值最小的结点
BTreeNode<T>* SearchMaxVal();//查找值最大的结点
void Delete(T val); //删除任意节点
1.先定义一个二叉树的结点类
template<class T>
class BTreeNode{
public:
T val;
BTreeNode<T>* left; //指向左孩子的指针
BTreeNode<T>* right;
BTreeNode<T>* parent; //指向父结点的指针
BTreeNode(T tVal){
val = tVal;
left = right = parent = NULL;
}
bool operator==(BTreeNode<T>* bt){ //重载操作符比较两结点是否相等
return bt.val == val ? true: false;
}
};
2.定义二叉查找树的类BSortTree
#include "BTreeNode.h"
template<class T>
class BSortTree{
private:
BTreeNode<T>* root; //根结点指针
int size; //树中元素总个数
public:
BSortTree(void){
root = NULL;
size = 0;
}
~BSortTree(void){}
int Size() { return size;}
void Insert(T val){ //插入结点元素
if(root == NULL){ //树为空
BTreeNode<T>* pNode = new BTreeNode<T>(val);
root = pNode;
size++;
return;
}
InsertTree(root, val); //树不为空时插入元素
}
BTreeNode<T>* Search(T val){ //查找结点
return SearchTree(root, val);
}
BTreeNode<T>* SearchMinVal(){ //查找最小值元素
SearchTreeMinVal(root);
}
BTreeNode<T>* SearchMaxVal(){ //查找最大值元素
SearchTreeMaxVal(root);
}
void Delete(T val){ //删除任意结点
DeleteTreeNode(root, val);
}
private:
//删除节点分4种情况
//1.如果是叶子,则直接删除
//2.如果只有左子树,则删除结点后左子树上移即可
//3.如果只有右子树,则删除结点后右子树上移即可
//4.如果左右子树都有,则查找要删除结点(p)的左子树中的最大结点(m),把m的结点值赋给p,然后删除m.
void DeleteTreeNode(BTreeNode<T>* pRoot, T val){ //删除结点
BTreeNode<T>* node = Search(val); //要删除的结点
if(node == NULL) //要删除的结点不存在
return;
//1.被删结点是叶子,直接删
if(node->left==NULL && node->right==NULL){
if(node->parent == NULL){ //只有一个结点的树
size = 0;
root = NULL;
}
else if(node->parent->left == node)//被删结点是左孩子
node->parent->left = NULL;
else //结点是右孩子
node->parent->right = NULL;
delete node;
size--;
return;
}
//2.被删结点只有左子树
if(node->left !=NULL && node->right==NULL){
node->left->parent = node->parent;
if(node->parent == NULL) //被删结点是根结点
root = node->left;
else if(node->parent->left == node)//被删结点是左孩子
node->parent->left = node->left;
else //被删结点是右孩子
node->parent->right = node->right;
delete node;
size--;
return;
}
//3.被删结点只有右子树
if(node->right !=NULL && node->left==NULL){
node->right->parent = node->parent;
if(node->parent == NULL) //被删结点是根结点
root = node->right;
else if(node->parent->left == node)//被删结点是左孩子
node->parent->left = node->left;
else //被删结点是右孩子
node->parent->right = node->right;
delete node;
size--;
return;
}
//4.被删结点左右孩子都有
if(node->left !=NULL && node->right != NULL){
BTreeNode<T>* replaceNode = SearchTreeMinVal(node->right); //也可以替换成查找左子树最大值
node->val = replaceNode->val;
DeleteTreeNode(root, replaceNode->val);
}
}
void InsertTree(BTreeNode<T>* pRoot,T val)
{
BTreeNode<T>* pNode = new BTreeNode<T>(val);
if(pRoot->left == NULL && val < pRoot->val){
pRoot->left = pNode;
pNode->parent = pRoot;
size++;
return;
}
if(pRoot->right == NULL && val >= pRoot->val){
pRoot->right = pNode;
pNode->parent = pRoot;
size++;
return;
}
if(val < pRoot->val)
InsertTree(pRoot->left,val);
else
InsertTree(pRoot->right,val);
}
BTreeNode<T>* SearchTree(BTreeNode<T>* pRoot,T val){
if(pRoot == NULL)
return NULL;
else if(val == pRoot->val)
return pRoot;
else if(val < pRoot->val)
return SearchTree(pRoot->left,val);
else
return SearchTree(pRoot->right, val);
}
BTreeNode<T>* SearchTreeMinVal(BTreeNode<T>* pRoot){
if(pRoot==NULL)
return NULL;
else if(pRoot->left == NULL)
return pRoot;
elsewww.zzzyk.com
return SearchTreeMinVal(pRoot->left);
}
BTreeNode<T>* SearchTreeMaxVal(BTreeNode<T>* pRoot){
if(pRoot==NULL)
return NULL;
else if(pRoot->right == NULL)
return pRoot;
else
return SearchTreeMinVal(pRoot->right);
}
