BinarySortTree.h

typedef int ElemType;

typedef enum
{
	FALSE, TRUE
} Status;

typedef struct BitNode
{
	ElemType data;
	BitNode *lchild, *rchild;
	BitNode()
	{
		lchild = rchild = NULL;
	}
} *BiTree;

Status SearchBST(BiTree T, ElemType key, BiTree f, BiTree &p) //查找关键字
//在根指针T所指的二叉排序树中递归的查找其关键字等于key的数据元素，若查找成功
//用p返回元素节点并返回TRUE，否则指针p返回查找路径上访问的最后一节点并返回FALSE
//指针f指向T的双亲，其初始调用值为NULL
{
	if (T == NULL) //查找不成功
	{
		p = f;
		return FALSE;
	}
	else if (key == T->data) //查找成功
	{
		p = T;
		return TRUE;
	}
	else if (key < T->data) //左子树中查找
		return SearchBST(T->lchild, key, T, p);
	else
		//右子树查找
		return SearchBST(T->rchild, key, T, p);
}

Status InsertBST(BiTree &T, ElemType key)
//二叉排序树中不存在关键字等于key的数据元素时,插入key并返回TRUE
//否则返回FALSE
{
	BiTree p, insert;
	if (SearchBST(T, key, NULL, p) == FALSE) //查找不成功
	{
		insert = new BitNode; //开辟节点
		insert->data = key;
		if (p == NULL) //没有元素的情况
			T = insert;
		//利用SearchBST()返回的指针将其缀在相应的子树上
		else if (key < p->data)
			p->lchild = insert;
		else
			p->rchild = insert;
		return TRUE;
	}
	return FALSE;
}

Status Delete(BiTree &p)
//从二叉排序树中删除节点p并重接它的左子树和右子树
{
	BiTree q, s;
	if (p->lchild == NULL) //左子树空重接其右子树
	{
		q = p;
		p = p->rchild;
		delete q;
	}
	else if (p->rchild == NULL) //右子树空重接其左子树
	{
		q = p;
		p = p->lchild;
		delete q;
	}
	else //左右子树均非空
	{
		q = p;
		s = p->lchild;
		while (s->rchild != NULL)
		{
			q = s;
			s = s->rchild;
		}
		p->data = s->data;
		if (q != p)
			q->rchild = s->lchild;
		else
			q->lchild = s->lchild;
		delete s;
	}
	return TRUE;
}

Status DeleteBST(BiTree &T, ElemType key)
//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素节点并返回TRUE否则返回FALSE
{
	if (T == NULL) //查找不成功
		return FALSE;
	else
	{
		if (key == T->data)
			return Delete(T);
		else if (key < T->data)
			return DeleteBST(T->lchild, key);
		else
			return DeleteBST(T->rchild, key);
	}
}

Status TraverseBST(BiTree T)
{
	if (T == NULL)
		return FALSE;
	else
	{
		cout << T->data << endl;
		TraverseBST(T->lchild);
		TraverseBST(T->rchild);
	}
}

main.cpp

#include<iostream>
using namespace std;

#include"BinarySortTree.h"

int main()
{
	BiTree T = NULL;
	ElemType key;
	short choice;
	while (1)
	{
		system("cls");
		cout << "1 . InsertBST()" << endl << "2 . DeleteBST()" << endl
				<< "3 . TraverseBST()" << endl;
		cin >> choice;
		system("cls");
		switch (choice)
		{
		case 1:
			cin >> key;
			InsertBST(T, key);
			break;
		case 2:
			cin >> key;
			DeleteBST(T, key);
			break;
		case 3:
			TraverseBST(T);
			system("pause");
			break;
		}
	}
}