龙空技术网

《大话数据结构》C++实现二叉排序树的查找、插入和删除操作

人强小 269

前言:

而今我们对“c语言二叉排序树查找”大约比较关注,咱们都需要剖析一些“c语言二叉排序树查找”的相关资讯。那么小编在网摘上搜集了一些对于“c语言二叉排序树查找””的相关内容,希望你们能喜欢,兄弟们快快来学习一下吧!

#include<iostream>using namespace std;typedef int status;//定义一个数的结构体typedef struct BiTNode{	int data;	struct BiTNode* lchild, * rchild;}BiTNode, * BiTree;//函数声明void CreateBST(BiTree* T, int a[], int n);void outputBST(BiTree T);status InsertBST(BiTree* T, int key);status DeleteBST(BiTree*T,int key);status Delete(BiTree *p);//二叉排序树的查找函数定义status SearchBST(BiTree T,int key,BiTree f,BiTree *p){	if (!T)	{		*p = f;		return false;	}	else if (key==T->data)	{		*p = T;		return true;	}	else if (key<T->data)	{		return SearchBST(T->lchild,key,T,p);	}	else	{		return SearchBST(T->rchild,key,T,p);	}}//二叉排序树的插入函数定义status InsertBST(BiTree *T,int key){	BiTree p=NULL, s=NULL;	if (!SearchBST(*T,key,NULL,&p))	{		s = (BiTree)malloc(sizeof(BiTNode));		s->data = key;		s->lchild = s->rchild = NULL;		if (!p)			* T = s;		else if (key < p->data)			p->lchild = s;		else			p->rchild = s;		return true;	}	return false;}//二叉排序树的删除操作函数定义status DeleteBST(BiTree* T, int key){	if (!*T)		return false;	else	{		if (key == (*T)->data)		{			return Delete(T);		}		else if (key<(*T)->data)		{			return DeleteBST(&(*T)->lchild,key);		}		else		{			return DeleteBST(&(*T)->rchild,key);		}	}}//根据情况来删除节点status Delete(BiTree* p){	BiTree q, s;	if ((*p)->rchild==NULL)	{		q = *p; *p = (*p)->lchild; free(q);	}	else if ((*p)->lchild==NULL)	{		q = *p; *p = (*p)->rchild; free(q);	}	else	{		q = *p; s = (*p)->lchild;		while (s->rchild)		{			q = s; s = s->rchild;		}		(*p)->data = s->data;		if (q != *p)			q->rchild = s->lchild;		else			q->lchild = s->lchild;		free(s);	}	return true;}//通过一个数组来创建二叉排序树void CreateBST(BiTree*T, int a[], int n){	int i;	for (i = 0; i < n; i++)	{		InsertBST(T, a[i]);	}}//把一个二叉排序树中序遍历打印void outputBST(BiTree T){	if (T == NULL)	{		return;	}	outputBST(T->lchild);	cout << T->data << " ";	outputBST(T->rchild);}//主函数int main(){	int a[] = { 62,88,58,47,35,73,51,99,37,93 };	BiTree T = NULL;	//创建二叉排序树	CreateBST(&T, a, 10);	//在二叉排序树中插入95	InsertBST(&T, 95);	//在二叉排序树中查找节点	int b = 95;	BiTree p = NULL;	if (!SearchBST(T, b, NULL, &p))		cout << "没有找到" << endl;	else	{		cout << b << "查找结果的指针为:\n" << p << endl;	}	//在二叉排序树中删除88节点	DeleteBST(&T, 88);	//验证上述的插入和删除操作	outputBST(T);	cout << endl;	return 0;}

标签: #c语言二叉排序树查找