二叉搜索树

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树

1.非空左子树的所有键值小于其根结点的键值 2.非空右子树的所有键值大于其根结点的键值。 3.左、右子树都是二叉搜索树。

二叉搜索树操作的特别函数

1.二叉搜索树的查找操作：Find

查找从根结点开始，如果树为空，返回NULL 若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：

①若X小于根结点键值，只需在左子树中继续搜索； ②如果X大于根结点的键值，在右子树中进行继续搜索； ③若两者比较结果是相等，搜索完成，返回指向此结点的指针。

//递归 Position Find(ElementType x, BinTree BST) { if (!BST) return NULL; if (x > BST->Data) return Find(x, BST->Right); else if (x < BST->Date) return Find(x, BST->Left); else return BST; } //迭代 Position Find(ElementType x, BinTree BST) { while (BST) { if (x > BST->Data) BST = BST->Right; else if (x < BST->Data) BST = BST->Left; else return BST; } return NULL; }

2.查找最大和最小元素

1.最大元素一定是在树的最右分枝的端结点上 2.最小元素一定是在树的最左分枝的端结点上

Position FindMin(BinTree BST) { if (!BST) return NULL; else if (!BST->Left) return BST; else return FindMin(BST->Left); } Position FindMax(BinTree BST) { if (BST) while (BST->Right) BST = BST->Right; return BST; }

3.二叉搜索树的插入

BinTree Insert(ElementType x, BinTree BST) { if (!BST) { /*若原树为空，生成并返回一个结点的二叉搜索树*/ BST = malloc(sizeof(struct TreeNode)); BST->Data = x; BST->Left = BST->Right = NULL; } else if (x < BST->Data) /*递归插入左子树*/ BST->Left = Insert(x, BST->Left); else if (x > BST->Data) /*递归插入右子树*/ BST->Right = Insert(x, BST->Right); /* else X已经存在，什么都不做 */ return BST; }

4.二叉搜索树的删除

①要删除的是叶结点：直接删除，并再修改其父结点指针—置为NULL ②要删除的结点只有一个孩子结点:将其父结点的指针指向要删除结点的孩子结点 ③要删除的结点有左、右两棵子树:用另一结点替代被删除结点：右子树的最小元素 或者左子树的最大元素

BinTree Delete(ElementType x, BinTree BST) { Position Tmp; if (!BST) printf("树空"); else if (x < BST->Data) /* 左子树递归删除 */ BST->left = Delete(x, BST->Left); else if (x > BST->Data) /* 右子树递归删除 */ BST->Right = Delete(x, BST->Right); else if (BST->Left && BST->Right) { /*被删除结点有左右两个子结点 */ Tmp = FindMin(BST->Right); /*在右子树中找最小的元素填充删除结点*/ BST->Data = Tmp->Data; /*在删除结点的右子树中删除最小元素*/ BST->Right = Delete(BST->Data, BST->Right); } else {/*被删除结点有一个或无子结点*/ Tmp = BST; if (!BST->Left) /* 有右孩子或无子结点*/ BST = BST->Right; else if (!BST->Right) /*有左孩子或无子结点*/ BST = BST->Left; free(Tmp); } return BST; }