【二叉搜索樹】:一棵樹可以為空,如果不空亮隙,必須滿足以下性質(zhì):
非空左子樹的所有的鍵值小于其根節(jié)點的鍵值
非空右子樹的所有的鍵值大于其根節(jié)點的鍵值
左途凫、右子樹都是二叉搜索樹
二叉搜索樹
/* 搜索二叉樹操作集 */
#include<stdio.h>
#include<stdlib.h>
#define SIZE 10
typedef int ElementType;
typedef struct TNode *BinTree;
typedef BinTree Position;
typedef struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
BinTree Insert(ElementType X,BinTree bst);//二叉搜索樹建立、插入
void PreOrderTraversal(BinTree bst); //輸出二叉樹
BinTree FindMinNode(BinTree bst); //返回最小元素節(jié)點的指針
BinTree FindMaxNode(BinTree bst); //返回最大元素的節(jié)點指針
BinTree FindX(ElementType X, BinTree bst); //查找元素X并返回其節(jié)點指針
BinTree DeleteX(ElementType X, BinTree bst);//刪除指定節(jié)點X并返回其指針
int main()
{
int x=1;
BinTree BST = NULL;
BinTree MinNodeOfBST=NULL;
BinTree MaxNodeOfBST=NULL;
BinTree findNodeX=NULL;
int arrary[SIZE] = { 5,2,1,3,6,7,8,9,4,0 };
for (int i = 0; i < SIZE; i++) {
BST=Insert(arrary[i],BST);
}
PreOrderTraversal(BST);
putchar('\n');
MinNodeOfBST=FindMinNode(BST);
MaxNodeOfBST=FindMaxNode(BST);
printf("Min= %d Max= %d\n", MinNodeOfBST->Data,MaxNodeOfBST->Data);
findNodeX=FindX(x,BST);
printf("%d\n", findNodeX->Data);
BST=DeleteX(1,BST);
PreOrderTraversal(BST);
putchar('\n');
BST = DeleteX(1, BST);
system("pause");
return 0;
}
/* 建立二叉樹溢吻、插入節(jié)點(只能插在葉節(jié)點) */
BinTree Insert(ElementType X,BinTree bst)
{
if(!bst){
/* 如果樹為空维费,生成并返回一個節(jié)點的二叉樹 */
bst=(BinTree)malloc(sizeof(struct TNode));
bst->Data=X;
bst->Left=bst->Right=NULL;
}else{
/* 找到要插入節(jié)點的位置 */
if(X<bst->Data){
bst->Left=Insert(X,bst->Left); //遞歸插入左子樹
}else if(X>bst->Data){
bst->Right=Insert(X,bst->Right);//遞歸插入右子樹
}else;
}
return bst;
}
/* 最小元素一定在樹的最左端分支的端節(jié)點 */
BinTree FindMinNode(BinTree bst)
{
if(!bst) return NULL;
else if(!bst->Left) return bst;
else return FindMinNode(bst->Left);
}
/* 最大元素一定在樹的最右端分支的端節(jié)點 */
BinTree FindMaxNode(BinTree bst)
{
if(!bst) return NULL;
else if(!bst->Right) return bst;
else return FindMaxNode(bst->Right);
/*
迭代實現(xiàn)
if(bst){
while(bst->Right)
bst=bst->Right;
}
return bst;
*/
}
/*
查找元素X,并返回其指針
x小于根節(jié)點鍵值促王,左子樹搜索
x大于根節(jié)點鍵值犀盟,右子樹搜索
結(jié)果相等,搜索完成蝇狼,返回指向此節(jié)點的指針
*/
BinTree FindX(ElementType X, BinTree bst)
{
if(bst){
if(X>bst->Data) //位于右子樹
return FindX(X,bst->Right);
else if(X<bst->Data) //位于左子樹
return FindX(X,bst->Left);
else
return bst;
}
}
/*
二叉搜索樹刪除指定元素阅畴,并返回二叉樹指針
刪除葉節(jié)點:直接刪除,并修改其父節(jié)點指針為NULL
刪除節(jié)點只有一個孩子節(jié)點:
將其父節(jié)點的指針指向要刪除的節(jié)點的孩子節(jié)點
刪除節(jié)點有兩個孩子節(jié)點:
用另一個節(jié)點替代被刪除節(jié)點(右子樹的最小元素或者左子樹的最大元素)
*/
BinTree DeleteX(ElementType X,BinTree bst)
{
BinTree temp;
if(!bst) printf("Not Find X\n");
else if(X<bst->Data) //位于左子樹
bst->Left=DeleteX(X,bst->Left);
else if(X>bst->Data) //位于右子樹
bst->Right=DeleteX(X,bst->Right);
else //要刪除的點
if(bst->Left&&bst->Right) { //左右節(jié)點均存在
temp=FindMaxNode(bst);
bst->Data=temp->Data;
bst->Right=DeleteX(bst->Data,bst->Right);
}else{ //小于等于一個節(jié)點
temp=bst;
if(!bst->Left)
bst=bst->Right;
else if(!bst->Right)
bst=bst->Left;
free(temp);
}
return bst;
}
/* 輸出二叉樹 */
void PreOrderTraversal(BinTree bst)
{
if(bst){
printf("%d ", bst->Data);
PreOrderTraversal(bst->Left);
PreOrderTraversal(bst->Right);
}
}