算法二叉树的构建和查找

潇洒

发布于 2023-10-20 10:31:42

1390

发布于 2023-10-20 10:31:42

文章被收录于专栏：石头岛

前言

对二叉树有一定了解之后，学习一下对二叉树的操作，有时候这些东西一学就忘，反复操作几回就熟了。二叉树的概念已经了解了，那么得知道怎么操作。现在就讲讲怎么操作二叉树。

构建二叉树

首先得先种一颗树，然后才能操作树。怎么构建？有哪些对象、需要什么方法？

主要对象

Node 节点对象
BinaryTree 树对象

Node 节点对象

作用：存数据的。大白话就是树中的每一个节点，存着外面进来的数据。最简单的理解就是HashMap就是一颗树的实现，每次不明白，就想想HashMap，是不是就通了。

四个关键要素：

left
right
key
value

BinaryTree 对象

作用：操作node节点数据，维护树结构。大白话，就是把Node拼起来，成为一颗大树。主要操作：

put
get
delete
size
min
max

put 完以后要返回整棵树，开始是始于 root，返回也是返回 root。

实现

实现就是把Node和BinaryTree这两结合起来用，还用的没问题。需要考虑几个问题：

怎么结合起来用
从哪开始写

怎么结合起来用？即然要操作，那就需要对外暴露操作接口BinaryTree就是最外操作的对象。

从哪开始写？先定义数据结构，再定义方法。

查询和添加逻辑基本相同，都是通过递归的形式。删除比较麻烦，如果被删除的节点有子节点，不能让丢掉这些子节点，需要重新维护这些子节点。删除的节点，左子树的所有节点一定比右子树的节点小，所以只需要从右子树中拿到最小的那个节点即可，也就是右子树中最左边的叶子节点。

删除步骤

找到要删除的 key
判断如果左子树为空，就用右边最小
判断如果右子树为空，就用左边最小
删除找到的最小值
将最小值替换被删除的节点，重新跟左右子节点建立连接
简化的情况被删除节点只有一个左子树或右子树，直接拿过来替换当前节点就行

实现代码：

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * 二叉树
 * 左小右大
 *
 * @author liu kai
 * @since 2015/5/30 19:30.
 */
public class BinaryTree<Key extends Comparable<Key>, Value> {

  //根节点
  private Node root;
  //个数
  private int size;

  private class Node {
    public Node left;
    public Node right;
    public Key key;
    public Value value;

    public Node(Key key, Value value, Node left, Node right) {
      this.left = left;
      this.right = right;
      this.key = key;
      this.value = value;
    }
  }

  public void put(Key key, Value value) {
    root = put(root, key, value);
  }

  // 插入
  private Node put(Node x, Key key, Value value) {
    if (x == null) {
      size++;
      return new Node(key, value, null, null);
    }
    int comp = key.compareTo(x.key);
    // key 比当前节点小，往左
    if (comp > 0) {
      x.right = put(x.right, key, value);
      // key 比当前节点大，往右
    } else if (comp < 0) {
      x.left = put(x.left, key, value);
      // 相等，就是当前节点，替换值
    } else {
      x.value = value;
    }
    return x;
  }

  // 查询
  public Value get(Key key) {
    return get(root, key);
  }

  private Value get(Node x, Key key) {
    if (x == null) {
      return null;
    }

    int comp = key.compareTo(x.key);
    // key 比当前节点小，往左
    if (comp > 0) {
      return get(x.right, key);
      // key 比当前节点大，往右
    } else if (comp < 0) {
      return get(x.left, key);
      // 相等，就是当前节点，替换值
    } else {
      return x.value;
    }
  }

  public int size() {
    return size;
  }

  public Node delete(Key key) {
    return delete(root, key);
  }

  // x 当前要被删除的点节
  private Node delete(Node x, Key key) {
    if (x == null) {
      return null;
    }
    int comp = key.compareTo(x.key);
    //   1 张三
    //   /   \
    // 2李四  3王五
    //         \
    //        4工作
    if (comp > 0) {
      x.right = delete(x.right, key);
    } else if (comp < 0) {
      x. left = delete(x.left, key);
    } else {

      //1.简单情况：
      // 被删除节点只有一个 左子树 或 右子树，直接拿过来替换当前节点就行
      if (x.left == null) {
        size--;
        return x.right;
      }
      if (x.right == null) {
        size--;
        return x.left;
      }
      size--;
      Node minNode = x.right;
      //2.找到最左节点
      while (minNode.left != null) {
        // 如果 minNode 没有子节点了，说明 minNode 是最小节点
        // 这里 minNode 是当前节点， .left 就是它的子节点
        minNode = minNode.left;
      }

      // 3.断开最左节点和上个节点的联系
      // 由于没有记录父节点是谁，所以需要再次遍历
      Node parent = x.right;
      while (parent.left != null) {
        // 当前节点的子节点没有子节点，就是最小节点
        if (parent.left.left != null) {
          parent.left = null;
        } else {
          parent = parent.left;
        }
      }

      // 4.建立连接
      // 再跟左右子树建立连接，再跟父节点建立连接
      minNode.left = x.left;
      minNode.right = x.right;

      return x;
    }
    return x;
  }
}