关于java:二叉排序树Java实现

44次阅读

共计 8043 个字符，预计需要花费 21 分钟才能阅读完成。

PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接

目录

1、数列的查问和增加问题

2、二叉排序树 

 2、1 二叉排序树的介绍

 2、2 二叉排序树的创立和遍历

 2、3 二叉排序树的删除

1、数列的查问和增加问题

讲二叉排序树之前，咱们先丢出一个问题：假如给你一个数列 {7,3,10,12,5,2,8}，你用什么方法如何实现它进行高效的查问和增加数据？以下有 3 种计划进行参考；

计划 1：应用数组

（1）如果数组未排序，那么间接在数组尾增加，这样速度快，然而查找速度很慢。

（2）如果数组曾经排序，那么能够间接应用二分查找，这样查找速度会更快，然而为了确保数组有序，在增加新数据时，找到插入地位后，前面的数据需整体挪动，速度就变慢。

计划 2：应用链表

不论链表是否有序，查找速度都是很慢的，然而增加数据速度会比数组快，不须要数据挪动。

计划 3：应用二叉排序树

既能够保证数据的检索速度，同时也能够保证数据的插入，删除，批改的速度。

2、二叉排序树

2、1 二叉排序树的介绍

对于二叉排序树的任何一个非叶子节点，要求左子节点的值比以后节点的值小，右子节点的值比以后节点的值大；留神：假如有雷同的值，能够将该节点当作左子节点或右子节点。

好，咱们当初先画一棵二叉排序树，这样会更好了解一点，二叉排序树如图 1 所示；

图片

看，假如图 1 中的 5 节点是以后节点，那么左子节点的值比以后节点的值小，右子节点的值比以后节点的值大。

2、2 二叉排序树的创立和遍历

将一个数列 array = {7,3,10,12,5,2,8} 创立成对应的二叉排序树，并应用后序遍历（后续遍历相干的内容可看 Java 版的数据结构和算法（四）这篇文章）二叉排序树。

将数列 array = {7,3,10,12,5,2,8} 创立成二叉排序树的思路如下所示；

（1）用一个 for 循环遍历 array 数组，用 array 元素作为节点的值创立 Node 节点。

（2）将 array 的第一个元素作为一棵树的根节点 root，刚开始 root 的左右子树都为空。

（3）将 array 的第二个元素以及前面的元素增加到 root 为根节点的树中。

（4）增加的元素如果小于以后节点的值并且以后节点的左子节点为空，那么就将增加的元素作为以后节点的左子节点。

（5）增加的元素如果小于以后节点的值并且以后节点的左子节点不为空，那么就将以后节点的左子节点作为新的以后节点，而后又走（4）步骤。

（6）增加的元素如果大于等于以后节点的值并且以后节点的右子节点为空，那么就将增加的元素作为以后节点的右子节点。

（7）增加的元素如果大于等于以后节点的值并且以后节点的右子节点不为空，那么就将以后节点的右子节点作为新的以后节点，而后又走（4）步骤。

咱们下面这些思路，数列 array = {7,3,10,12,5,2,8} 创立的二叉排序树如图 2 所示；

图片

咱们将数列 array = {7,3,10,12,5,2,8} 创立成对应的二叉排序树并应用后序遍历，当初用 Java 代码实现一把；

（1）创立一个节点类 Node :

package com.xiaoer.binarysorttree;

public class Node {

private Node leftNode;
private Node rightNode;
private int value;

public Node(int value) {

super();
this.value = value;

}
public Node getLeftNode() {

return leftNode;

}
public void setLeftNode(Node leftNode) {

this.leftNode = leftNode;

}
public Node getRightNode() {

return rightNode;

}
public void setRightNode(Node rightNode) {

this.rightNode = rightNode;

}

// 增加节点办法
public void addNode(Node node) {

if (node == null) {System.out.println("该节点为空，不进行增加");
  return;
}

// 判断传入节点的值是否比以后节点的值小
if (node.value < value) {
  
  // 如果以后节点的左子节点为空，那么就把传入的节点作为以后节点的左子节点
  if (leftNode == null) {
    leftNode = node;
    
    // 递归遍历以后节点的左子树增加 node
  } else {leftNode.addNode(node);
  }
  
  // 否则增加的节点的值大于等于以后节点的值
} else {
  
  // 如果以后节点的右子节点为空，那么就把传入的节点作为以后节点的右子节点
  if (rightNode == null) {
    rightNode = node;
    
    // 递归遍历以后节点的右子树增加 node
  } else {rightNode.addNode(node);
  }
}

}

// 后续遍历
public void postOrder() {

if (leftNode != null) {leftNode.postOrder();
}

if (rightNode != null) {rightNode.postOrder();
}

System.out.println(this);

}

@Override
public String toString() {

return "Node [value=" + value + "]";

}

}

（2）创立一个测试类 Test：

package com.xiaoer.binarysorttree;

