Java-二叉排序树的简介与遍历

先看一个需求 给你一个数组（7，3，10，12，5，1，9），要求能高效的完成对数据的查询的添加 解决方案分析 使用数组 数组未排序，优点：直接在数组尾添加，速度快。缺点：查找速度慢 数组排序：优点：可以使用二分查找，查找速度快。缺点：为了保证数组有序，在添加数据时，找到插入位置后，后面的数据需要整体移动，速度慢 使用链式储存-链表 不管链表是否有序，查找速度都很慢，添加数据速度比数组快，不需要数据整体移动 使用二叉排序树

二叉排序树介绍

二叉排序树：BST（Binary Sort(Search) Tree），对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值要小，右子节点的值要比当前节点的值要大 特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点

二叉排序树遍历代码实现

//创捷节点 class Nodes{ int value; Nodes left; Nodes right; public Nodes(int value) { super(); this.value = value; } @Override public String toString() { return "Nodes [value=" + value + "]"; } //添加节点方法 //递归形式添加，注意要满足二叉排序树的要求 public void add(Nodes node) { if(node==null) { return; } //判断传入的节点值和当前子树根节点的值的关系 if(node.value<this.value) { //如果当前节点左子节点为空 if(this.left==null) { this.left=node; }else { //递归向左子树添加 this.left.add(node); } }else {//添加的节点值大于当前的节点值 if(this.right==null) { this.right=node; }else { //递归向右子树添加 this.right.add(node); } } } //中序遍历 public void infixOrder() { if(this.left!=null) { this.left.infixOrder(); } System.out.println(this); if(this.right!=null) { this.right.infixOrder(); } } } //创建二叉排序树 class BinarySortTree{ private Nodes root; //添加节点方法 public void add(Nodes node) { if(root==null) { root=node; }else { root.add(node); } } //中序遍历 public void infixOrder() { if(root!=null) { root.infixOrder(); }else { System.out.println("二叉排序树为空"); } } } 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 Nodes(arr[i])); } //中序遍历二叉排序树 System.out.println("中序遍历二叉排序树~"); binarySortTree.infixOrder();//1,3,5,7,9,10,12 }