bstnode.cpp

用C语言编写实现数据结构方面的例子

#include <stdio.h>
#include <malloc.h>

typedef int KeyType;

typedef struct BSTNode
{
	KeyType key;
	struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree;


void InsertBST(BSTree *t,KeyType k)
{//若二叉排序树*t没有关健字k,则插入,否则直接返回

	BSTree p=*t;
	BSTree f;

	while(p)
	{
		if (p->key==k)
		{
			return ;
		}
		f=p;
		p=(k<p->key)?p->lchild:p->rchild;
			
	}

	p=(BSTNode *)malloc(sizeof(BSTNode));

	p->key=k;
	p->lchild=p->rchild=NULL;
	
	if (*t==NULL)
	{
		*t=p;
	}
	else if (k<f->key)
	{
		f->lchild=p;
	}
	else
		f->rchild=p;

}

void BSTNodeVisit(BSTNode *t)
{
	printf("%#x,%d,%#x,%#x\n",t,t->key,t->lchild,t->rchild);
}


BSTree SearchBST(BSTree t,KeyType k)
{
	if (!t||k==t->key)
	{
		return t;
	}
	else if (k<t->key)
	{
		return SearchBST(t->lchild,k);
	}
	else return SearchBST(t->rchild,k);

}

void PreOrderTraverse(BSTree t)
{
	if (t)
	{
		BSTNodeVisit(t);
		PreOrderTraverse(t->lchild);
		PreOrderTraverse(t->rchild);
	}
}

void DelBST(BSTree *t,KeyType k)
{//在二叉树*t中删除关健字k的结点

	BSTree p=*t;
	BSTree f=NULL;//f最终指向被删除结点的双亲

	BSTree q=NULL;
	BSTree s=NULL;

	while (p)
	{
		if (p->key==k)//找到关健字k的结点
		{
			break;
		}
		f=p;

		p=(k<p->key)?p->lchild:p->rchild;
	}

	if (!p)//无关健字k的结点
	{
		printf("未找到要删除的结点\n");
		return ;
	}

	if (!p->lchild)//被删结点*p无左孩子
	{
		if (p==*t)//被删结点是根结点
		{
			*t=p->rchild;
		}

		else if (f->lchild==p)//将双亲结点的左(右)指针指向被删除结点的右孩子
		{
			f->lchild=p->rchild;
		}
		else
			f->rchild=p->rchild;
	
		free(p);
	}
	else//被删除结点*p有左孩子
	{
		q=p;
		s=p->lchild;

		while (s->rchild)//查找*p的中序遍历的前驱*s
		{
			q=s;
			s=s->rchild;
		}

		p->key=s->key;

		if (q!=p)
		{
			q->rchild=s->lchild;
		}
		else
			p->lchild=s->lchild;

		free(s);
		
	}

}

int main()
{
	int i;
	int flag=1;
	int select;
	char ch;
	int num;//初始二叉树的个数
	KeyType tre;//二叉树的关健字
	int search;//查找的结点
	int del;//删除的结点

	BSTree sea=(BSTree)malloc(sizeof(BSTree));//查找后的二叉树
	sea=NULL;

	BSTree tree=(BSTree )malloc(sizeof(BSTNode));
	tree=NULL;

	printf("请输入二叉树的个数:");
	scanf("%d",&num);

	for (i=0;i<num;i++)
	{
		printf("请输入关健字:");
		scanf("%d",&tre);
		InsertBST(&tree,tre);
	}

	while (flag)
	{
		printf("1....PreOrderTraverse()\n");
		printf("2....SearchBST()\n");
		printf("3....DelBST()\n");
		printf("4....InsertBST()\n");
		printf("请选择1--4\n");
			
		scanf("%d",&select);
	
		switch(select)
		{
		case 1:
			printf("二叉树前序遍历结果:\n");
			PreOrderTraverse(tree);
			break;
		case 2:
			printf("请输入要查找的数:");
			scanf("%d",&search);
			sea=SearchBST(tree,search);
			printf("查找后的新二叉树前序遍历结果:\n");
			PreOrderTraverse(sea);
			break;
		case 3:
			printf("请输入要删除的结点:");
			scanf("%d",&del);
			DelBST(&tree,del);
			printf("删除后的二叉树前序遍历结果:\n");
			PreOrderTraverse(tree);
			break;
		case 4:
			printf("请输入新插入关健字:");
		    scanf("%d",&tre);
	    	InsertBST(&tree,tre);
			break;
		}

		printf("继续操作(Y|N):");

		getchar();
		ch=getchar();

		flag=((ch=='n'||ch=='N')?0:1);
	}
	
	return 0;
}