二叉搜索树

二叉搜索树/二叉查找树/二叉排序树

特点：

• 树节点增加key属性，用来比较谁大谁小，key不可以重复
• 对于任意一个树节点，它的key比左子树的key都大，同时也比右子树的key都大

/**
 * 二叉搜索树
 */
public class BSTree1 {

    public  TreeNode root;

    public static class TreeNode {
        int key;  //节点的健
        Object value; //节点的值
        TreeNode left;
        TreeNode right;

        public TreeNode(int key) {
            this.key = key;
        }

        public TreeNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public TreeNode(int key, Object value, TreeNode left, TreeNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}

查找元素 - 递归实现

public class BSTree1 {
  
  ...

  public Object get(int key) {
    return doGet(root, key);
  }

  private Object doGet(TreeNode node, int key) {
      if (node == null) { //没找到结束递归
          return null;
      }

      if (key < node.key) { //向左找
          return doGet(node.left, key);
      } else if (key > node.key) { //向右找
          return doGet(node.right, key);
      } else { //找到了
          return node.value;
      }
  }
}

查找元素 - 非递归实现

public class BSTree1 {

  ...

  public Object get(int key){
      TreeNode node = root;
      while(node != null){
          if (key < node.key){ //向左
              node = node.left;
          }else if (key > node.key){ //向右
              node = node.right;
          }else{
              return node.value;
          }
      }

      return null;
  }
}