图书馆网站建设教程,河北网站开发,聊城做网站的公司教程,免费网页空间2023二叉搜索树#xff08;Binary Search Tree#xff0c;简称 BST#xff09;是一种数据结构#xff0c;用于存储具有可比较键#xff08;通常是数字或字符串#xff09;的元素
1 结构特点
节点结构#xff1a;每个节点都有一个键和两个子节点#xff08;左子节点和右子…二叉搜索树Binary Search Tree简称 BST是一种数据结构用于存储具有可比较键通常是数字或字符串的元素
1 结构特点
节点结构每个节点都有一个键和两个子节点左子节点和右子节点。排序特性 若左子树不空则左子树上所有节点的值都小于根节点的值 若右子树不空则右子树上所有节点的值都大于根节点的值 左子树和右子树也分别是二叉搜索树。
这样的特性使得二叉搜索树能高效地支持多种查找和动态集合操作。 二叉搜索树有一个重要特性就是他的中序遍历结果一定是有序的
2 二叉搜索树的查找 如果当前节点为空则搜索失败。 否则如果当前节点的值等于要查找的值则直接返回。 否则如果要查找的值比当前节点小就往当前节点的左子树找。如果要查找的值比当前节点值大就往当前节点的右子树找。 3 二叉搜索树的插入
首先找到他需要插入的位置然后再插入 如果当前节点为空直接创建一个新的节点返回。 如果要插入的值比当前节点小就往当前节点的左子树查找插入的位置。 如果要插入的值比当前节点大就往当前节点的右子树查找插入的位置。 4 二叉搜索树的删除
如果删除的是叶子节点则直接删除如果删除的节点只有一个子节点让这个仅有的子节点替代他如果删除的节点有两个子节点就需要考虑删除当前节点后子节点该怎么存放 删除有两种实现方式一种是直接删除需要删除的节点一种是使用移形换位法 直接删除有个缺点就是会导致树严重不平衡AVL 树和红黑树都是移形换位法
4.1 前驱节点和后驱节点
前驱节点对一棵二叉树进行中序遍历遍历后的结果中当前节点的前一个节点为该节点的前驱节点后继节点对一棵二叉树进行中序遍历遍历后的结果中当前节点的后一个节点为该节点的后继节点 当然查找一个节点的前驱节点和后继节点不一定需要打印二叉树的中序遍历结果这么麻烦 一个节点的前驱节点是他左子树中的最大节点这个节点就是他左子树往右一直走下去的节点一个节点的后继节点就是他右子树的最小节点这个节点就是他右子树往左一直走下去的节点
4.2 直接删除
直接删除的缺点就是会严重破坏树的平衡性
4.2.1 方法1让待删除节点的右子节点成为他前驱节点的右子节点 4.2.2 方法2让待删除节点的左子节点成为他后继节点的左子节点
