英文全称:Binary Sort Tree,它满足以下3个特点:
如下图:
二叉排序树,中序遍历输出结果是有序的
新元素被插入之后一定是个叶子节点,如某个key已存在,那么新值覆盖旧值
/** * 添加节点 * @param key * @param data */
public void add (int key, String data) {
/* 1、如果 根节点root为空 则将新增的节点设置为根节点,并返回结束*/
if (root == null) {
root = new Node(key, data);
return;
}
/*2、找到节点要添加的位置*/
Node cur = root; // cur:表示要判断的当前节点。cur从根节点开始判断,因此初始值为root
Node pre = null; // pre表示cur的上个节点 也就是父节点
// 实际上当cur==null时 说明我们已经找到合适的位置了
while (cur != null) {
if (key < cur.key) { // 向左子树寻找
pre = cur;
cur = cur.left;
}else if (key > cur.key) { // 向右子树寻找
pre = cur;
cur = cur.right;
}else { // key == cur.key 则表示当前key已存在
cur.data = data; // 新值覆盖旧值,并返回结束
return;
}
}
// 循环结束 cur为null则表示已经找到了合适的添加位置
/*3、最终判断:应当插入父节点的左边还是右边?*/
if (key < pre.key) // 插入到父节点的左边
pre.left = new Node(key, data);
else // 插入到父节点的右边
pre.right = new Node(key, data);
}
1、拿着待查元素和根节点比较;
2、如果比根节点小,继续在左子树中查找;
3、如果比根节点大,继续在右子树中查找;
4、如果当前元素查找到null也没找到,说明该元素不存在。
非递归方式:
/** * 非递归的搜索 * @param key * @return */
public Node find(int key) {
// cur从根节点开始搜索
Node cur = root;
while (cur != null) {
// 如果当前节点的key与搜索的key值相等 则说明找到了,直接返回当前节点
if (cur.key == key)
return cur;
// 下面是当前节点大于key和小于key的情况(向下搜索)
if (key < cur.key)
cur = cur.left;
else { // key > cur.key
cur = cur.right;
}
}
// 如果走出循环还没找到 则表示已经找到末尾了还没找到
return null;
}
递归方式:
/** * 递归的搜索 * @param node * @param key * @return */
public Node dgFind(Node node, int key) {
// 如果节点为空 则表示已经找到末尾了还没找到
if (node == null)
return null;
// 如果cur.key == key 则表示找到了,直接返回
if (node.key == key)
return node;
// 下面是当前节点大于key和小于key的情况
if (key < node.key)
return dgFind(node.left, key); // 切记这里是return dgFind(xxx, xxx) 不是直接调用dgFind(xxx, xxx)
else // key > node.key
return dgFind(node.right, key);
}
非root节点 (这种情况下再分三种情况)
叶子节点:若删除节点为叶子节点,理论上直接删除即可。但操作上,会找到删除节点的父节点parent,后判断删除节点是parent的左节点还是右节点,最后将parent的左节点或者右节点置null即可
只有一棵子树:若删除节点只有一棵子树,那么就找该节点的父节点parent,判断待删除的节点是parent的左节点还是右节点,最后将parent的左节点或者右节点指向待删除节点的子节点。那么待删除节点就会被回收删除了。
有两棵子树:若删除节点有两棵子树,即左、右节点都存在。那么只需要从待删除的左子树中找到最大节点(也可以是右子树的最小值,都可以),然后用其替换待删除节点的位置。实际操作:将这个最大节点先备份为temp,然后将这个节点从树中删除。然后将temp的左右指针分别指向root的左右节点、再将parent的左指针或者右指针指向temp
root节点,那么parent就为null(这种情况下再分三种情况)
叶子节点:若删除节点为叶子节点。正确操作:直接将root置为null即可
只有一棵子树:若删除节点只有一棵子树。正确操作:直接将待删除节点的子节点设置为root节点即可
有两棵子树:若删除节点有两棵子树。正确操作:从待删除节点的左子树中找到最大节点(也可以是右子树的最小节点),然后用其替换root节点的位置。实际操作:将这个最大节点先备份为temp,然后将这个节点从树中删除。然后将temp的左右指针分别指向root的左右节点。最后将temp设置为root节点
通过上面描述,我们需要封装两个方法。
找到指定key的父节点的方法:public Node findParent(int key)
找寻指定节点下面的的最大节点的方法:public Node searchMax(Node node)
找到指定key父节点的方法:
/** * 返回指定key的父节点 * @param key * @return */
public Node findParent(int key) {
// 如果搜索的key是根节点的key 那么直接返回null 因为root没有父节点
if (key == root.key)
return null;
Node cur = root;
while (cur != null) {
// 如果左节点不为null 且左节点的key与搜索的key相同 怎直接返回当前节点
if (cur.left!=null && cur.left.key==key)
return cur;
// 与上面类似
if (cur.right!=null && cur.right.key==key)
return cur;
// 向下搜索
if (key < cur.key)
cur = cur.left;
if (key > cur.key)
cur = cur.right;
}
// 如果走出循环还没找到 则表示已经找到末尾了还没找到
return null;
}
找寻指定节点下面的的最大节点:
/** * 找寻该节点下面的的最大节点 * @param node * @return */
public Node searchMax(Node node){
// 循环找到最大节点(只要右子节点存在,就移入)
Node target = node;
while(target.right != null){ // 无需递归
target = target.right;
}
// 已到达最大节点
return target;
}
删除主要代码:
/** * 删除指定节点 * @param key * @return */
public boolean delNode(int key) {
/** * 先分两大种情况: * 删除节点为 非root节点 * 删除节点为 root节点 * * 再分三种情况: * 1、删除的节点是叶子节点(左右节点都为null) * 2、删除的节点只有一个子树(左节点为null 或者 右节点为null) * 3、删除的节点有两颗子树(左右节点都不为null) */
// 找到要删除的节点
Node targetNode = find(key);
if (targetNode == null) // 如果node为null 这说明树中不存在指定key的节点,直接返回false
return false;
// 找到要删除节点的父节点
Node parent = findParent(key);
if (parent != null) { // parent不为null,则表示删除节点不是root节点
if (targetNode.left==null && targetNode.right==null) { // 1、删除节点是叶子节点
if (parent.left!=null && parent.left.key == targetNode.key) // 待删除节点是父节点的左节点
parent.left = null;
else // 待删除节点是父节点的右节点
parent.right = null;
}else if (targetNode.left!=null && targetNode.right!=null) { // 3、待删除节点有两棵子树
// 备份一下要替换的节点
Node maxNode = searchMax(targetNode.left);
Node temp = new Node(maxNode.key, maxNode.data);
// 将这个节点从树中删除
delNode(maxNode.key);
// temp节点 的左、右指针指向 待删除节点的左、右节点
temp.left = targetNode.left; temp.right = targetNode.right;
// 父节点的左指针或者右指针指向temp节点, 备份节点彻底替换掉待删除节点
if (parent.left!=null && parent.left.key == targetNode.key)
parent.left = temp;
else
parent.right = temp;
}else { // 2、待删除节点有一颗子树
if (parent.left!=null && parent.left.key == targetNode.key) { // 如果待删除节点是parent的左节点
if (targetNode.left != null) // 若待删除节点唯一存在的子树是左子树
parent.left = targetNode.left;
if (targetNode.right != null) // 若待删除节点唯一存在的子树是右子树
parent.left = targetNode.right;
}else { // 如果待删除节点是parent的右节点
if (targetNode.left != null)
parent.right = targetNode.left;
if (targetNode.right != null)
parent.right = targetNode.right;
}
}
}else { // parent为null,则表示删除节点是root节点
if (targetNode.left==null && targetNode.right==null) {
root = null;
}else if (targetNode.left!=null && targetNode.right!=null) {
Node maxNode = searchMax(targetNode.left);
Node temp = new Node(maxNode.key, maxNode.data);
delNode(maxNode.key);
temp.right = targetNode.right; temp.left = targetNode.left;
// 将这个备份节点设置为root节点
this.root = temp;
}else {
if (targetNode.left != null)
this.root = targetNode.left;
else
this.root = targetNode.right;
}
}
return true;
}
public class BinarySortTreeDemo {
public static void main(String[] args) {
// 创建一个二叉排序树
BinarySortTree BST = new BinarySortTree();
// 并未BST设置一个root节点
Node root = new Node(0, "root");
BST.root = root;
// 手动添加节点
BST.add(3, "z3"); BST.add(5, "z5"); BST.add(8, "z8");
BST.add(2, "z2"); BST.add(2, "z22"); BST.add(9, "z9");
BST.add(7, "z7"); BST.add(66, "z66"); BST.add(52, "z52");
BST.delNode(66);
BST.midOrder(BST.root);
}
}
class Node {
// key 值用来比较、排序
public int key;
public String data;
public Node left = null;
public Node right = null;
public Node(int key, String data) {
this.key = key;
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"key=" + key +
", data='" + data + '\'' +
'}';
}
}
class BinarySortTree {
// 二叉排序树的根节点
public Node root;
/** * 添加节点 * @param key * @param data */
public void add (int key, String data) {
/* 1、如果 根节点root为空 则将新增的节点设置为根节点,并返回结束*/
if (root == null) {
root = new Node(key, data);
return;
}
/*2、找到节点要添加的位置*/
Node cur = root; // cur:表示要判断的当前节点。cur从根节点开始判断,因此初始值为root
Node pre = null; // pre表示cur的上个节点 也就是父节点
// 实际上当cur==null时 说明我们已经找到合适的位置了
while (cur != null) {
if (key < cur.key) { // 向左子树寻找
pre = cur;
cur = cur.left;
}else if (key > cur.key) { // 向右子树寻找
pre = cur;
cur = cur.right;
}else { // key == cur.key 则表示当前key已存在
cur.data = data; // 新值覆盖旧值,并返回结束
return;
}
}
// 循环结束 cur为null则表示已经找到了合适的添加位置
/*3、最终判断:应当插入父节点的左边还是右边?*/
if (key < pre.key) // 插入到父节点的左边
pre.left = new Node(key, data);
else // 插入到父节点的右边
pre.right = new Node(key, data);
}
/** * 中序遍历 * @param node */
public void midOrder(Node node) {
if (node != null) {
midOrder(node.left);
System.out.println("节点的key:"+node.key+" 节点的值:"+node.data);
midOrder(node.right);
}
}
/** * 非递归的搜索 * @param key * @return */
public Node find(int key) {
// cur从根节点开始搜索
Node cur = root;
while (cur != null) {
// 如果当前节点的key与搜索的key值相等 则说明找到了,直接返回当前节点
if (cur.key == key)
return cur;
// 下面是当前节点大于key和小于key的情况(向下搜索)
if (key < cur.key)
cur = cur.left;
else { // key > cur.key
cur = cur.right;
}
}
// 如果走出循环还没找到 则表示已经找到末尾了还没找到
return null;
}
/** * 递归的搜索 * @param node * @param key * @return */
public Node dgFind(Node node, int key) {
// 如果节点为空 则表示已经找到末尾了还没找到
if (node == null)
return null;
// 如果cur.key == key 则表示找到了,直接返回
if (node.key == key)
return node;
// 下面是当前节点大于key和小于key的情况
if (key < node.key)
return dgFind(node.left, key); // 切记这里是return dgFind(xxx, xxx) 不是直接调用dgFind(xxx, xxx)
else // key > node.key
return dgFind(node.right, key);
}
/** * 返回指定key的父节点 * @param key * @return */
public Node findParent(int key) {
// 如果搜索的key是根节点的key 那么直接返回null 因为root没有父节点
if (key == root.key)
return null;
Node cur = root;
while (cur != null) {
// 如果左节点不为null 且左节点的key与搜索的key相同 怎直接返回当前节点
if (cur.left!=null && cur.left.key==key)
return cur;
// 与上面类似
if (cur.right!=null && cur.right.key==key)
return cur;
// 向下搜索
if (key < cur.key)
cur = cur.left;
if (key > cur.key)
cur = cur.right;
}
// 如果走出循环还没找到 则表示已经找到末尾了还没找到
return null;
}
/** * 删除指定节点 * @param key * @return */
public boolean delNode(int key) {
/** * 先分两大种情况: * 删除节点为 非root节点 * 删除节点为 root节点 * * 再分三种情况: * 1、删除的节点是叶子节点(左右节点都为null) * 2、删除的节点只有一个子树(左节点为null 或者 右节点为null) * 3、删除的节点有两颗子树(左右节点都不为null) */
// 找到要删除的节点
Node targetNode = find(key);
if (targetNode == null) // 如果node为null 这说明树中不存在指定key的节点,直接返回false
return false;
// 找到要删除节点的父节点
Node parent = findParent(key);
if (parent != null) { // parent不为null,则表示删除节点不是root节点
if (targetNode.left==null && targetNode.right==null) { // 1、删除节点是叶子节点
if (parent.left!=null && parent.left.key == targetNode.key) // 待删除节点是父节点的左节点
parent.left = null;
else // 待删除节点是父节点的右节点
parent.right = null;
}else if (targetNode.left!=null && targetNode.right!=null) { // 3、待删除节点有两棵子树
// 备份一下要替换的节点
Node maxNode = searchMax(targetNode.left);
Node temp = new Node(maxNode.key, maxNode.data);
// 将这个节点从树中删除
delNode(maxNode.key);
// temp节点 的左、右指针指向 待删除节点的左、右节点
temp.left = targetNode.left; temp.right = targetNode.right;
// 父节点的左指针或者右指针指向temp节点, 备份节点彻底替换掉待删除节点
if (parent.left!=null && parent.left.key == targetNode.key)
parent.left = temp;
else
parent.right = temp;
}else { // 2、待删除节点有一颗子树
if (parent.left!=null && parent.left.key == targetNode.key) { // 如果待删除节点是parent的左节点
if (targetNode.left != null) // 若待删除节点唯一存在的子树是左子树
parent.left = targetNode.left;
if (targetNode.right != null) // 若待删除节点唯一存在的子树是右子树
parent.left = targetNode.right;
}else { // 如果待删除节点是parent的右节点
if (targetNode.left != null)
parent.right = targetNode.left;
if (targetNode.right != null)
parent.right = targetNode.right;
}
}
}else { // parent为null,则表示删除节点是root节点
if (targetNode.left==null && targetNode.right==null) {
root = null;
}else if (targetNode.left!=null && targetNode.right!=null) {
Node maxNode = searchMax(targetNode.left);
Node temp = new Node(maxNode.key, maxNode.data);
delNode(maxNode.key);
temp.right = targetNode.right; temp.left = targetNode.left;
// 将这个备份节点设置为root节点
this.root = temp;
}else {
if (targetNode.left != null)
this.root = targetNode.left;
else
this.root = targetNode.right;
}
}
return true;
}
/** * 找寻该节点下面的的最大节点 * @param node * @return */
public Node searchMax(Node node){
// 循环找到最大节点(只要右子节点存在,就移入)
Node target = node;
while(target.right != null){ // 无需递归
target = target.right;
}
// 已到达最大节点
return target;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_45464560/article/details/121134249
内容来源于网络,如有侵权,请联系作者删除!