数据结构与算法（九）二叉搜索树的删除操作

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;
}

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;
    }
  }
}

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;
}