首页 > 代码库 > 【数据结构第四周】树知识点整理（下）【二叉搜索树】
【数据结构第四周】树知识点整理（下）【二叉搜索树】
二叉搜索树
（1）定义
二叉搜索树（Binary Search Tree），也称二叉排序树或二叉查找树
一棵二叉树，可以为空；如果不为空，满足以下性质：
a.非空左子树的所有键值小于其根节点的键值
b.非空右子树的所有键值大于其根节点的键值
c.左右子树都是二叉搜索树
（2）相关操作
Position Find( ElementType X, BinTree BST ):从二叉搜索树BST 中查找元素X,返回其所在结点的地址
Position FindMin( BinTree BST ):从二叉搜索树BST中查找并返回 最小元素所在结点的地址
Position FindMax( BinTree BST ) :从二叉搜索树BST中查找并返回 最大元素所在结点的地址
BinTree Insert( ElementType X, BinTree BST )
BinTree Delete( ElementType X, BinTree BST )
（3）查找操作
递归实现
Position Find( ElementType X, BinTree BST ) { if( !BST ) { return NULL; /*查找失败*/ } if( X > BST->Data ) { return Find( X, BST->Right ); /*在右子树中继续查找*/ }else if( X < BST->Data ) { return Find( X, BST->Left ); /*在左子树中继续查找*/ }else /* X == BST->Data */ { return BST; /*查找成功,返回结点的找到结点的地址*/ }}迭代实现
Position IterFind( ElementType X, BinTree BST ) { while( BST ) { if( X > BST->Data ) { BST = BST->Right; /*向右子树中移动,继续查找*/ }else if( X < BST->Data ) { BST = BST->Left; /*向左子树中移动,继续查找*/ } else /* X == BST->Data */ { return BST; /*查找成功,返回结点的找到结点的地址*/ } } return NULL; /*查找失败*/ }查找效率决定于树的高度
（3）查找最大和最小元素
最大元素一定是在树的最右分支的端结点上
最小元素一定是在树的最左分支的端结点上
查找最小元素的递归函数
Position FindMin( BinTree BST ){ if (! BST) { return NULL/*空的二叉搜索树，返回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;}（4）二叉搜索树的插入
BinTree Insert( ElementType X, BinTree BST ) { if( !BST ) { /*若原树为空,生成并返回一个结点的二叉搜索树*/ BST = malloc(sizeof(struct TreeNode)); BST->Data = http://www.mamicode.com/X;>（5）二叉搜索树的删除
分三种情况
a.要删除的是叶子结点，直接删除，并再修改其父结点指针——置为NULL
b.要删除的结点只有一个孩子结点：将其父结点的指针指向要删除结点的孩子结点
c.要删除的结点有左右两棵子树：用另一结点替代被删除的结点：右子树的最小元素或者左子树的最大元素
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 = http://www.mamicode.com/Tmp->Data;>
【数据结构第四周】树知识点整理（下）【二叉搜索树】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。