public class Test {

private Node rootNode;

public static void main(String[] args) {

    int[] array = {7,3,10,12,5,2,8};
    Test test = new Test();
    
    //for 循环将数组转化成二叉排序树
    for (int i = 0;i < array.length;i++) {test.addNode(new Node(array[i]));
    }
    
    // 二叉排序树的后续遍历
    test.postOrder();

}

private void addNode(Node node) {

if (rootNode == null) {rootNode = node;} else {rootNode.addNode(node);
}

}

private void postOrder() {

if (rootNode == null) {System.out.println("这是一棵空树");
} else {rootNode.postOrder();
}

}
}

运行程序，日志打印如下所示；

图片

依据日志打印的后果，的确咱们用后序遍历的二叉树就是图 2 中的二叉树。

2、3 二叉排序树的删除

二叉排序树的删除有三种状况须要思考；

（1）删除叶子节点（比方图 2 中的 2、5、8、12）。

（2）删除只有一棵子树的节点。

（3）删除有两颗子树的节点（比方图 2 中的 3、7、10）

好，咱们当初写一下这三种状况的思路；

删除叶子节点的思路

（1）找到要删除的结点。

（2）找到要删除的节点的父结点。

（3）确定要删除的节点是父节点的左子结点还是右子结点，如果是左子节点，就将父节点的左子节点置空；如果是右子节点，就将父节点的右子节点置空。

删除只有一棵子树的节点的思路

（1）先去找到要删除的结点（假如为 deleteNode）

（2）找到 deleteNode 的父结点（假如为 parentNode）

（3）确定 deleteNode 的子结点是左子结点还是右子结点。

（4）确定 deleteNode 是 parentNode 的左子结点还是右子结点。

（5）如果 deleteNode 有左子节点且 deleteNode 是 parentNode 的左子结点，那么 parentNode 的左子节点就指向 targetNode 的左子节点。

（6）如果 deleteNode 有左子节点且 deleteNode 是 parentNode 的右子结点，那么 parentNode 的右子节点就指向 targetNode 的左子节点。

（7）如果 deleteNode 有右子节点且 deleteNode 是 parentNode 的左子结点，那么 parentNode 的左子节点就指向 targetNode 的右子节点。

（8）如果 deleteNode 有右子节点且 deleteNode 是 parentNode 的右子结点，那么 parentNode 的右子节点就指向 targetNode 的右子节点。

删除有两颗子树的节点的思路

（1）先去找到要删除的结点（假如是 deleteNode）。

（2）找到 deleteNode 的父结点（假如是 parentNode）。

（3）从 deleteNode 的右子树找到最小的结点。

（4）用一个长期变量（temp），将最小结点的值保留 temp 中，并删除该最小结点。

（5）将 deleteNode 的值设置为 temp。

好，咱们当初在图 2 的根底上增加一个值为 9 的节点，那么依照创立二叉排序树的规定，这个值为 9 的节点就成为了 8 节点的右子节点，那么就失去如图 3 所示的二叉排序树了；

图片

当初咱们要在图 3 的二叉排序树中分 3 次删除一个节点，第一次删除叶子节点 12，第二次删除只有一棵子树的节点（也就是 8），第三次删除有两棵子树的节点（就拿 10 节点来吧）；好，咱们当初代码实现一把，在下面创立二叉排序树的案例的代码上，咱们只须要增加局部代码即可；

（1）在 Node 类中增加 2 个办法，那就是 setValue(int value) 和 getValue() 办法；

public void setValue(int value) {

this.value = value;

}

public int getValue() {

return value;

}

（2）在 Test 类中增加 deleteNode(int value, Node rootNode)、deleteRightTreeMin(Node node)、deleteMinNode(int value, Node deleteNode)、searchDeleteNode(int value, Node node) 和 searchDeleteParentNode(int value, Node node) 这几个办法；

/**

  • 删除节点
  • @param value
  • 查找要删除的值
  • @param rootNode
  • 根节点
    */

private void deleteNode(int value, Node rootNode) {

if (rootNode == null) {System.out.println("这是一棵空树，删除失败");
  return;
}

// 查找要删除的节点
Node deleteNode = searchDeleteNode(value, rootNode);

if (deleteNode == null) {System.out.println("没找到要删除的节点，删除失败");
  return;
}

// 如果这棵树只有一个根节点，那么就将根节点置空
if (rootNode.getLeftNode() == null && rootNode.getRightNode() == null) {
  rootNode = null;
  System.out.println("这棵树只有一个根节点，删除胜利");
  return;
}

// 如果要删除的节点是根节点且只有一颗左子树
if (rootNode.getLeftNode() != null && rootNode.getRightNode() == null
    && rootNode.getValue() == value) {rootNode = rootNode.getLeftNode();
  return;
}

// 如果要删除的节点是根节点且只有一颗右子树
if (rootNode.getLeftNode() == null && rootNode.getRightNode() != null
    && rootNode.getValue() == value) {rootNode = rootNode.getRightNode();
  return;
}

// 查找要删除节点的父节点
Node parentNode = searchDeleteParentNode(value, rootNode);

// 如果删除的节点是叶子节点
if (deleteNode.getLeftNode() == null
    && deleteNode.getRightNode() == null) {if (parentNode.getLeftNode() != null
      && parentNode.getLeftNode().getValue() == value) {parentNode.setLeftNode(null);

  } else if (parentNode.getRightNode() != null
      && parentNode.getRightNode().getValue() == value) {parentNode.setRightNode(null);
  }

  // 要删除有 2 棵子树的节点
} else if (deleteNode.getLeftNode() != null
    && deleteNode.getRightNode() != null) {int minValue = deleteRightTreeMin(deleteNode.getRightNode());
  deleteNode.setValue(minValue);

  // 要删除只有一颗子树的节点
} else {

  // 要删除的节点只有左子节点
  if (deleteNode.getLeftNode() != null) {

    // deleteNode 是 parentNode 的左子树
    if (parentNode.getLeftNode() != null
        && parentNode.getLeftNode().getValue() == value) {parentNode.setLeftNode(deleteNode.getLeftNode());

      // deleteNode 是 parentNode 的右子树
    } else {parentNode.setRightNode(deleteNode.getLeftNode());
    }

    // 要删除的节点只有右子节点
  } else {

    // deleteNode 是 parentNode 的左子树
    if (parentNode.getLeftNode() != null
        && parentNode.getLeftNode().getValue() == value) {parentNode.setLeftNode(deleteNode.getRightNode());

      // deleteNode 是 parentNode 的右子树
    } else {parentNode.setRightNode(deleteNode.getRightNode());
    }
  }
}

}

