資料結構——二叉排序樹

二叉排序樹

二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜尋樹。

一棵空樹，或者是具有下列性質的二叉樹：

（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

（3）左、右子樹也分别為二叉排序樹；

（4）沒有鍵值相等的結點。

問題 在二叉排序樹 bt 中遞歸查找值等于 key 的元素是否存在，若在則傳回其結點指針

以下寫了一個簡單的建立二叉排序樹，周遊二叉排序樹，查找資料的代碼。

main()函數中以中序周遊為例

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include<conio.h>

//在二叉排序樹 bt 中遞歸查找值等于 key 的元素是否存在
//若在則傳回其結點指針

typedef int BTElemType; //二叉樹結點的資料類型

//二叉樹結點類型
typedef struct BiTNode{
	BTElemType data;
	struct BiTNode *lchild, *rchild;    //左右孩子指針
}BiTNode, *BiTree;

BiTree searchBSTT (BiTree bt , BTElemType key) 
{

	if ( bt == NULL) //樹空或已超過葉子
		return NULL;
	else if ( bt->data == key)//根結點等于給定值
	{
		return bt;
	}
	else if ( key < bt->data) //給定值小于根結點，進入左子樹
	{
		return searchBSTT ( bt->lchild, key) ;
	}
	else  //給定值大于根結點，進入右子樹
	{
		return searchBSTT ( bt->rchild, key) ;
	}
	
}

//在二叉排序樹 bt 中插入新資料結點 s
BiTree insertBST (BiTree bt, BiTree s) 
{  //s 在函數被調用前已建立好
	if ( bt==NULL)  //空樹，s 成為樹根
		bt = s;
	else if ( s->data < bt->data)  //新結點小于根，遞歸進入左子樹尋找插入位置
		bt->lchild=insertBST ( bt->lchild, s);
	else if ( s->data > bt->data)  //新結點大于根，遞歸進入右子樹尋找插入位置
		bt->rchild=insertBST ( bt->rchild, s) ;
	return bt;
}

//中序周遊二叉排序樹并顯示周遊序列
void inorder (BiTree bt) 
{
	if(bt!=NULL)  
	{
		inorder(bt->lchild);   //遞歸通路左孩子
		printf("%5d", bt->data);  //顯示根結點資料
		inorder(bt->rchild);  //遞歸通路右孩子
	}
}

//建立二叉排序樹, 資料從鍵盤輸入, 直到輸入值等于- 1 為止
//傳回二叉排序樹的根結點指針
BiTree createBST(void) 
{
    BiTree bt, s;
    BTElemType e;
    int i = 0;

	printf("\n請輸入資料(-1: 結束)\n");
	scanf("%d", &e);
	bt = NULL;
	while ( e!= -1) {
		s=(BiTree) malloc(sizeof(BiTNode));
		s->data = e; s->lchild = s->rchild = NULL;
		
		bt=insertBST (bt , s);  //每讀入一個資料，就插入到樹中
		scanf ("%d", &e);
	}
	printf("\n二叉排序樹建立完成\n");
	return bt;
}

//查找資料并顯示查找的次數
BiTree searchBST (BiTree bt , BTElemType key) 
{
	int count=0;
	if(bt==NULL)
	{
		return NULL;//樹空或已超過葉子
	}
	else
	{
		if(bt->data ==key)
		{
			count++;
		}
		else
		{
			while(bt->data !=key)
			{
				if(bt->data <key)//給定值大于根結點，進入右子樹
				{
					count++;
					bt=bt->rchild ;
				}
				else
				{
					count++;
					bt=bt->lchild ;//給定值小于根結點，進入左子樹
				}
			}
		}
		printf("查找次數為%4d\n",count);
	    return bt;
	}
}

int main()
{
    BiTree t, s;
    BTElemType key;
    char ch;
	//鍵盤輸入資料，建立二叉排序樹
	t=createBST();
	//中序周遊輸出二叉排序樹(檢驗建立的正确性)
	inorder(t);
	printf("\n");
	//二叉排序樹查找的測試循環
	do {
		printf("\n輸入要查找的資料值：");
		scanf("%d", &key);
		s=searchBSTT(t, key);
		if(s)
			printf("\n查找成功，資料值＝%d", s->data);
		else
			printf("\n查找失敗");

		printf("\n是否繼續(y/n)?\n");
		ch=getch();
	} while ( ch=='y' || ch=='Y');
}
return 0;

           

若代碼有錯誤的地方或是其他更好的代碼，請各位指教。