二叉排序树的构造，插入，删除，完整c代码实现

淡淡的烟草味﹌ 2023-10-17 17:13 2阅读 0赞

\#include <stdio.h>  
\#include <stdlib.h>  
typedef struct BiTNode\{  
int data;  
struct BiTNode \*lchild, \*rchild;  
\}BiTNode, \*BiTree;  
//在给定的BST中插入结点，其数据域为element  
void BSTInsert( BiTree \*t, int element )  
\{  
if( NULL == \*t ) \{  
(\*t) = (BiTree)malloc(sizeof(BiTNode));  
(\*t)->data = element;  
(\*t)->lchild = (\*t)->rchild = NULL;  
\}  
  
if( element == (\*t)->data )  
return ;  
  
else if( element < (\*t)->data )  
BSTInsert( &(\*t)->lchild, element );  
  
else  
BSTInsert( &(\*t)->rchild, element );  
\}  
  
//创建BST  
void CreateBST( BiTree \*t, int \*a, int n )  
\{  
(\*t) = NULL;  
for( int i=0; i<n; i++ )  
BSTInsert( t, a\[i\] );  
\}  
  
//BST的递归查找  
void SearchBST( BiTree t, int key )  
\{  
BiTree p;  
p = t;  
if( p ) \{  
if( key == p->data )  
printf("查找成功!\\n");  
else if( (key < p->data) && (NULL != p->lchild) )  
SearchBST( p->lchild , key );  
else if( (key > p->data) && (NULL != p->rchild) )  
SearchBST( p->rchild , key );  
else  
printf("无此元素!\\n");  
\}  
\}  
  
//BST结点的删除  
void DelBSTNode( BiTree t, int key )  
\{  
BiTree p, q;  
p = t;  
int temp;  
while( NULL != p && key != p->data ) \{  
q = p;  
if( key < p->data )  
p = p->lchild ;  
else  
p = p->rchild ;  
\}  
  
if( NULL == p )  
printf("无此元素!\\n");  
else \{  
//情况1:结点p的双亲结点为q，且p为叶子结点，则直接将其删除。  
if( NULL == p->lchild && NULL == p->rchild ) \{  
if( p == q->lchild )  
q->lchild = NULL;  
if( p == q->rchild )  
q->rchild = NULL;  
free(p);  
p = NULL;  
\}  
//情况2:结点p的双亲结点为q，且p只有左子树或只有右子树，则可将p的左子树或右子树直接改为其双亲结点q的左子树或右子树。  
else if( (NULL == p->rchild && NULL != p->lchild) ) \{ //p只有左子树  
if( p == q->lchild )  
q->lchild = p->lchild ;  
else if( p == q->rchild )  
q->rchild = p->lchild ;  
free(p);  
p = NULL;  
\}  
else if( NULL == p->lchild && NULL != p->rchild ) \{ //p只有右子树  
if( p == q->lchild )  
q->lchild = p->rchild ;  
if( p == q->rchild )  
q->rchild = p->rchild ;  
free(p);  
p = NULL;  
\}  
//情况3:结点p的双亲结点为q，且p既有左子树又有右子树。本代码使用直接前驱（也可以直接后继）  
  
else if( NULL != p->lchild && NULL != p->rchild ) \{  
BiTree s, sParent;  
sParent = p;  
s = sParent->lchild ;  
while( NULL != s->rchild ) \{ //找到p的直接前驱  
sParent = s;  
s = s->rchild ;  
\}  
temp = s->data ;  
DelBSTNode( t, temp );  
p->data = temp;  
\}  
\}  
  
\}  
  
//中序遍历打印BST  
void PrintBST( BiTree t )  
\{  
  
  
if( t ) \{  
PrintBST( t->lchild);  
printf("%d ", t->data);  
PrintBST( t->rchild);  
\}  
  
  
\}  
  
int main()  
\{  
int n;  
int \*a;  
int key;  
BiTree t;  
printf("请输入二叉查找树的结点数:\\n");  
scanf("%d", &n);  
a = (int \*)malloc(sizeof(int)\*n);  
printf("请输入二叉找树的结点数据:\\n");  
for( int i=0; i<n; i++ )  
scanf("%d", &a\[i\]);  
CreateBST( &t, a, n );  
printf("当前二叉查找树的遍历为:\\n");  
PrintBST( t );  
printf("\\n");  
printf("请输入要查找的元素:\\n");  
scanf("%d", &key);  
printf("查找结果:\\n");  
SearchBST( t, key ); //递归查找  
printf("\\n");  
printf("请输入要删除的元素:\\n");  
scanf("%d", &key);  
DelBSTNode( t, key );  
printf("当前二叉查找树的遍历为:\\n");  
PrintBST( t);  
printf("\\n");  
return 0;

代码已实现！