小代碼 向原文學習 BST 簡單的C語言版本

 
 /********************************
 運行環境：http://www.anycodes.cn/zh/
 原文：http://blog.csdn.net/u014488381/article/details/41719765/
 二叉排序樹的查找算法的C代碼實現
 修改以直接測試
 待C++類封裝版本
 *********************************/
#include <stdio.h>
#include <stdlib.h>
typedef int Elemtype;
typedef struct BiTNode{
	Elemtype data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

/*/在給定的BST中插入結點，其數據域(數值)為element/*/
void BSTInsert( BiTree *t, Elemtype 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, Elemtype *a, int n )
{
	(*t) = NULL;
	for( int i=0; i<n; i++ )
		BSTInsert( t, a[i] );
}

/*/BST的遞歸查找/*/
void SearchBST( BiTree t, Elemtype 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 _SearchBST( BiTree t, Elemtype key )
{
	BiTree p;  p = t;
	while( NULL != p && key != p->data ) /*/結點存在而數值不等時/*/
	{
		if( key < p->data )  p = p->lchild ;
		 else 	         	p = p->rchild ;
	}/*/ 走出循環后 p指針總是指向找到的元素 或者 葉子結點下的空結點/*/
	if( NULL != p ) printf("查找成功!\n");
	 else    	    printf("無此元素!\n");
}

/*/BST結點的刪除    本二叉樹內容重點/*/
void DelBSTNode( BiTree t, Elemtype key )
{
	BiTree p, q;
	p = t;
	Elemtype temp;
	/*/ 先遍歷找這元素/*/
	while( NULL != p && key != p->data ) {
		q = p; /*/ q總是在結點p的上方（當p不是根結點時q總是父親）
             p就是我們要刪的元素
		/*/
		if( key < p->data )			p = p->lchild ;
		else		p = p->rchild ;
	}
	if( NULL == p )  printf("無此元素!\n");
	/*/找到元素  會有如下幾個情況
     1.         2.              3.
      q            q                   q
      /\          / \                 /  \  
     p  p        p   p               p     p
	             /     \             / \   / \  
	            x       x           x   x  x  x
	 /*/        
	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 ;	    /*/此時 s指向的是最大的右下葉子結點 為一般情況1 直接刪除/*/
				DelBSTNode( t, temp );
				p->data = temp;   /*/最后將原來要刪除的p的數據改為temp/*/
		}
	}

}

/*/
待遞歸版本的刪除 傳引用的妙處
中序遍歷打印BST/*/
void PrintBST( BiTree t )
{
	if( t ) {
		PrintBST( t->lchild );
		printf("%d ", t->data);
		PrintBST( t->rchild );
	}
}

void use()
{
	int n;
	int *a;
	Elemtype 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##############################################\n");
	
	printf("請輸入要查找的元素:\n");
	scanf("%d", &key);
	printf("BST遞歸查找結果:\n");
	SearchBST( t, key );		//遞歸查找

	printf("##############################################\n");
	printf("請輸入要刪除的元素:\n");
	scanf("%d", &key);
	DelBSTNode( t, key );
	printf("當前二叉查找樹的中序遍歷結果為:\n");
	PrintBST( t );
	printf("\n##############################################\n");

	printf("請輸入要查找的元素:\n");
	scanf("%d", &key);
	printf("BST迭代查找結果:\n");
	_SearchBST( t, key );		//迭代查找
 
}
void test()
{
	int n;  
	Elemtype key;   BiTree t;
    int a[]={5,8,2,1,4,7,9,6,3};
	printf("請輸入二叉查找樹的結點數:\n");
    n=9;
	printf("請輸入二叉找樹的結點數據:\n");
	CreateBST( &t, a, n );
	printf("當前二叉查找樹的中序遍歷結果為:\n");
	PrintBST( t );
	printf("\n##############################################\n");
	
	printf("請輸入要查找的元素:\n");
	key=8;
	printf("BST遞歸查找結果:\n");
	SearchBST( t, key );		//遞歸查找

	printf("##############################################\n");
	printf("請輸入要刪除的元素:\n");
	 key=5;
	DelBSTNode( t, key );
	printf("當前二叉查找樹的中序遍歷結果為:\n");
	PrintBST( t );
	printf("\n##############################################\n");

	printf("請輸入要查找的元素:\n");
	 key=5;
	printf("BST迭代查找結果:\n");
	_SearchBST( t, key );		//迭代查找
 
}
int main(void)
{
	printf("Hello,C world of AnycodeX!\n");
	test();
	return EXIT_SUCCESS;
}