查找（二叉排序树）

教材：严版数据结构 P227-231

实现：算法9.5-9.8

代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
 
using namespace std;
 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define EQ(a,b) (a==b)
#define LT(a,b) (a<b)
 
typedef int Status;
typedef char TElemType;
typedef int KeyType;
typedef struct {
	KeyType key;//关键字域
}ElemType;
 
typedef struct BiTNode {
	ElemType data;
	struct BiTNode *lchild, *rchild;//左右孩子指针
}BiTNode,*BiTree;
 
//插入
Status InsertBST(BiTree &T,ElemType e)
{
	if (T == NULL)
	{
		T = (BiTNode *)malloc(sizeof(BiTNode));
		T->lchild = T->rchild = NULL;
		T->data = e;
		return 1;
	}
	else
	{
		//关键字已存在于树中，插入失败，返回0
		if (e.key == T->data.key)
			return 0;
		else if (e.key < T->data.key)
			return InsertBST(T->lchild, e);
		else
			return InsertBST(T->rchild, e);
	}
}
//前序遍历
void PreOrderTraverse(BiTree T)
{
	if (T)
	{
		cout << T->data.key << " ";
		if (T->lchild)
			PreOrderTraverse(T->lchild);
		if (T->rchild)
			PreOrderTraverse(T->rchild);
	}
}
//中序递归遍历
void InOrderTraverse(BiTree T)
{
	if (T)
	{
		
		if (T->lchild)
			InOrderTraverse(T->lchild);
 
		cout << T->data.key << " ";
 
		if (T->rchild)
			InOrderTraverse(T->rchild);
	}
}
//后序递归遍历
void PostOrderTraverse(BiTree T)
{
	if (T)
	{
 
		if (T->lchild)
			PostOrderTraverse(T->lchild);		
		if (T->rchild)
			PostOrderTraverse(T->rchild);
		cout << T->data.key<<" ";
	}
}
//查找关键字
BiTree SearchBSTa(BiTree T, KeyType e)
{
	if (T == NULL)
		return NULL;
	else
	{
		if (T->data.key == e)
			return T;
		else if (e < T->data.key)
			return SearchBSTa(T->lchild, e);
		else
			return SearchBSTa(T->rchild, e);
	}
}
//删除确定结点
Status Delete(BiTree &T)
{
	BiTNode *p=new BiTNode();
	//右子树为空
	if (!T->rchild)
	{
		p = T;
		T = T->lchild;
		free(p);
	}
	//左子树为空
	else if (!T->lchild)
	{
		p = T;
		T = T->rchild;
		free(p);
	}
	else//左右子树均不空
	{
		p = T;
		BiTNode *s = new BiTNode();
		s = T->lchild;
		while (s->rchild)
		{
			T = s;
			s = s->rchild;
		}
		T->data = s->data;
		if (p != T)
			p->rchild = s->lchild;
		else
			T->lchild = s->lchild;
		delete s;
	}
	return TRUE;
}
//找到删除的结点
Status DeleteBST(BiTree &T, KeyType key)
{
	if (!T)
		return FALSE;
	else
	{
		if (EQ(key, T->data.key))
			return Delete(T);
		else if (LT(key, T->data.key))
			return DeleteBST(T->lchild, key);
		else
			return DeleteBST(T->rchild, key);
	}
}//DeleteBST
 
 
 
void main()
{
	BiTree T = NULL, s;
	int n, i;
	ElemType e;
	cout << "输入二叉排序树的结点数：";
	cin >> n;
	cout << "输入" << n << "个结点的值:" << endl;
	for (i = 1; i <= n; ++i)
	{
		cin >> e.key;
		InsertBST(T, e);
	}
	cout << "先序遍历二叉排序树，结果是：" << endl;
	PreOrderTraverse(T);
	cout << endl;
	cout << "中序遍历二叉排序树，结果是：" << endl;
	InOrderTraverse(T);
	cout << endl;
	cout << "后序遍历二叉排序树，结果是：" << endl;
	PostOrderTraverse(T);
	cout << endl;
	cout << "输入要查找结点的值：\n";
	cin >> e.key;
	s = SearchBSTa(T, e.key);
	if (s)
	{
		printf("已找到！结点的八进制地址为：%o\n", s);
	}
	else
	{
		printf("没找到");
	}
	cout << "输入插入结点的值：";
	cin >> e.key;
	InsertBST(T, e);
	cout << "先序遍历二叉排序树，结果是：" << endl;
	PreOrderTraverse(T);
	cout << endl;
	cout << "中序遍历二叉排序树，结果是：" << endl;
	InOrderTraverse(T);
	cout << endl;
	cout << "后序遍历二叉排序树，结果是：" << endl;
	PostOrderTraverse(T);
	cout << endl;
 
	cout << "输入要删除结点的值：" << endl;
	cin >> e.key;
	DeleteBST(T, e.key);
	cout << "先序遍历二叉排序树，结果是：" << endl;
	PreOrderTraverse(T);
	cout << endl;
	cout << "中序遍历二叉排序树，结果是：" << endl;
	InOrderTraverse(T);
	cout << endl;
	cout << "后序遍历二叉排序树，结果是：" << endl;
	PostOrderTraverse(T);
	cout << endl;
	system("pause");
}