数据结构----查找（动态查找）

#include 
#include 
#include 
#include 
typedef int KeyType;

typedef struct {
	KeyType key;
} DataType;


typedef struct Node {
	DataType data;
	struct Node *lchild, *rchild;
} BiTreeNode, *BiTree;


BiTree BSTSearch(BiTree t, DataType x) {
	BiTreeNode *p;
	if (t != NULL) {
		p = t;
		while (p != NULL) {
			if (p->data.key == x.key) {
				//找到就返回指向该结点的指针
				return p;
			} else if (x.key < p->data.key) {
				//关键字小于结点，在左子树查找
				p = p->lchild;
			} else {
				//关键字不小于结点，在右子树查找
				p = p->rchild;
			}
		}
	}
	return NULL;
}


int BSTInsert(BiTree *t, DataType x) {
	BiTreeNode *p, *cur, *parent = NULL;
	cur = *t;
	while (cur != NULL) {
		if (cur->data.key == x.key) {
			return 0;
		}
		parent = cur;
		if (x.key < cur->data.key) {
			cur = cur->lchild;
		} else {
			cur = cur->rchild;
		}
	}
	p = (BiTreeNode *)malloc(sizeof(BiTreeNode));
	if (!p) {
		exit(-1);
	}
	p->data = x;
	p->lchild = NULL;
	p->rchild = NULL;
	if (!parent) {
		*t = p;
	} else if (x.key < parent->data.key) {
		parent->lchild = p;
	} else {
		parent->rchild = p;
	}
	return 1;
}


int BSTDelete(BiTree *t, DataType x) {
	if (!*t) {
		return 0;
	} else {
		if (x.key == (*t)->data.key) {
			DeleteNode(t);
		} else if ((*t) ->data.key > x.key) {
			//当前元素大于x的值，在左子树查找
			BSTDelete(&(*t)->lchild, x);
		} else {
			BSTDelete(&(*t)->rchild, x);
		}
		return 1;
	}
}


void DeleteNode(BiTree *x) {
	BiTree q, p, j;
	if (!(*x)->rchild) {
		q = *x;
		*x = (*x)->lchild;
		free(q);
	} else if (!(*x)->lchild) {
		q = *x;
		*x = (*x)->rchild;
		free(q);
	} else {
		p = *x;
		j = (*x)->lchild;
		while (j->rchild) {
			p = j;
			j = j->rchild;
		}
		(*x)->data = j->data;
		if (p != *x) {
			p->rchild = j->lchild;
		} else {
			p->lchild = j->lchild;
		}
		free(p);
	}
}



void InOrderTraverse(BiTree t) {
	if (t) {
		//中序遍历左子树
		InOrderTraverse(t->lchild);
		//访问根结点
		printf("%4d", t->data);
		//中序遍历右子树
		InOrderTraverse(t->rchild);
	}
}



int main(void) {
	BiTree t = NULL, p;
	DataType table[] = {55, 43, 66, 88, 18, 80, 21, 72};
	int n = sizeof(table) / sizeof(table[10]);
	DataType x = {80}, s = {18};
	int i;

	for (i = 0; i < n; i++) {
		BSTInsert(&t, table[i]);
	}

	printf("n关键字序列为:n");

	for (i = 0; i < n; i++) {
		printf("%4d", table[i]);
	}
	printf("n");

	printf("中序遍历二叉树得到的序列为:n");
	InOrderTraverse(t);
	p = BSTSearch(t, x);

	if (p != NULL) {
		printf("n二叉排序树查找:元素关键字%d查找成功！n", x);
	} else {
		printf("n二叉排序树查找:没有找到关键字%d.n", x);
	}
	BSTDelete(&t, s);
	printf("n删除元素%d后，中序遍历二叉树得到的序列为:n", s.key);
	InOrderTraverse(t);
	getch();
	printf("n");
	system("pause");
	return 0;
}