二叉查找树查找,插入,删除算法详解(C语言实现,注释最全,单步调试通过)
二叉查找树的定义
二叉排序树 (Binary Sort Tree) 又称二叉查找树,它是一种对排序和查找都很有用的特殊二叉树。
二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: (1) 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2) 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3) 它的左、 右子树也分别为二叉排序树。
二叉排序树是递归定义的。 由定义可以得出二叉排序树的一个重要性质:中序遍历一棵二叉 树时可以得到一个结点值递增的有序序列。
二叉查找树的实现
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
#define ElemType int
#define KeyType int
typedef struct _BinaryNode
{
ElemType data;
struct _BinaryNode *lchild;
struct _BinaryNode *rchild;
}BinaryNode,*BinaryTree;
int SearchBST(BinaryTree Node,KeyType KeyData,BinaryTree FatherNode,BinaryTree *FoundNode,BinaryTree *FatherOfFoundNode)
{
if(!Node)
{
*FatherOfFoundNode = FatherNode;
*FoundNode = NULL;
return false;
}
if(KeyData == Node->data)
{
*FoundNode = Node;
*FatherOfFoundNode = FatherNode;
return true;
}
else if(KeyData < Node->data)
{
return SearchBST(Node->lchild, KeyData, Node, FoundNode,FatherOfFoundNode);
}
else
{
return SearchBST(Node->rchild, KeyData, Node, FoundNode,FatherOfFoundNode);
}
}
BinaryTree FindBSTMin(BinaryTree BinaryNode)
{
if(BinaryNode == NULL)
{
return NULL;
}
else
{
if(BinaryNode->lchild == NULL)
{
return BinaryNode;
}
else
{
return FindBSTMin(BinaryNode->lchild);
}
}
}
BinaryTree FindBSTMax(BinaryTree BinaryNode)
{
if(BinaryNode == NULL)
{
return NULL;
}
else
{
if(BinaryNode->rchild == NULL)
{
return BinaryNode;
}
else
{
return FindBSTMax(BinaryNode->rchild);
}
}
}
int InsertBST(BinaryTree *Tree,ElemType Data)
{
BinaryTree FoundNode = NULL;
BinaryTree FatherOfFoundNode = NULL;
if(!SearchBST(*Tree,Data,NULL,&FoundNode,&FatherOfFoundNode))
{
BinaryTree InsertNode = (BinaryTree)malloc(sizeof(BinaryNode));
InsertNode->data = Data;
InsertNode->lchild = NULL;
InsertNode->rchild = NULL;
if(!FatherOfFoundNode)
{
*Tree = InsertNode;
}
else if(Data < FatherOfFoundNode->data)
{
FatherOfFoundNode->lchild = InsertNode;
}
else
{
FatherOfFoundNode->rchild = InsertNode;
}
return true;
}
else
{
return false;
}
}
int DeleteNode(BinaryTree *DeleteNode,BinaryTree *FatherOfDeleteNode)
{
BinaryTree FatherOfPrecursorForDeleteNode = NULL;
BinaryTree PrecursorForDeleteNode = NULL;
if (!(*DeleteNode)->lchild && !(*DeleteNode)->rchild) {
if((*FatherOfDeleteNode)->lchild == *DeleteNode)
{
(*FatherOfDeleteNode)->lchild = NULL;
}
else
{
(*FatherOfDeleteNode)->rchild = NULL;
}
free(*DeleteNode);
*DeleteNode = NULL;
}
else if(!(*DeleteNode)->rchild)
{
if((*FatherOfDeleteNode)->lchild == *DeleteNode)
{
(*FatherOfDeleteNode)->lchild = (*DeleteNode)->lchild;
}
else
{
(*FatherOfDeleteNode)->rchild = (*DeleteNode)->lchild;
}
free(*DeleteNode);
*DeleteNode = NULL;
}
else if(!(*DeleteNode)->lchild)
{
if((*FatherOfDeleteNode)->rchild == *DeleteNode)
{
(*FatherOfDeleteNode)->rchild = (*DeleteNode)->rchild;
}
else
{
(*FatherOfDeleteNode)->lchild = (*DeleteNode)->rchild;
}
free(*DeleteNode);
*DeleteNode = NULL;
}
else
{
FatherOfPrecursorForDeleteNode = *DeleteNode;
PrecursorForDeleteNode = (*DeleteNode)->lchild;
while (PrecursorForDeleteNode->rchild)
{
FatherOfPrecursorForDeleteNode = PrecursorForDeleteNode;
PrecursorForDeleteNode = PrecursorForDeleteNode->rchild;
}
(*DeleteNode)->data = PrecursorForDeleteNode->data;
if (FatherOfPrecursorForDeleteNode == *DeleteNode) {
(*DeleteNode)->lchild = PrecursorForDeleteNode->lchild;
}
else {
FatherOfPrecursorForDeleteNode->rchild = PrecursorForDeleteNode->lchild;
}
free(PrecursorForDeleteNode);
PrecursorForDeleteNode = NULL;
}
return true;
}
BinaryTree DeleteBST(BinaryTree BinaryNode)
{
if(BinaryNode != NULL)
{
DeleteBST(BinaryNode->lchild);
DeleteBST(BinaryNode->rchild);
free(BinaryNode);
}
return NULL;
}
int main(void)
{
int i;
int Squence2[] = {8, 4, 10, 2, 6, 12, 5};
BinaryTree Tree = NULL;
for (i = 0; i < sizeof(Squence2)/sizeof(Squence2[0]);++i)
{
int ReturnCode = InsertBST(&Tree, Squence2[i]);
printf("insert %d result %d\r\n", Squence2[i], ReturnCode);
}
BinaryTree FoundNode = NULL;
BinaryTree FatherOfFoundNode = NULL;
if(SearchBST(Tree,8,NULL,&FoundNode,&FatherOfFoundNode))
{
DeleteNode(&FoundNode,&FatherOfFoundNode);
}
}
|