算法基础（七）：二叉排序树基本操作-插入、删除（附源代码加注释）

#include"stdafx.h"
#include"Basic_Symbol.h"

#define MaxSize 100
typedef int KeyType;		//定义关键字类型
typedef char InfoType;		
typedef struct node			//定义结点类型
{
	KeyType key;			//关键字项
	InfoType data;			//数据域
	struct node
		*lchild,
		*rchild;			//左右孩子指针
}BSTNode;

int path[MaxSize];			//全局变量，用于存放路径
void DispBST(BSTNode *b);	//函数声明

int InsertBST(BSTNode *&p, KeyType k)			//P为根节点，插入关键字为K的结点
{
	if( p == NULL)								//如果原树为空，则操作
	{
		p = (BSTNode *)malloc(sizeof(BSTNode)); //分配空间
		p->key = k;
		p->lchild = p->rchild = NULL;			//左右孩子初值为空
		return 1;
	}
	else if(k == p->key)
		return 0;
	else if(k < p->key)							//如果小于，则放左边
		return InsertBST(p->lchild,k);
	else return InsertBST(p->rchild,k);			//大于，放右边，满足二叉排序树的特点
}

BSTNode *CreatBST(KeyType A[],int n)			//利用数组A中的元素作为关键字来构造二叉树，n为要建立的结点个数，应小于数组长度
{
	BSTNode *bt = NULL;
	int i = 0;
	while(i< n)									//循环加递归构造二叉排序树
		if(InsertBST(bt,A[i]) == 1)
		{
			printf("\nthe number %d step:",i+1,A[i]);
			DispBST(bt);
			i++;
		}
	return bt;									//返回根指针
}

void Delete1(BSTNode *p,BSTNode *&r)			//当被删除结点p有左右子树时的删除过程
{
	BSTNode *q;
	if(r->rchild != NULL)		//如果右孩子不为空
	{
		Delete1(p,r->rchild);	//删除右孩子
	}
	else						
	{
		p->key = r->key;
		q = r;
		r = r->lchild;
		free(q);
	}
}
void Delete( BSTNode *&p)		//从二叉排序树中删除*p结点
{
	BSTNode *q;
	if(p->rchild == NULL)		//没有右子树的情况
	{
		q = p;
		p = p->lchild;
		free(q);
	}
	else if(p->lchild == NULL)	//没有左子树
	{
		q = p;
		p = p->rchild;
		free(q);
	}
	else Delete1(p,p->lchild);	//左右都有
}
int DeleteBST(BSTNode *&bt,KeyType k)		//在bt中删除关键字为k的结点
{
	if(bt == NULL)
		return 0;							//空树，删除失败
	else
	{
		if(k < bt->key)
			return DeleteBST(bt->lchild,k);
		else if(k>bt->key)
			return DeleteBST(bt->rchild,k);
		else 
		{
			Delete(bt);
			return 1;
		}
	}
}
void SearchBST1(BSTNode *bt,KeyType k,KeyType path[],int i)		
{
	int j;
	if(bt == NULL)			
		return;
	else if(k == bt->key)
	{
		path[i+1] = bt->key;
		for(j = 0;j<=i+1;j++)
			printf("%3d",path[j]);
		printf("\n");
	}
	else 
	{
		path[i + 1] = bt->key;
		if(k < bt->key)
			SearchBST1(bt->lchild,k,path,i+1);
		else 
			SearchBST1(bt->rchild,k,path,i+1);
	}
}
int SearchBST2(BSTNode *bt,KeyType k)
{
	if(bt == NULL)
		return 0;
	else if(k == bt->key)
	{
		printf("%3d",bt->key);
		return 1;
	}
	else if(k < bt->key)
		SearchBST2(bt->lchild,k);
	else SearchBST2(bt->rchild,k);
	printf("%3d",bt->key);
}
void DispBST(BSTNode *bt)
{
	if(bt != NULL)
	{
		printf("%d",bt->key);
		if(bt->lchild != NULL || bt->rchild != NULL)
		{
			printf("(");
			DispBST(bt->lchild);
			if(bt->rchild != NULL)
				printf(",");
			DispBST(bt->rchild);
			printf(")");
		}
	}
}

KeyType predt = -32767;
int JudgeBST(BSTNode *bt)
{
	int b1,b2;
	if(bt == NULL)
		return 1;
	else
	{
		b1 = JudgeBST(bt->lchild);
		if(b1 == 0 || predt >= bt->key)
			return 0;
		predt = bt->key;
		b2 = JudgeBST(bt->rchild);
		return b2;
	}
}
void main()
{
	BSTNode *bt;
	KeyType k = 6;
	int n = 10;
	int a[] = {4,9,0,1,8,6,3,5,2,7};
	printf("create a BST Tree:\n");
	bt = CreatBST(a,n);
	printf("BST:\n");
	DispBST(bt);
	printf("\n");
	printf("bt%s\n",(JudgeBST(bt)?"yes,it is a bst":"no,it is not a bst"));
	printf("\n");
	printf("\nsearch the keyword(di gui) : %d",k);
	SearchBST1(bt,k,path, -1);
	printf("\nsearch the keyword(not di gui) : %d",k);
	printf("\ndelete...");
	printf("\nthe origin BST:");
	DispBST(bt);
	printf("\n delete the node 4..");
	DeleteBST(bt,4);
	DispBST(bt);
	printf("\n delete the node 5..");
	DeleteBST(bt,5);
	DispBST(bt);
	printf("\n");
}

算法基础（七）：二叉排序树基本操作-插入、删除（附源代码加注释）,布布扣,bubuko.com

算法基础（七）：二叉排序树基本操作-插入、删除（附源代码加注释）

原文：http://blog.csdn.net/zjc_game_coder/article/details/21038935