java数据结构和算法——二叉排序树的创建、遍历

示例需求：给定一个数组 int[] arr = {7, 3, 10, 12, 5, 1, 9, 2}，创建和遍历二叉排序树

1、创建Node结点类

package com.rf.springboot01.dataStructure.binarySortTree;

/**
 * @description:  创建Node结点
 * @author: xiaozhi
 * @create: 2020-09-27 21:48
 */
public class Node {
    public int value;//节点的值
    public Node left;//左节点
    public Node right;//右节点

    //构造方法
    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    /**
    * @Description: 递归的形式添加结点，注意需要满足二叉排序树的要求
    * @Param:  node 传入的几点
    * @Author: xz
    * @Date: 2020/9/27 21:58
    */
    public void addNode(Node node){
        if(node == null){
            return;
        }
        if(node.value  当前结点的值
            if(this.right == null){ //如果当前结点右子结点为null
                this.right = node;
            }else{//递归的向右子树添加
                this.right.addNode(node);
            }
        }
    }

    /** 
    * @Description: 中序遍历二叉排序树
    * @Param:  
    * @Author: xz  
    * @return: 
    * @Date: 2020/9/27 22:09
    */
    public void infixOrder(){
        //左子节点不为null，向左子节点中序遍历
        if(this.left != null){
            this.left.infixOrder();
        }

        //输出当前节点
        System.out.println(this);

        //右子节点不为null，向右子节点中序遍历
        if(this.right != null) {
            this.right.infixOrder();
        }
    }
}

2、创建二叉排序树类

package com.rf.springboot01.dataStructure.binarySortTree;

/**
 * @description: 创建二叉排序树
 * @author: xiaozhi
 * @create: 2020-09-27 22:16
 */
public class BinarySortTree {
    public Node root;

    public Node getRoot() {
        return root;
    }
    
    /** 
    * @Description:  添加二叉排序树节点方法
    * @Param:  node 传入的节点
    * @Author: xz  
    * @Date: 2020/9/27 22:18
    */
    public void addBstNode(Node node){
        if(root == null){//如果root为空则直接让root指向node
            root = node;
        }else{
            root.addNode(node);
        }
    }
    /** 
    * @Description:  中序遍历二叉排序树方法
    * @Param:  
    * @Author: xz  
    * @return: 
    * @Date: 2020/9/27 22:25   
    */
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空，不能遍历");
        }
    }

}

3、创建测试类

package com.rf.springboot01.dataStructure.binarySortTree;

/**
 * @description:
 * @author: xiaozhi
 * @create: 2020-09-27 22:40
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        //循环的添加结点到二叉排序树
        for(int i=0;i