/**

  • @param node
  • 以 node 为根节点
  • @return 返回以 node 为根节点子树中最小的 value 值
    */

private int deleteRightTreeMin(Node node) {

Node t = node;
while (t.getLeftNode() != null) {t.setLeftNode(t.getLeftNode());
}

int value = t.getValue();

// 删除最小节点
deleteMinNode(value, t);
return value;

}

private void deleteMinNode(int value, Node deleteNode) {

deleteNode(value, deleteNode);

}

// 查找要删除的节点（值为 value），node 为以后节点
private Node searchDeleteNode(int value, Node node) {

if (node == null) {System.out.println("进行递归的节点不能为空");
  return null;
}

// 找到该节点
if (value == node.getValue()) {
  return node;

  // 如果查找的值小于以后节点的值，那么就向左递归查找
} else if (value < node.getValue()) {

  // 如果以后节点的左子节点为空，那么就不进行递归查找要删除的节点了
  if (node.getLeftNode() == null) {return null;}
  return searchDeleteNode(value, node.getLeftNode());

  // 如果查找的值大于以后节点的值，那么就向右递归查找
} else {

  // 如果以后节点的右子节点为空，那么就不进行递归查找要删除的节点了
  if (node.getLeftNode() == null) {return null;}
  return searchDeleteNode(value, node.getRightNode());
}

}

/**

  • @param value
  • 要查找的值
  • @param node
  • 要删除节点的父节点
  • @return 返回以后节点的父节点
    */

private Node searchDeleteParentNode(int value, Node node) {

// 要删除节点的父节点如果为空
if (node == null) {return null;}

// 如果要删除节点的父节点的值等于要查找的值，则返回要删除节点的父节点
if ((node.getLeftNode() != null && node.getLeftNode().getValue() == value)
    || (node.getRightNode() != null && node.getRightNode()
        .getValue() == value)) {return node;} else {

  // 如果要查找的值小于以后节点的值且以后节点的左子节点不为空
  if (value < node.getValue() && node.getLeftNode() != null) {

    // 向左子树递归查找
    return searchDeleteParentNode(value, node.getLeftNode());

    // 如果要查找的值大于等于以后节点的值且以后节点的右子节点不为空
  } else if (value >= node.getValue() && node.getRightNode() != null) {

    // 向右子树递归查找
    return searchDeleteParentNode(value, node.getRightNode());
  } else {

    // 没有找到父节点
    return null;
  }
}

}

删除叶子节点 12，程序入口调用如下所示；

public static void main(String[] args) {

int[] array = { 7, 3, 10, 12, 5, 2, 8 ,9};
Test test = new Test();

// for 循环将数组转化成二叉排序树
for (int i = 0; i < array.length; i++) {test.addNode(new Node(array[i]));
}

test.deleteNode(12, test.rootNode);

// 二叉排序树的后续遍历
test.postOrder();

}

删除叶子节点 12，日志打印如下所示；

图片

删除只有一颗子树的节点 8，程序入口调用如下所示；

public static void main(String[] args) {

int[] array = { 7, 3, 10, 12, 5, 2, 8 ,9};
Test test = new Test();

// for 循环将数组转化成二叉排序树
for (int i = 0; i < array.length; i++) {test.addNode(new Node(array[i]));
}

test.deleteNode(8, test.rootNode);

// 二叉排序树的后续遍历
test.postOrder();

}

删除只有一颗子树的节点 8，日志打印如下所示；

图片

删除有两棵子树的节点 10，程序入口调用如下所示；

图片

正文完
java
发表至： java
2022-04-30
 0
关于java:牛逼京东热-框架-JDhotkey-开源了单机-QPS-可达-37-万
关于java:Druid测试Druid工具类
关于java:Mybatis事务管理机制
JMM内存模型详解一