二叉搜索树的数据结构系列（1）

本文将主要以运动图像的形式显示二叉搜索树的结构和动态操作；但是，不会过多提及基本概念和属性. 如果您想了解该系统，请查看“邓俊辉老师的数据”结构课程；

二叉树: 结合了向量的静态操作（二进制搜索）和列表的动态操作（插入和删除）的优点；使树成为广泛使用的数据结构；

二进制搜索树: 按顺序排列，可以搜索的树是二进制搜索树；如下图所示；

忽略二叉树的大小和高度的简化结构如下:

public class BST<T extends Comparable<? super T>> {
  private BSTNode<T> root;
  public BST() {root = null;}
  ...
  
  class BSTNode<T extends Comparable<? super T>> {
    T key;
    BSTNode<T> parent;
    BSTNode<T> left;
    BSTNode<T> right;
    BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
      this.key = key;
      this.parent = parent;
      this.left = left;
      this.right = right;
    }
  }
}

根据二叉搜索树，左子节点小于父节点，右子节点大于或等于父节点，并逐渐寻找深度；

实现如下:

private BSTNode<T> search(BSTNode<T> x, T key) {
  if (x == null) return x;
  int cmp = key.compareTo(x.key);
  if (cmp < 0)
    return search(x.left, key);
  else if (cmp > 0)
    return search(x.right, key);
  else
    return x;
}
public BSTNode<T> search(T key) {
  return search(root, key);
}

更好的实现方式还应该记录搜索失败的最后一个节点，除了查找最大值和最小值之外.

同样根据BST的排序规则进行插入，首先找到插入位置，然后确定插入节点的引用关系；

如果有大小和其他信息，则需要按顺序从节点开始更新祖先节点

private void insert(T key) {
  BSTNode<T> node = new BSTNode<T>(key, null, null, null);
  BSTNode<T> r = this.root;
  BSTNode<T> p = null;
  int cmp;
  // 查找插入位置
  while (r != null) {
    p = r;
    cmp = node.key.compareTo(r.key);
    if (cmp < 0)
      r = r.left;
    else
      r = r.right;
  }
  if (p == null)
    this.root = node;
  else {
    node.parent = p;
    cmp = node.key.compareTo(p.key);
    if (cmp < 0)
      p.left = node;
    else
      p.right = node;
  }
}

删除，还需要先找到该节点，然后删除；

当目标节点没有左子节点或右子节点时，直接删除该节点，然后替换其后代；

当目标节点同时具有左右两个子节点时:

请注意，这只是一种实现，也可以由前体交换

public void delete(T key) {
  BSTNode<T> node = search(root, key);
  if (node != null) delete(node);
  node = null;
}
private BSTNode<T> delete(BSTNode<T> node) {
  // 将完全节点和直接后继交换
  if (node.left != null && node.right != null) {
    BSTNode<T> succ = successor(node);
    node.key = succ.key;
    node = succ;
  }
  // 将孩子节点的父亲接到祖父上
  BSTNode<T> child = node.left != null ? node.left : node.right;
  if (child != null) child.parent = node.parent;
  // 目标节点没有父节点则是根节点
  if (node.parent == null) root = child;
    // 目标节点是左孩子时
  else if (node == node.parent.left) node.parent.left = child;
    // 目标节点是右孩子时
  else node.parent.right = child;
  return node;
}
private BSTNode<T> successor(BSTNode<T> node) {
    BSTNode<T> succ = node.right;
    while (succ.left != null) succ = succ.left;
    return succ;
}

//这只是右侧子树中的直接后继；整个中阶遍历的直接后继节点也可以是其父节点或祖先节点；

对于数据结构，了解它的最直接方法是遍历该操作数据结构二叉排序树数据结构二叉排序树，对于二叉树，在层次结构之前，之中，之后和层次结构中有四个遍历；

具体过程如下:

// 递归实现
private void travPre(BSTNode<T> tree) {
  if (tree == null) return;
  System.out.print(tree.key + " ");
  travPre(tree.left);
  travPre(tree.right);
}
// 迭代实现
public void travPre2(BSTNode<T> tree) {
  Stack<BSTNode<T>> stack = new Stack<>();
  while (true) {
    visitAlongVine(tree, stack);
    if (stack.isEmpty()) break;
    tree = stack.pop();
  }
}
private void visitAlongVine(BSTNode<T> tree, Stack<BSTNode<T>> stack) {
  while (tree != null) {
    System.out.print(tree.key + " ");
    stack.push(tree.right);
    tree = tree.left;
  }
}

具体过程如下:

// 递归实现
private void travIn(BSTNode<T> tree) {
  if (tree == null) return;
  travIn(tree.left);
  System.out.print(tree.key + " ");
  travIn(tree.right);
}
// 迭代实现
public void travIn2(BSTNode<T> tree) {
  Stack<BSTNode<T>> stack = new Stack<>();
  while (true) {
    goAlongVine(tree, stack);
    if (stack.isEmpty()) break;
    tree = stack.pop();
    System.out.print(tree.key + " ");
    tree = tree.right;
  }
}
private void goAlongVine(BSTNode<T> tree, Stack<BSTNode<T>> stack) {
  while (tree != null) {
    stack.push(tree);
    tree = tree.left;
  }
}

具体过程如下:

// 递归实现
private void travPost(BSTNode<T> tree) {
  if (tree == null) return;
  travPost(tree.left);
  travPost(tree.right);
  System.out.print(tree.key + " ");
}
// 迭代实现
public void travPost2(BSTNode<T> tree) {
  Stack<BSTNode<T>> stack = new Stack<>();
  if (tree != null) stack.push(tree);
  while (!stack.isEmpty()) {
    if (stack.peek() != tree.parent)
      gotoHLVFL(stack);
    tree = stack.pop();
    System.out.print(tree.key + " ");
  }
}
private void gotoHLVFL(Stack<BSTNode<T>> stack) {
  BSTNode<T> tree;
  while ((tree = stack.peek()) != null)
    if (tree.left != null) {
      if (tree.right != null) stack.push(tree.right);
      stack.push(tree.left);
    } else
      stack.push(tree.right);
  stack.pop();
}

遍历图层相对简单，即从上到下逐层遍历；

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-280548-1.html