旅游网站排行榜前十名官网,销售类网站模板,产品彩页模板,义乌哪里有学做网站的#x1f525;博客主页#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 二叉搜索树的概述 2.0 二叉搜索树的成员变量及其构造方法 3.0 实现二叉树的核心接口 3.1 实现二叉搜索树 - 获取值 get(int key) 3.2 实现二叉搜索树 - 获取最小… 博客主页 【小扳_-CSDN博客】 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 二叉搜索树的概述 2.0 二叉搜索树的成员变量及其构造方法 3.0 实现二叉树的核心接口 3.1 实现二叉搜索树 - 获取值 get(int key) 3.2 实现二叉搜索树 - 获取最小的关键字 min(BinaryNode node) 3.3 实现二叉搜索树 - 获取最大的关键字 max(BinaryNode node) 3.4 实现二叉搜索树 - 增、更新 put( int key, Object value) 3.5 实现二叉搜索树 - 查找关键字的后驱节点 successor(int key) 3.6 实现二叉搜索树 - 查找关键字的前驱节点 predecessor(int key) 3.7 实现二叉搜索树 - 删除关键字节点 delete(int key) 3.8 实现二叉搜索树 - 查找范围小于关键字的节点值 less(int key) 3.9 实现二叉搜索树 - 查找范围大于关键字的节点值 greater(int key) 4.0 实现二叉搜索树 - 查找范围大于 k1 且小于 k2 关键字的节点值 between(int k1, int k2) 5.0 实现二叉搜索树核心方法的完整代码 1.0 二叉搜索树的概述 二叉搜索树是一种数据结构用于存储数据并支持快速的插入、删除和搜索操作。它是一种树形结构。 它具有以下特点 - 每个节点最多有两个子节点分别称为左子节点和右子节点。 - 对于每个节点其左子节点的值小于该节点的值右子节点的值大于该节点的值。 - 中序遍历二叉搜索树可以得到有序的元素序列。 由于其特性二叉搜索树在插入、删除和搜索操作上具有较高的效率。在平均情况下这些操作的时间复杂度为 O(log n)其中 n 为树中节点的数量。然而如果树的结构不平衡最坏情况下这些操作的时间复杂度可能会达到 O(n)。由于其高效的搜索特性二叉搜索树常被用于实现关联数组和集合等数据结构。然而为了避免树的结构不平衡导致性能下降人们也发展了平衡二叉搜索树如红黑树、AVL树等变种。 2.0 二叉搜索树的成员变量及其构造方法 外部类成员变量有根节点、节点类内部类。 外部类构造方法默认的构造方法对外公开二叉搜索树的核心方法。 节点类的成员变量有 - key 关键字相对比一般的二叉树二叉搜索树可以明显提高增删查改的效率原因在于关键字可以根据比较两个关键字的大小进行操作。 - value 值作用则为存放值。 - left 链接左节点。 - right链接右节点。 节点类的构造方法 带两个参数的构造方法参数为 key 、value 带四个参数的构造方法参数为 key 、value 、left 、right
代码如下 public class BinaryTree {BinaryNode root null;static class BinaryNode {int key;Object value;BinaryNode left;BinaryNode right;public BinaryNode(int kty, Object value) {this.key kty;this.value value;}public BinaryNode(int key, Object value, BinaryNode left, BinaryNode right) {this.key key;this.value value;this.left left;this.right right;}}} 补充二叉搜索树在增、删、查、改的效率高的原因 二叉搜索树的高效性与其关键字的特性密切相关。二叉搜索树的关键特性是对于每个节点其左子节点的值小于该节点的值右子节点的值大于该节点的值。这种特性使得在二叉搜索树中进行搜索、插入和删除操作时可以通过比较关键字的大小来快速定位目标节点从而实现高效的操作。在平均情况下这些操作的时间复杂度为 O(log n)其中 n 为树中节点的数量。因此关键字的有序性是二叉搜索树能够实现高效操作的关键原因之一。 3.0 实现二叉树的核心接口
public interface BinarySearchTreeInterface {/***查找 key 对应的 value*/Object get(int key);/*** 查找最小关键字对应值*/Object min();/*** 查找最大关键字对应值*/Object max();/*** 存储关键字与对应值*/void put(int key, Object value);/*** 查找关键字的后驱*/Object successor(int key);/*** 查找关键字的前驱*/Object predecessor(int key);/*** 根据关键字删除*/Object delete(int key);
} 3.1 实现二叉搜索树 - 获取值 get(int key) 实现思路为从根节点开始先判断当前的节点 p.key 与 key 进行比较若 p.key key则向左子树下潜 p p.left 若 p.key key 则向右子树下潜 p p.right 若 p.key key 则找到到了关键字返回该节点的值 p.value 。按这样的规则一直循环下去直到 p null 退出循环则说明没有找到对应的节点则返回 null 。
代码如下 Overridepublic Object get(int key) {if (root null) {return null;}BinaryNode p root;while(p ! null) {if (p.key key) {p p.left;}else if (p.key key) {p p.right;}else {return p.value;}}return null;} 若 root 为 null 则不需要再进行下去了直接结束。 3.2 实现二叉搜索树 - 获取最小的关键字 min(BinaryNode node) 实现思路在某一个树中需要得到最小的关键字由根据数据结构的特点最小的关键字在数的最左边简单来说一直向左子树遍历下去直到 p.left null 时则该 p 节点就是最小的关键字了。然后找到了最小的节点返回该节点的值即可。
代码如下 非递归实现 Overridepublic Object min() {if (root null) {return null;}BinaryNode p root;while(p.left ! null) {p p.left;}return p.value;}//重载了一个方法带参数的方法。public Object min(BinaryNode node) {if (node null) {return null;}BinaryNode p node;while (p.left ! null) {p p.left;}return p.value;} 递归实现 //使用递归实现找最小关键字public Object minRecursion() {return doMin(root);}private Object doMin(BinaryNode node) {if (node null) {return null;}if (node.left null) {return node.value;}return doMin(node.left);} 3.3 实现二叉搜索树 - 获取最大的关键字 max(BinaryNode node) 实现思路为在某一个树中需要得到最大的关键字由根据数据结构的特点最大的关键字在数的最右边简单来说一直向右子树遍历下去直到 p.right null 时则该 p 节点就是最大的关键字了。然后找到了最大的节点返回该节点的值即可。
代码如下 非递归实现 Overridepublic Object max() {if (root null) {return null;}BinaryNode p root;while(p.right ! null) {p p.right;}return p.value;}//重载了一个带参数的方法public Object max(BinaryNode node) {if (node null) {return null;}BinaryNode p node;while (p.right ! null) {p p.right;}return p.value;} 递归实现 //使用递归实现找最大关键字public Object maxRecursion() {return doMax(root);}private Object doMax(BinaryNode node) {if (node null) {return null;}if (node.right null) {return node.value;}return doMax(node.right);} 3.4 实现二叉搜索树 - 增、更新 put( int key, Object value) 实现思路为在二叉搜索树中先试着查找是否存在与 key 对应的节点 p.key 。若找到了则为更新该值 p.value value 即可。若找不到则需要新增该关键字节点。 具体来分析如何新增关键字先定义 BinaryNode parent 、 BinaryNode pp 指针在去比较 key 之前先让 parent 指向 p 。最后循环结束后 p null 对于 parent 来说此时正指着 p 节点的双亲节点。 接着创建一个新的节点BinaryNode newNode new BinaryNode(key, value) 则此时还需要考虑的是该新的节点该连接到 parent 的左孩子还是右孩子 需要比较 parent.key 与 newNode.key 的大小即可若 parent.key newNode.key则链接到 parent.left 处若 prent.key newNode.key 则连接到 parent.right 处。
代码如下 Overridepublic void put(int key, Object value) {if (root null) {root new BinaryNode(key,value);return;}BinaryNode p root;BinaryNode parent null;while (p ! null) {parent p;if (p.key key) {p p.left;} else if (p.key key) {p p.right;}else {p.value value;return;}}//该树没有该关键字因此需要新建节点对象BinaryNode newNode new BinaryNode(key,value);if (newNode.key parent.key) {parent.left newNode;}else {parent.right newNode;}} 3.5 实现二叉搜索树 - 查找关键字的后驱节点 successor(int key) 具体实现思路为先遍历找到该关键字的节点若找不到则返回 null 若找到了判断以下的两种情况第一种情况该节点有右子树则该关键字的后驱为右子树的最小关键字第二种情况该节点没有右子树则该关键字的后驱为从右向左而来的祖宗节点。最后返回该后驱节点的值
代码如下 Overridepublic Object successor(int key) {if (root null) {return null;}//先找到该关键字节点BinaryNode p root;BinaryNode sParent null;while (p ! null) {if (p.key key) {sParent p;p p.left;} else if (p.key key) {p p.right;}else {break;}}//没有找到关键字的情况if (p null) {return null;}//情况一:该节点存在右子树,则该后继为右子树的最小关键字if (p.right ! null) {return min(p.right);}//情况二:该节点不存在右子树那么该后继就需要到祖宗从右向左的节点if (sParent null) {//可能不存在后继节点,比如最大关键字的节点就没有后继节点了return null;}return sParent.value;} 3.6 实现二叉搜索树 - 查找关键字的前驱节点 predecessor(int key) 具体实现思路为先对该二叉树进行遍历寻找 key 的节点若遍历结束还没找到则返回 null 若找到了需要判断以下两种情况 第一种情况该节点有左子树则该前驱节点为该左子树的最大关键字节点。 第二种情况该节点没有左子树则该前驱节点为从左向右而来的祖宗节点。 最后返回该前驱节点的值。
代码如下 Overridepublic Object predecessor(int key) {if (root null) {return null;}BinaryNode p root;BinaryNode sParent null;while (p ! null) {if (p.key key) {p p.left;} else if (p.key key) {sParent p;p p.right;}else {break;}}if (p null) {return null;}//情况一:存在左子树则该前任就为左子树的最大关键字节点if (p.left ! null) {return max(p.left);}//情况二:不存在左子树则该前任为从祖宗自左向右而来的节点if (sParent null) {return null;}return sParent.value;} 3.7 实现二叉搜索树 - 删除关键字节点 delete(int key) 具体实现思路为先遍历二叉树查找该关键字节点。若遍历结束了还没有找到则返回 null 若找到了则需要以下四种情况 第一种情况找到该删除的节点只有左子树。则直接让该左子树 托付 给删除节点的双亲节点这就删除了该节点了。至于左子树是链接到双亲节点的左边还有右边这个问题根据该数据结构的特点由该删除节点来决定。若删除的节点之前是链接该双亲节点的左边则左子树也是链接到该双亲节点的左边若删除的节点之前是链接该双亲节点的右边则左子树也是链接到该双亲节点的右边。 第二种情况找到该删除的节点只有右子树。则直接让该右子树 托付 给删除节点的双亲节点这就删除了该节点了。至于右子树是链接到双亲节点的左边还有右边这个问题根据该数据结构的特点由该删除节点来决定。若删除的节点之前是链接该双亲节点的左边则右子树也是链接到该双亲节点的左边若删除的节点之前是链接该双亲节点的右边则右子树也是链接到该双亲节点的右边。 第三种情况找到该删除节点都没有左右子树。该情况可以归并到以上两种情况的任意一种处理均可。 第四种情况找到该删除节点都有左右子树。分两步第一步先找后继节点来替换删除节点找该后继节点直接到删除节点的右子树中找最小的关键字节点即可。第二步需要先将后继节点的右子树处理好需要将该右子树交给替换节点的双亲节点链接。还需要判断两种情况第一种情况若删除节点与替换节点是紧挨着的对替换节点的右子树无需要求只对左子树重新赋值若删除节点与替换节点不是紧挨着的关系对替换节点的左右子树都要重新赋值。
代码如下 Overridepublic Object delete(int key) {if (root null) {return null;}BinaryNode p root;BinaryNode parent null;while (p ! null) {if (p.key key) {parent p;p p.left;} else if (p.key key) {parent p;p p.right;}else {break;}}//没有找到该关键字的节点if (p null) {return null;}//情况一、二、三:只有左子树或者右子树或者都没有if (p.right null) {shift(parent,p,p.left);} else if (p.left null) {shift(parent,p,p.right);}else {//情况四:有左右子树//替换节点采用删除节点的后继节点//先看被删的节点与替换的节点是否为紧挨在一起BinaryNode s p.right;BinaryNode sParent p;while (s.left ! null) {sParent s;s s.left;}if (sParent ! p) {//说明没有紧挨在一起则需要将替换节点的右子树进行处理shift(sParent,s,s.right);s.right p.right;}shift(parent,p,s);s.left p.left;}return p.value;}private void shift(BinaryNode parent, BinaryNode delete, BinaryNode next) {if (parent null) {root next;} else if (parent.left delete) {parent.left next;}else if (parent.right delete){parent.right next;}} 为了方便将删除节点与替换节点之间的替换操作单独成一个方法出来。 递归实现删除关键字 key 节点同理也是细分为以上描述的四种情况。
代码如下 //使用递归实现删除关键字节点public BinaryNode deleteRecursion(BinaryNode node , int key) {if (node null) {return null;}if (node.key key) {node.left deleteRecursion(node.left,key);return node;} else if (node.key key) {node.right deleteRecursion(node.right,key);return node;}else {if (node.right null) {return node.left;} else if (node.left null) {return node.right;}else {BinaryNode s node.right;while (s.left ! null) {s s.left;}s.right deleteRecursion(node.right,s.key);s.left node.left;return s;}}} 3.8 实现二叉搜索树 - 查找范围小于关键字的节点值 less(int key) 具体实现思路为利用中序遍历来遍历每一个节点的 key 若小于 key 的节点直接放到数组容器中若大于 key 的可以直接退出循环。最后返回该数组容器即可。
代码如下 //找 key 的所有 valuepublic ListObject less(int key) {if (root null) {return null;}ArrayListObject result new ArrayList();BinaryNode p root;StackBinaryNode stack new Stack();while (p ! null || !stack.isEmpty()) {if (p ! null) {stack.push(p);p p.left;}else {BinaryNode pop stack.pop();if (pop.key key) {result.add(pop.value);}else {break;}p pop.right;}}return result;} 3.9 实现二叉搜索树 - 查找范围大于关键字的节点值 greater(int key) 具体实现思路利用中序遍历来遍历每一个节点的 key 若大于 key 的节点直接放到数组容器中。
代码如下 //找 key 的所有 valuepublic ListObject greater(int key) {if (root null) {return null;}ArrayListObject result new ArrayList();StackBinaryNode stack new Stack();BinaryNode p root;while (p ! null || !stack.isEmpty()) {if (p ! null) {stack.push(p);p p.left;}else {BinaryNode pop stack.pop();if (pop.key key) {result.add(pop.value);}p pop.right;}}return result;} 该方法的改进遍历方向进行调整先从右子树开始再访问根节点最后才到左子树。因此只要小于 key 的关键字节点直接退出循环。
代码如下 //改进思路:遍历方向进行调整先从右子树开始再访问根节点最后才到左子树public ListObject greater1(int key) {if (root null) {return null;}ArrayListObject result new ArrayList();StackBinaryNode stack new Stack();BinaryNode p root;while (p ! null || !stack.isEmpty()) {if (p ! null ) {stack.push(p);p p.right;}else {BinaryNode pop stack.pop();if (pop.key key) {result.add(pop.value);}else {break;}p pop.left;}}return result;} 4.0 实现二叉搜索树 - 查找范围大于 k1 且小于 k2 关键字的节点值 between(int k1, int k2) 实现思路跟以上的思路没有什么区别唯一需要注意的是当前节点的 key k2 则可以退出循环了。
代码如下 //找到 k1 且 k2 的所有valuepublic ListObject between(int k1, int k2) {if (root null) {return null;}ArrayListObject result new ArrayList();StackBinaryNode stack new Stack();BinaryNode p root;while(p ! null || !stack.isEmpty()) {if (p ! null) {stack.push(p);p p.left;}else {BinaryNode pop stack.pop();if (pop.key k1 pop.key k2) {result.add(pop.value);} else if (pop.key k2) {break;}p pop.right;}}return result;} 5.0 实现二叉搜索树核心方法的完整代码 实现接口代码 import java.util.ArrayList;import java.util.List;
import java.util.Stack;public class BinaryTree implements BinarySearchTreeInterface{BinaryNode root null;static class BinaryNode {int key;Object value;BinaryNode left;BinaryNode right;public BinaryNode(int kty, Object value) {this.key kty;this.value value;}public BinaryNode(int key, Object value, BinaryNode left, BinaryNode right) {this.key key;this.value value;this.left left;this.right right;}}Overridepublic Object get(int key) {if (root null) {return null;}BinaryNode p root;while(p ! null) {if (p.key key) {p p.left;}else if (p.key key) {p p.right;}else {return p.value;}}return null;}Overridepublic Object min() {if (root null) {return null;}BinaryNode p root;while(p.left ! null) {p p.left;}return p.value;}public Object min(BinaryNode node) {if (node null) {return null;}BinaryNode p node;while (p.left ! null) {p p.left;}return p.value;}//使用递归实现找最小关键字public Object minRecursion() {return doMin(root);}private Object doMin(BinaryNode node) {if (node null) {return null;}if (node.left null) {return node.value;}return doMin(node.left);}Overridepublic Object max() {if (root null) {return null;}BinaryNode p root;while(p.right ! null) {p p.right;}return p.value;}public Object max(BinaryNode node) {if (node null) {return null;}BinaryNode p node;while (p.right ! null) {p p.right;}return p.value;}//使用递归实现找最大关键字public Object maxRecursion() {return doMax(root);}private Object doMax(BinaryNode node) {if (node null) {return null;}if (node.right null) {return node.value;}return doMax(node.right);}Overridepublic void put(int key, Object value) {if (root null) {root new BinaryNode(key,value);return;}BinaryNode p root;BinaryNode parent null;while (p ! null) {parent p;if (p.key key) {p p.left;} else if (p.key key) {p p.right;}else {p.value value;return;}}//该树没有该关键字因此需要新建节点对象BinaryNode newNode new BinaryNode(key,value);if (newNode.key parent.key) {parent.left newNode;}else {parent.right newNode;}}Overridepublic Object successor(int key) {if (root null) {return null;}//先找到该关键字节点BinaryNode p root;BinaryNode sParent null;while (p ! null) {if (p.key key) {sParent p;p p.left;} else if (p.key key) {p p.right;}else {break;}}//没有找到关键字的情况if (p null) {return null;}//情况一:该节点存在右子树,则该后继为右子树的最小关键字if (p.right ! null) {return min(p.right);}//情况二:该节点不存在右子树那么该后继就需要到祖宗从右向左的节点if (sParent null) {//可能不存在后继节点,比如最大关键字的节点就没有后继节点了return null;}return sParent.value;}Overridepublic Object predecessor(int key) {if (root null) {return null;}BinaryNode p root;BinaryNode sParent null;while (p ! null) {if (p.key key) {p p.left;} else if (p.key key) {sParent p;p p.right;}else {break;}}if (p null) {return null;}//情况一:存在左子树则该前任就为左子树的最大关键字节点if (p.left ! null) {return max(p.left);}//情况二:不存在左子树则该前任为从祖宗自左向右而来的节点if (sParent null) {return null;}return sParent.value;}Overridepublic Object delete(int key) {if (root null) {return null;}BinaryNode p root;BinaryNode parent null;while (p ! null) {if (p.key key) {parent p;p p.left;} else if (p.key key) {parent p;p p.right;}else {break;}}//没有找到该关键字的节点if (p null) {return null;}//情况一、二、三:只有左子树或者右子树或者都没有if (p.right null) {shift(parent,p,p.left);} else if (p.left null) {shift(parent,p,p.right);}else {//情况四:有左右子树//替换节点采用删除节点的后继节点//先看被删的节点与替换的节点是否为紧挨在一起BinaryNode s p.right;BinaryNode sParent p;while (s.left ! null) {sParent s;s s.left;}if (sParent ! p) {//说明没有紧挨在一起则需要将替换节点的右子树进行处理shift(sParent,s,s.right);s.right p.right;}shift(parent,p,s);s.left p.left;}return p.value;}private void shift(BinaryNode parent, BinaryNode delete, BinaryNode next) {if (parent null) {root next;} else if (parent.left delete) {parent.left next;}else if (parent.right delete){parent.right next;}}//使用递归实现删除关键字节点public BinaryNode deleteRecursion(BinaryNode node , int key) {if (node null) {return null;}if (node.key key) {node.left deleteRecursion(node.left,key);return node;} else if (node.key key) {node.right deleteRecursion(node.right,key);return node;}else {if (node.right null) {return node.left;} else if (node.left null) {return node.right;}else {BinaryNode s node.right;while (s.left ! null) {s s.left;}s.right deleteRecursion(node.right,s.key);s.left node.left;return s;}}}//找 key 的所有 valuepublic ListObject less(int key) {if (root null) {return null;}ArrayListObject result new ArrayList();BinaryNode p root;StackBinaryNode stack new Stack();while (p ! null || !stack.isEmpty()) {if (p ! null) {stack.push(p);p p.left;}else {BinaryNode pop stack.pop();if (pop.key key) {result.add(pop.value);}else {break;}p pop.right;}}return result;}//找 key 的所有 valuepublic ListObject greater(int key) {if (root null) {return null;}ArrayListObject result new ArrayList();StackBinaryNode stack new Stack();BinaryNode p root;while (p ! null || !stack.isEmpty()) {if (p ! null) {stack.push(p);p p.left;}else {BinaryNode pop stack.pop();if (pop.key key) {result.add(pop.value);}p pop.right;}}return result;}//改进思路:遍历方向进行调整先从右子树开始再访问根节点最后才到左子树public ListObject greater1(int key) {if (root null) {return null;}ArrayListObject result new ArrayList();StackBinaryNode stack new Stack();BinaryNode p root;while (p ! null || !stack.isEmpty()) {if (p ! null ) {stack.push(p);p p.right;}else {BinaryNode pop stack.pop();if (pop.key key) {result.add(pop.value);}else {break;}p pop.left;}}return result;}//找到 k1 且 k2 的所有valuepublic ListObject between(int k1, int k2) {if (root null) {return null;}ArrayListObject result new ArrayList();StackBinaryNode stack new Stack();BinaryNode p root;while(p ! null || !stack.isEmpty()) {if (p ! null) {stack.push(p);p p.left;}else {BinaryNode pop stack.pop();if (pop.key k1 pop.key k2) {result.add(pop.value);} else if (pop.key k2) {break;}p pop.right;}}return result;}}
