【数据结构】二叉排序数

2021 年 12 月 10 日

583 次浏览

1591字数

```cpp
#include <stdlib.h>
#include <stdio.h>
typedef struct node
{
	int k;
	struct node *l,*r;
}BT;

BT* INSBT(BT *root,BT *new_T)
{
	BT *p = root;
	if(root==NULL) 
		root=new_T;
	else
		while(p->k!=new_T->k)
			if(p->k<new_T->k)
				if(p->r==NULL) {
					p->r=new_T;
					break;
				}
				else 
					p=p->r;
			else
				if(p->l==NULL) {
					p->l=new_T;
					break;
				}
	else p=p->l;
	return root;
}

BT* CREABT(int n)
{
	BT *root,*new_T;
	int i,key;
	for(root=NULL,i=1;i<=n;i++)
	{
		scanf("%d",&key);
		new_T=(BT*)malloc(sizeof(BT));
		new_T->k=key;
		new_T->l=new_T->r=NULL;
		root=INSBT(root,new_T);
	}
	return root;
}

BT* SEARBT(BT *root,int key)
{
	BT *p;
	for(p=root;p!=NULL&&p->k!=key;)
		if(p->k<key) 
			p=p->r;
		else p=p->l;
	return p;
}

BT* DELBT(BT *root, int key)
{								// 删除key 
	BT *p,*q,*f;
	for(q=NULL,p=root;p!=NULL&&p->k!=key;)		// 遍历找到key 
	{
		q=p;									// p 是父节点，q是当前节点 
		if(key<p->k) 
			p=p->l;
		else 
			p=p->r;
	}
	if(p->k==key)
	{
		if(p->l==NULL)
			if(q->l==p) 	
				q->l=p->r;else q->r=p->r;		// p父节点左子树为空，
		else
		{										// p父节点左子树不为空
			f=p;
			for(;p->r!=NULL;q=p,p=p->r);		// 沿着左子树的右孩子，右到底  
				f->k=p->k;
			q->r=p->l;							// 将得到最右边的节点连接到q节点的左子树 
		}
		free(p);
	}
	return root;
}

void INBT(BT *root)
{
	if(root!=NULL)
	{
		INBT(root->l);
		printf("%d ",root->k);
		INBT(root->r);
	} 
}

int main()
{
	BT *root,*p;int n,key;
	scanf("%d",&n);
	root=CREABT(n);
	INBT(root);
	scanf("%d",&key);
	p=SEARBT(root,key);
	if(p==NULL) printf("\nno exit");
	else printf("\n%d",p->k);
	root=DELBT(root,key);
	printf("\n");
	INBT(root);
	return 0;
}

```

最后修改：2021 年 12 月 13 日