删除某层二叉树的方法

Question

我有 class SimpleTree 只是基本的二叉树：

public class SimpleTree<T extends Comparable<T>> {
protected class TreeItem {
    public T value;
    public TreeItem left;
    public TreeItem right;

    public TreeItem(T value, TreeItem left, TreeItem right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public TreeItem(T value) {
        this(value, null, null);
    }

    public T getValue() {
        return value;
    }

    public TreeItem getLeft() {
        return left;
    }

    public TreeItem getRight() {
        return right;
    }

    public void setValue(T value) {
        this.value = value;
    }
}

protected TreeItem item = null;
protected int size = 0; // number of elements

而问题是写方法：

 public void delete(TreeItem item, int level) {
...
}

其中 level 是某个树中元素的级别（根级别 == 0）。例如 level == 1:

Before:
            8 ----- 0 level root
           / \
          /   \  (size == 6)
         /     \
        5       10 ----- 1 level
       / \       \
      2   6      11 ----- 2 level and etc.

After:
                8 ----- 0 level
               / \
              /   \   (size == 3)
             /     \
            /       \ 
           /         \
          2           11 ----- 1 level

只保存 DELETED 元素的 LEFT 叶子，如果我们没有这样 -> 保存右边。

Answer 1

你的树好像是递归数据结构。

假设要删除Level N，然后递归向下遍历到N- 1 在 N-1 级检查四种情况：

它有一个左边和一个右边child（节点2）
它只有一个左child（节点6）
它只有一个权利child（节点10）
没有children（节点7）

当您尝试删除 N 级时您必须修复剩余的节点这就是你从 N-1 级开始的原因，因为你需要 fix-up 阶段 N 级每个节点的 parent。

以上四种情况很容易简化为：

如果左child的左child存在，则将左child设置为左child的左child。 (4.left = 4.left.left)
else如果左边child的右边child存在，则将左边child设置为左边child的右边child。 (4.left = 4.left.对)
其他NO-OP

右边child 例如节点4完全一样。

实际上，fix-up 就是您所需要的。之后，让 GC 为您清理，您就完成了。

删除某层二叉树的方法

Method to delete certain level of binary tree

java

binary-tree