树结构入门教程-二叉排序树

前面我们学习了赫夫曼相关的实际操作,本节我们再来学习另外一种树的结构算法--->二叉排序树,那么首先我们来介绍下什么是二叉排序树

二叉排序树的介绍

二叉排序树简称BST(BinarySortTree),对于二叉排序树的任何一个非叶子节点,都有这样的要求:左子节点的值比当前节点的值要小,右子节点的值比当前节点的值要大,这里还有一种特殊的情况:

如果值都是相同的,我们可以将节点放在左子节点或者是右子节点,当然一般会尽量避免出现相同的.我们来看一个案例如下图的二叉排序树{7,3,10,12,5,1,9}当我们要插入2是过程如下图所示:

image.png

上述就是二叉树排序树的示意图,了解完什么是二叉排序树我们通过具体的案例然后用代码来实现一棵二叉排序树的创建过程

案例分析

假设我们有这样一组数列{7,3,10,12,5,1,9},需要我们完成二叉排序树的创建和打印操作

代码实现

首先我们需要一个Node,这个我们还是直接用之前创建的即可,代码如下:

''''
//创建节点
class Node{
int value;
Node left;
Node right;

public Node(int value) {
    this.value = value;
}

@Override
public String toString() {
    return "Node{" +
            "value=" + value +
            '}';
}
//节点的添加方法
//采用递归的方式来添加,需要满足二叉排序树的要求
public void add(Node node){
    if (node == null){
         return;
    }
    //判断当前传入节点的值和当前子树的根节点的值的关系
    if (node.value < this.value){
        //如果当前节点的左子节点为null,我们直接添加
        if (this.left == null){
            this.left = node;
        }else { //递归去添加
            this.left.add(node);
        }
    }else { //表示 node.value > this.value
        if (this.right ==null){
            this.right = node;
        }else {
            this.right.add(node);
        }
    }
}
//中序遍历
public void midOrder(){
    if (this.left !=null){
        this.left.midOrder();
    }
    //输出当前节点
    System.out.println(this);
    if (this.right !=null){
        this.right.midOrder();
    }
}

上述Node中最重要的方法是add方法,也是我们动态构建二叉排序树的核心方法,之前我们构建树都是手动去添加节点,这里是递归去添加的,再来看我们的创建二叉排序树的代码:

//创建二叉排序树
class BinarySortTree{
private Node root;
//添加方法
public  void add(Node node){
    if (root ==null){//表示空树
       root = node;
    }else {
        root.add(node);
    }
}
//中序遍历
public void midOrder(){
    if (root != null){
        root.midOrder();
    }else {
        System.out.println("二叉排序树为null,无法遍历!");
    }
}

我们可以看到的是这里还是调用Node中的add方法,接着我们来测试一把,测试代码如下:

/**
 * 树结构学习-二叉排序树
 */
public class BinarySortTreeCase {
public static void main(String[] args) {
    int[] arr = {7,3,10,12,5,1,9};
    BinarySortTree binarySortTree = new BinarySortTree();
    //循环添加节点
    for (int i = 0; i <arr.length ; i++) {
        binarySortTree.add(new Node(arr[i]));
    }
    //中序遍历二叉排序树
    System.out.println("中序遍历二叉排序树!");
    binarySortTree.midOrder();

来看测试结果如下图所示:

二叉排序树创建测试结果.png

上图测试结果是我们通过中序遍历得到的结果,最后发现是没有问题的,那么关于二叉树的创建和遍历我们就到这了,下篇我们来学习它的删除节点的操作过程,完整代码在Git上可下载:

• Git地址:https://gitee.com/cblove_java/nacos_learning_demo