小代碼 向原文學(xué)習(xí) BST 簡單的C語言版本

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

/*/在給定的BST中插入結(jié)點(diǎn)，其數(shù)據(jù)域(數(shù)值)為element/*/
void BSTInsert( BiTree *t, Elemtype element )
{/*/每次插入 開辟空間/*/
	if( NULL == *t ) {
		(*t) = (BiTree)malloc(sizeof(BiTNode));
		(*t)->data = element;
		(*t)->lchild = (*t)->rchild = NULL;
	}
/*/依據(jù)二叉搜索樹性質(zhì)/*/
	if( element == (*t)->data ) return ; /*/不允許有重復(fù)的數(shù)據(jù)，若遇到直接不處理/*/
	else if( element < (*t)->data ) BSTInsert( &(*t)->lchild, element );
	     else                       BSTInsert( &(*t)->rchild, element );
}

/*/創(chuàng)建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 ) /*/結(jié)點(diǎn)存在而數(shù)值不等時/*/
	{
		if( key < p->data )  p = p->lchild ;
		 else 	         	p = p->rchild ;
	}/*/ 走出循環(huán)后 p指針總是指向找到的元素 或者 葉子結(jié)點(diǎn)下的空結(jié)點(diǎn)/*/
	if( NULL != p ) printf("查找成功!\n");
	 else    	    printf("無此元素!\n");
}

/*/BST結(jié)點(diǎn)的刪除    本二叉樹內(nèi)容重點(diǎn)/*/
void DelBSTNode( BiTree t, Elemtype key )
{
	BiTree p, q;
	p = t;
	Elemtype temp;
	/*/ 先遍歷找這元素/*/
	while( NULL != p && key != p->data ) {
		q = p; /*/ q總是在結(jié)點(diǎn)p的上方（當(dāng)p不是根結(jié)點(diǎn)時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:結(jié)點(diǎn)p的雙親結(jié)點(diǎn)為q，且p為葉子結(jié)點(diǎn)，則直接將其刪除。/*/
		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:結(jié)點(diǎn)p的雙親結(jié)點(diǎn)為q，且p只有左子樹或只有右子樹，
		則可將p的左子樹或右子樹直接改為其雙親結(jié)點(diǎn)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:結(jié)點(diǎn)p的雙親結(jié)點(diǎn)為q，且p既有左子樹又有右子樹。
		本代碼使用直接前驅(qū)（也可以直接后繼）這里找的是左子樹中最大的元素/*/	
		else if( NULL != p->lchild && NULL != p->rchild ) {
				BiTree s, sParent;
				sParent = p;
				s = sParent->lchild ;
				while( NULL != s->rchild )	{/*/找到p的直接前驅(qū)/*/
					sParent = s;
					s = s->rchild ;	      /*/左子樹最大的總是在左子樹中最右下角/*/
				}
				temp = s->data ;	    /*/此時 s指向的是最大的右下葉子結(jié)點(diǎn) 為一般情況1 直接刪除/*/
				DelBSTNode( t, temp );
				p->data = temp;   /*/最后將原來要刪除的p的數(shù)據(jù)改為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("請輸入二叉查找樹的結(jié)點(diǎn)數(shù):\n");
	scanf("%d", &n);

	a = (int *)malloc(sizeof(int)*n);
	printf("請輸入二叉找樹的結(jié)點(diǎn)數(shù)據(jù):\n");
	for( int i=0; i<n; i++ )
		scanf("%d", &a[i]);
	CreateBST( &t, a, n );
	printf("當(dāng)前二叉查找樹的中序遍歷結(jié)果為:\n");
	PrintBST( t );
	printf("\n##############################################\n");
	
	printf("請輸入要查找的元素:\n");
	scanf("%d", &key);
	printf("BST遞歸查找結(jié)果:\n");
	SearchBST( t, key );		//遞歸查找

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

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

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

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