wordpress播放pdf,网站seo分析工具,万创网做的网站怎么样,门户网站建设合同408答疑 文章目录 三、树形查找二叉排序树#xff08;BST#xff09;二叉排序树中结点值之间的关系二叉树形查找二叉排序树的查找过程示例 向二叉排序树中插入结点插入过程示例 构造二叉排序树的过程构造示例 二叉排序树中删除结点的操作情况一#xff1a;被删除结点是叶结点… 408答疑 文章目录 三、树形查找二叉排序树BST二叉排序树中结点值之间的关系二叉树形查找二叉排序树的查找过程示例 向二叉排序树中插入结点插入过程示例 构造二叉排序树的过程构造示例 二叉排序树中删除结点的操作情况一被删除结点是叶结点情况二被删除结点只有一棵左子树或右子树情况三被删除结点有左、右两棵子树二叉排序树中删除并插入某结点的分析 代码实操结构定义插入操作查找操作删除操作中序遍历 六、参考资料鲍鱼科技课件26王道考研书 三、树形查找
二叉排序树BST
构造二叉排序树的目的并不是排序而是提高查找、插入和删除关键字的速度二叉排序树这种非线性结构也有利于插入和删除的实现。二叉排序树也称二叉查找树或者是一棵空树或者是具有下列特性的二叉树 若左子树非空则左子树上所有结点的值均小于根结点的值。若右子树非空则右子树上所有结点的值均大于根结点的值。左、右子树也分别是一棵二叉排序树。
二叉排序树中结点值之间的关系
根据二叉排序树的定义左子树结点值 根结点值 右子树结点值因此对二叉排序树进行中序遍历可以得到一个递增的有序序列。如下图所示二叉排序树的中序遍历序列为 123468。 二叉树形查找
二叉树形查找是以二叉排序树BST为基础进行查找并演化出相应的平衡树AVL和红黑树RB。除了掌握基础的查找还需掌握平衡树的平衡调整过程。
二叉排序树的查找过程
二叉排序树的查找是从根结点开始沿某个分支逐层向下比较的过程。若二叉排序树非空先将给定值与根结点的关键字比较若相等则查找成功若不等若小于根结点的关键字则在根结点的左子树上查找否则在根结点的右子树上查找。这显然是一个递归的过程。
示例
如下图中查找值为 4 的结点。首先 4 与根结点 6 比较。由于 4 小于 6所以在根结点 6 的左子树中继续查找。由于 4 大于 2所以在结点 2 的右子树中查找查找成功。 向二叉排序树中插入结点
二叉排序树作为一种动态树表其特点是树的结构通常不是一次生成的而是在查找过程中当树中不存在关键字值等于给定值的结点时再进行插入的。
插入过程
若原二叉排序树为空则直接插入否则若关键字 k k k 小于根结点值则插入到左子树若关键字 k k k 大于根结点值则插入到右子树。插入的结点一定是一个新添加的叶结点且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。
示例
下图展示了在一棵二叉排序树中依次插入结点 28 和结点 58 的过程虚线表示的边是其查找的路径。 构造二叉排序树的过程
从一棵空树出发依次输入元素将它们插入二叉排序树中的合适位置。设查找的关键字序列为 {45, 24, 53, 45, 12, 24}则生成的二叉排序树如下图所示。
构造示例 每一步都是根据关键字与当前树中结点的比较结果决定插入的位置。
二叉排序树中删除结点的操作
在二叉排序树中删除一个结点时不能简单地删除该结点及其所有子结点而是需要重新链接因删除结点而断开的二叉链表确保二叉排序树的性质不丢失。删除操作的实现过程按以下三种情况来处理
情况一被删除结点是叶结点
若被删除结点 z z z 是叶结点则直接删除不会破坏二叉排序树的性质。 情况二被删除结点只有一棵左子树或右子树
若结点 z z z 只有一棵左子树或右子树则让 z z z 的子树成为 z z z 父结点的子树替代 z z z 的位置。 情况三被删除结点有左、右两棵子树
若结点 z z z 有左、右两棵子树则令 z z z 的直接后继或直接前驱替代 z z z然后从二叉排序树中删去这个直接后继或直接前驱这样就转变成了第一或第二种情况。 二叉排序树中删除并插入某结点的分析
若在二叉排序树中删除并插入某结点得到的二叉排序树是否和原来的相同
不一定。这个问题需要考虑删除和插入操作对树结构的影响以及这些操作是否能够恢复到原始的树结构。具体分析可能涉及到树的平衡性、结点的相对位置以及操作的顺序等因素。
代码实操
结构定义
定义二叉排序树的结点结构体 BSTNode包含数据域 data指向左子树的指针 left 和指向右子树的指针 right。
typedef struct BSTNode {ElemType data;struct BSTNode *left;struct BSTNode *right;
} BSTNode, *BSTRoot;插入操作
在二叉排序树中插入值 x递归地找到正确的位置插入新结点。
bool insertBST(BSTNode *t, int x) {if (t NULL) {t (BSTNode*)malloc(sizeof(BSTNode));t-data x;t-left t-right NULL;return true; // 插入成功}if (x t-data)return false; // 插入失败if (x t-data)insertBST(t-left, x);elseinsertBST(t-right, x);return true;
}查找操作
在二叉排序树中查找关键字 key递归地遍历树直到找到或到达叶子结点。
BSTNode* searchBST(BSTNode *t, int key) {if (t NULL || t-data key)return t;if (key t-data)return searchBST(t-left, key);else return searchBST(t-right, key);
}删除操作
删除二叉排序树中关键字为 key 的结点处理三种情况无子结点、一个子结点、两个子结点。
bool removeBST(BSTNode *t, int key) {if (t NULL)return false; // 删除失败if (key t-data)removeBST(t-left, key);else if (key t-data)removeBST(t-right, key);else {BSTNode *p NULL;if (t-left ! NULL t-right ! NULL) {p t-left;while (p-right ! NULL)p p-right;t-data p-data;removeBST(t-left, p-data);} else {BSTNode *child (t-left ! NULL) ? t-left : t-right;p t;t child;free(p);}}return true;
}中序遍历
对二叉排序树进行中序遍历输出有序序列。
void sortBST(BSTNode *t) {if (t ! NULL) {sortBST(t-left);printf(%d , t-data);sortBST(t-right);}
}六、参考资料
鲍鱼科技课件
b站免费王道课后题讲解:
网课全程班:
26王道考研书
