一文详解：二叉搜索树

这几天一直在刷题，每天都觉得时间不够用，心态上会有波动。争取在9月之前刷到300道题，调整心态，继续前行。

今天我们来复习一下二叉排序树（BST），首先我们先看下定义： 一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； （4）没有键值相等的结点。 其实BST是一个排过序的二叉树，具体怎么排的呢？按照定义可以知道，对于一个结点比它小的值，放在左边；比它大的值放在右边。其中左子树和右子树也分别满足这个规则。例如下图这个二叉树就是一个二叉排序树（BST） 接下来我们用代码来实现，当然啦，第一步肯定先要造一个结点，然后结点组成一个二叉树 造结点： 在节点中我们写了添加节点的方法，使用的是递归的方式；不得不说，在树的问题中，递归用的真的是多。其实为了方便遍历我们写了二叉树的中序遍历（递归方式）。

//创建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{ 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 Node root; //添加节点的方法 public void add(Node node){ if(root == null){ root = node; }else{ root.add(node); } } //中序排序 public void infixOrder(){ if(root != null){ root.infixOrder(); }else{ System.out.println("当前的二叉排序树是空的"); } } }

最后进行测试:

public class BST { 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(arr[i]); //需要传入的是node结点 binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 binarySortTree.infixOrder(); } }

这里我们需要注意的是：二叉树和二叉排序树主要区别就是排序，因此，我们需要注意二叉排序树的插入，单独拎出来看一下：

//添加节点的方法 public void add(Node 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); } } }