二分查找树特点：
(1) 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
(2) 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
(3) 任意节点的左、右子树也分别为二叉查找树。
(4) 没有键值相等的节点（no duplicate nodes）。
前序遍历：中左右
中序遍历：左中右
序遍历：左右中
二叉查找树的重点在于如何找节点的前驱节点和后继节点
#pragma once
#include <iostream>
using namespace std; template <class T>
class BSTNode
{
public:
T key;
BSTNode *parent;
BSTNode *left;
BSTNode *right; BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):key(value),parent(p),left(l),right(r)
{ }
}; template <class T>
class BSTree
{
private:
BSTNode<T> *mRoot; public:
BSTree():mRoot(NULL){}
~BSTree(){} // 前序排序
void preOrder()
{
preOrder(mRoot);
}
void inOrder()
{
inOrder(mRoot);
}
void postOrder()
{
postOrder(mRoot);
}
// 查找二叉树中键值为key的节点
BSTNode<T>* SearchKey(const T key)
{
return SearchKey(mRoot, key);
}
BSTNode<T>* minKey()
{
return minKey(mRoot);
}
BSTNode<T>* maxKey()
{
return maxKey(mRoot);
}
// 插入节点
void insert( T key)
{
BSTNode<T> *z = new BSTNode<T>(key, NULL, NULL, NULL); if (z == NULL)
{
return;
}
insert(mRoot, z);
} private:
// 前序排序
void preOrder(BSTNode<T> *tree) const
{
if (tree != NULL)
{
cout << tree->key << " ";
preOrder(tree->left);
preOrder(tree->right);
}
} // 中序排序
void inOrder(BSTNode<T> *tree) const
{
if (tree != NULL)
{
preOrder(tree->left);
cout << tree->key << " ";
preOrder(tree->right);
}
} // 后序排序
void postOrder(BSTNode<T> *tree) const
{
if (tree != NULL)
{
preOrder(tree->left);
preOrder(tree->right);
cout << tree->key << " ";
}
}
BSTNode<T>* SearchKey(BSTNode<T>* pNode, const T key) const
{
// 递归查找
/*if (pNode = NULL || key == pNode->key)
{
return pNode;
}
else if (key > pNode->key)
{
return SearchKey(pNode->right);
}
else
{
return SearchKey(pNode->left);
}*/ // 非递归查找
BSTNode<T>* x = pNode;
while (x != NULL)
{
if (key > x->key)
{
x = x->right;
}
else if (key < x->key)
{
x = x->left;
}
else
{
return x;
}
} return NULL;
}
// 将节点插入到二叉树中
void insert(BSTNode<T>* &tree, BSTNode<T> *Node)
{
BSTNode<T> *y = NULL;
BSTNode<T> *x = tree;
while (NULL != x)
{
y = x;
if (Node->key > x->key)
{
x = x->right;
}
else
{
x = x->left;
}
} Node->parent = y; // 这到后面两句为关键代码
if (NULL == y)
{
tree = Node;
}
else if (Node->key > y->key)
{
y->right = Node;
}
else
{
y->left = Node;
}
}
// 查找最小节点
BSTNode<T>* minKey(BSTNode<T>* pNode) const
{
while (pNode != NULL)
{
pNode = pNode->left;
} return pNode;
}
BSTNode<T>* maxKey(BSTNode<T>* pNode) const
{
while (pNode != NULL)
{
pNode = pNode->right;
} return pNode;
}
// 找节点（x）的后继节点。即查找二叉树中数值大于该节点的最小值
BSTNode<T>* Successor(BSTNode<T>* x)
{
// 分三种情况
// 1. x有右孩子，找到以右孩子为根的子树的最小节点
// 2. x没有右孩子，当x为左孩子，则x的父节点为后继节点
// 2. x没有右孩子，当x为右孩子，则找x的最低父节点，并且该父节点具有左孩子
if (x->right != NULL)
{
return minKey(x->right);
}
BSTNode<T>* y = x->parent;
while ((NULL != y) &&(x == y->right))
{
x= y;
y = y->parent;
} return y;
}
// 找结点(x)的前驱结点。即查找"二叉树中数据值小于该结点"的"最大结点"
BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)
{
// 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
if (x->left != NULL)
return maxKey(x->left); // 如果x没有左孩子。则x有以下两种可能：
// (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
// (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
BSTNode<T>* y = x->parent;
while ((y!=NULL) && (x==y->left))
{
x = y;
y = y->parent;
} return y;
} // 删除二叉树中的节点，并返回被删除的节点
//BSTNode<T>* RemoveNode(BSTNode<T>* &tree, BSTNode<T>* pNode)
//{
// BSTNode<T>* x = tree; // while (NULL != x && pNode->key != x->key)
// {
// if (pNode->key > x->key)
// {
// x = x->right;
// }
// else if (pNode->key < x->key)
// {
// x = x->left;
// }
// } // // 找到或x为空 //}
};