/***************************
运行环境 http://www.anycodes.cn/zh/
原文件 http://www.cnblogs.com/hanxi/archive/2012/08/18/2645929.html
带注释的C++类版本 BST 二叉搜索树
***************************/
#ifndef BTREE_H_
#define BTREE_H_
#include
#include
#include
using namespace std;
template
class BSTree
{
private:
class BSTNode
{
public:
BSTNode* left;
BSTNode* right;
TreeDataType data; BSTNode():left(NULL),right(NULL) {}
BSTNode(TreeDataType a_data):data(a_data),left(NULL),right(NULL) {}
};//节点声明
typedef BSTNode* BSTNodePointer;
BSTNodePointer m_root;
public:
BSTree():m_root(NULL) {}
~BSTree() {deleteNode(m_root);}
bool isEmpty() const {return m_root == NULL;}
bool find(const TreeDataType& a_data) const;
void insert(const TreeDataType& a_data) {insertAux(m_root,a_data);}
void remove(const TreeDataType& a_data);
void inorder(ostream& out) const {inorderAux(out, m_root);}
void graph(ostream& out) const {graphAux(out, 0, m_root);}
protected:
void deleteNode(BSTNodePointer a_node);/*/删除节点和所有到子节点/*/
void insertAux(BSTNodePointer& a_subRoot, const TreeDataType& a_data);
void inorderAux(ostream& out, BSTNodePointer a_subRoot) const;
void graphAux(ostream& out, int a_indent, BSTNodePointer a_subRoot) const;
void find2(const TreeDataType& a_data, bool& found, BSTNodePointer& a_locPtr, BSTNodePointer& a_parent) const;
};/*/类模板声明结束/*/
#endif
template
inline void BSTree::deleteNode(BSTree::BSTNodePointer a_node)
{/*/递归删除结点/*/
if (a_node->left != NULL)
{
deleteNode(a_node->left);
}
else if (a_node->right != NULL)
{
deleteNode(a_node->right);
}
else if (a_node != NULL)
{
delete a_node;
a_node = NULL;
}
}
template
inline void BSTree::insertAux(BSTree::BSTNodePointer& a_subRoot, const TreeDataType& a_data)
{/*/ 递归 插入结点 /*/
if (a_subRoot == NULL)
{
a_subRoot = new BSTree::BSTNode(a_data);
}
else if (a_data < a_subRoot->data)
{
insertAux(a_subRoot->left,a_data);
}
else if (a_subRoot->data < a_data)
{
insertAux(a_subRoot->right,a_data);
}
else
{/*/不能有相同的结点/*/
std::cerr << "a_data already in the tree!\n";
}
}
template
inline void BSTree::inorderAux(ostream& out, BSTree::BSTNodePointer a_subRoot) const
{/*/LDR中序遍历/*/
if (a_subRoot != NULL)
{
inorderAux(out, a_subRoot->left);//L
out << a_subRoot->data << " ";//V
inorderAux(out, a_subRoot->right);//R
}
}
template
inline void BSTree::graphAux(ostream& out, int a_indent, BSTree::BSTNodePointer a_subRoot) const
{/*/图表式打印树/*/
if (a_subRoot != NULL)
{
graphAux(out, a_indent+8, a_subRoot->right); //R
out << setw(a_indent) << " " << a_subRoot->data << endl; //V
graphAux(out, a_indent+8, a_subRoot->left); //L
}
}
template
inline bool BSTree::find(const TreeDataType& a_data) const
{
BSTree::BSTNodePointer locPtr = m_root;
bool found = false;
while (!found && locPtr != NULL)
{
if (a_data < locPtr->data)
{
locPtr = locPtr->left;
}
else if (locPtr->data < a_data)
{
locPtr = locPtr->right;
}
else
{
found = true;
}
}
return found;
}
template
inline void BSTree::find2(const TreeDataType& a_data, bool& found,
BSTree::BSTNodePointer& a_locPtr,
BSTree::BSTNodePointer& a_parent) const
{/*/ 这里不仅要找 还要找到p结点 已便于后期 删除找到的结点 /*/
a_locPtr = m_root;
a_parent = NULL;
found = false;
while (!found && a_locPtr != NULL)
{
if (a_data < a_locPtr->data)
{
a_parent = a_locPtr;
a_locPtr = a_locPtr->left;
}
else if (a_locPtr->data < a_data)
{
a_parent = a_locPtr;
a_locPtr = a_locPtr->right;
}
else
{
found = true;
}
}
}
template
inline void BSTree::remove(const TreeDataType& a_data)
{
bool found = false;
BSTree::BSTNodePointer x; //被删除的节点
BSTree::BSTNodePointer parent;
find2(a_data,found,x,parent);
if (!found)
{
std::cerr << "a_data is not in the tree!\n";
return;
}
if (x->left != NULL && x->right != NULL)//节点有两个子女
{
//查找x的中续后继节点及其双亲节点
BSTree::BSTNodePointer xSucc = x->right;
parent = x;
while (xSucc->left != NULL)/*/ 在右中找最左的元素/*/
{
parent = xSucc;
xSucc = xSucc->left;
}
x->data = xSucc->data; /*/ 替换要删除的结点数据/*/
x = xSucc; /*/ 转向这个替死鬼/*/
}
BSTree::BSTNodePointer subTree = x->left;
if (subTree == NULL) /*/ 看替死鬼的情况 /*/
{
subTree = x->right;
}
if (parent == NULL)
{
m_root = subTree;
}
else if (parent->left == x)
{
parent->left = subTree; /*/替死鬼的右做p的左 /*/
}
else
{
parent->right = subTree; /*/替死鬼是p的右孩子，将右孩子做p的右孩子 /*/
}
delete x;
}
/*/
-----------文件分割线-------"BSTree.h"----------------
#include "BSTree.h"
#include
#include
using namespace std;
/*/
int test()
{
/*/
数据准备 int a[]
/*/
int a[]={1,3,5,7,9,2,4,6,8,-999};
int i=0;
BSTree intBST;
cout << "Constructing empty BST\n";
cout << "BST " << (intBST.isEmpty()?"is":"is not") << "empty\n";
int number;
for (;;)
{ number=a[i++];
if (number == -999) break;
intBST.insert(number);
}
intBST.inorder(cout);
cout << endl;
intBST.graph(cout);
//测试find
for (i=0;;i++)
{
cout << "Item to find (-999 to stop):";
number=a[i];
if (number == -999) break;
bool found = intBST.find(number);
cout << boolalpha << found << endl;
}
//测试remove
for (i=0;;i++)
{
cout << "Item to remove (-999 to stop):"< intBST;
cout << "Constructing empty BST\n";
cout << "BST " << (intBST.isEmpty()?"is":"is not") << "empty\n";
int number;
for (;;)
{
cout << "Item to insert (-999 to stop):"<> number;
if (number == -999) break;
intBST.insert(number);
}
intBST.inorder(cout);
cout << endl;
intBST.graph(cout);
//测试find
for (;;)
{
cout << "Item to find (-999 to stop):";
cin >> number;
if (number == -999) break;
bool found = intBST.find(number);
cout << boolalpha << found << endl;
}
//测试remove
for (;;)
{
cout << "Item to remove (-999 to stop):";
cin >> number;
if (number == -999) break;
intBST.remove(number);
cout << endl;
intBST.graph(cout);
cout << endl;
}
intBST.inorder(cout);
}
int main()
{
test(); return 0;
}
本文名称：向原文学习 已添加字母说明BST排序二叉树
文章源于：
http://kswsj.cn/article/psegeo.html
