1、二叉搜索树的删除操作

介绍

关于二叉搜索树的删除操作，先弄清如何找到前驱节点和后继节点

前驱节点(predecessor)

介绍

•前驱节点：中序遍历时的前一个节点•如果左子树存在，从该节点的左子节点的最右的节点。•如果左子树 == null && 父节点！= null 父节点为父节点遍历，一直到节点关系发生改变。如下图所示。•如果左子树 == null && 父节点== null ，没有前驱节点。

代码

public Node<E> findPredecessorNode(E element) {
  return findPredecessorNode(node(element));
}

private Node<E> findPredecessorNode(Node<E> element) {
  if (element.left != null) {
    Node<E> node = element.left;
    while (node.right!= null) {
      node = node.right;
    }
    return node;
  }

  while (element.parent != null && element == element.parent.left) {
    element = element.parent;
  }
  return element.parent;
}

后继节点(succeessor)

•前驱节点：中序遍历时的后一个节点•如果右子树存在，从该节点的左子节点的最左的节点。•如果右子树 == null && 父节点！= null 父节点为父节点遍历，一直到节点关系发生改变。•如果右子树 == null && 父节点== null ，没有后继节点。

删除节点

叶子节点

•直接删除

度为1的节点

•用子节点替换既可

度为2的节点

•找到前驱或者后继节点的值，并替换原节点。•他的前驱、后继节点的度只可能是0或者是1。

private void remove(Node<E> node) {
  if (node == null) return;
  size--;

  // 度为2的节点
  if (node.twoChildren()) { 
    // 找到后继节点
    Node<E> s = findSucceessorNode(node);
    // 用后继节点的值覆盖原节点的值
    node.element = s.element;

    node = s;
  }

  // 删除的node节点  （node的度必然是1或者0） 如果是0 replacement为null
  Node<E> replacement = node.left != null ? node.left : node.right;

  // 度为1
  if (replacement != null) {
    // 更改parent
    replacement.parent = node.parent;
    // 更改parent的 chil
    if (node.parent == null) { // node是度为1的节点并且是根节点
      root = replacement;
    } else if (node == node.parent.left) {
      node.parent.left = replacement;
    } else { // node == node.parent.right
      node.parent.right = replacement;
    }
  } else if (node.parent == null) { // node是叶子节点并且是根节点
    root = null;
  } else { // node是叶子节点
    if (node == node.parent.left) {
      node.parent.left = null;
    } else { 
      node.parent.right = null;
    }
  }
}

2、根据遍历结果重构二叉树

•中序遍历+ 前/后序遍历 •可以确定一颗唯一二叉树•前序遍历+ 后序遍历•如果他是一颗真二叉树(Proper Binary Tree) ,结果是唯一的。•其他情况 不唯一。

List<Integer> perorder = Arrays.asList(5,1,2,4,3,9);
List<Integer> inorder = Arrays.asList(2,1,4,5,9,3);


private  Node<E> RefactoringTree(List<E> perorderList, List<E> inorderList) {
  if (perorderList.size() == 0|| inorderList.size() == 0) {
    return null;
  }
  E element = perorderList.get(0);

  Node<E> root = new Node<>(element, null);
  perorderList = perorderList.subList(1, perorderList.size());
  int index = inorderList.indexOf(element);
  List<E> leftInorderList = inorderList.subList(0, index);
  List<E> rightInorderList = inorderList.subList(index + 1, inorderList.size());

  List<E> leftperOrderList = perorderList.subList(0, leftInorderList.size());
  List<E> rightperOrderList = perorderList.subList(leftperOrderList.size(), perorderList.size());

  root.left = RefactoringTree(leftperOrderList, leftInorderList);
  root.right = RefactoringTree(rightperOrderList, rightInorderList);
  return  root;
}