如何迭代二叉树?

现在我有

 private static void iterateall(BinaryTree foo) {
    if(foo!= null){
    System.out.println(foo.node);
    iterateall(foo.left);
    iterateall(foo.right);
   }
  }

你能把它改成迭代而不是递归吗?


答案 1

您正在寻找的是一种后继算法。

以下是如何定义它:

  • 第一条规则:树中的第一个节点是树中最左边的节点。
  • 下一条规则:节点的后续节点是:
    • Next-R 规则:如果它具有右子树,则为右子树中最左侧的节点。
    • 下一个 U 规则:否则,向上遍历树
      • 如果您向右转弯(即此节点是左子节点),则该父节点是继承节点
      • 如果您左转(即此节点是右转),请继续向上。
      • 如果你不能再上山了,那么就没有继任者了。

如您所见,要实现这一点,您需要一个父节点指针。


例:

alt text

  • 第一条规则:树中的第一个节点是树中最左边的节点:(1)
  • Next-U 规则:由于没有正确的子树,因此我们向上转到 。这是一个右转,下一个也是如此。(1)(3)(3)
  • 下一个 R 规则:由于具有右子树,因此该子树中最左侧的节点是下一个:。(3)(4)
  • Next-U 规则:由于没有正确的子树,因此我们向上转到 。这是一个右转,所以接下来是.(4)(6)(6)
  • 下一个 R 规则:由于具有右子树,因此该子树中最左侧的节点是下一个:。(6)(7)
  • Next-U 规则:由于没有正确的子树,因此我们向上转到 。这是一个左转,所以我们继续向上。这是一个左转,所以我们继续向上。这是一个右转,所以接下来是.(7)(6)(3)(8)(8)
  • 下一个 R 规则:由于具有右子树,因此该子树中最左侧的节点是下一个:。(8)(10)
  • 下一个 R 规则:由于具有右子树,因此该子树中最左侧的节点是下一个:。(10)(13)
  • Next-U 规则:由于没有正确的子树,因此我们向上转到 。这是一个右转,所以接下来是.(13)(14)(14)
  • Next-U 规则:由于没有正确的子树,因此我们向上转到 。这是一个左转,所以我们继续向上。这是一个左转,所以我们想继续往上走,但由于没有父母,我们已经到了终点。 没有继任者。(14)(10)(8)(8)(14)

伪代码

Node getLeftMost(Node n)
  WHILE (n.leftChild != NULL)
    n = n.leftChild
  RETURN n

Node getFirst(Tree t)
  IF (t.root == NULL) RETURN NULL
  ELSE
     RETURN getLeftMost(t.root);

Node getNext(Node n)
  IF (n.rightChild != NULL)
     RETURN getLeftMost(n.rightChild)
  ELSE
     WHILE (n.parent != NULL AND n == n.parent.rightChild)
        n = n.parent;
     RETURN n.parent;

PROCEDURE iterateOver(Tree t)
  Node n = getFirst(t);
  WHILE n != NULL
     visit(n)
     n = getNext(n)

Java 代码

以下是上述算法的简单实现:

public class SuccessorIteration {
    static class Node {
        final Node left;
        final Node right;
        final int key;
        Node parent;
        Node(int key, Node left, Node right) {
            this.key = key;
            this.left = left;
            this.right = right;
            if (left != null) left.parent = this;
            if (right != null) right.parent = this;
        }
        Node getLeftMost() {
            Node n = this;
            while (n.left != null) {
                n = n.left;
            }
            return n;
        }
        Node getNext() {
            if (right != null) {
                return right.getLeftMost();
            } else {
                Node n = this;
                while (n.parent != null && n == n.parent.right) {
                    n = n.parent;
                }
                return n.parent;
            }
        }
    }
}

然后,您可以有一个这样的测试工具:

static Node C(int key, Node left, Node right) {
    return new Node(key, left, right);
}
static Node X(int key)             { return C(key, null, null);  }
static Node L(int key, Node left)  { return C(key, left, null);  }
static Node R(int key, Node right) { return C(key, null, right); }
public static void main(String[] args) {
    Node n =
        C(8,
            C(3,
                X(1),
                C(6,
                    X(4),
                    X(7)
                )
            ),
            R(10,
                L(14,
                    X(13)
                )
            )
        );
    Node current = n.getLeftMost();
    while (current != null) {
        System.out.print(current.key + " ");
        current = current.getNext();
    }
}

这打印:

1 3 4 6 7 8 10 13 14 

另请参见


答案 2

你能把它改成迭代而不是递归吗?

您可以使用显式堆栈。伪代码:

private static void iterateall(BinaryTree foo) {
    Stack<BinaryTree> nodes = new Stack<BinaryTree>();
    nodes.push(foo);
    while (!nodes.isEmpty()) {
        BinaryTree node = nodes.pop();
        if (node == null)
            continue;
        System.out.println(node.node);
        nodes.push(node.right);
        nodes.push(node.left);
    }
}

但这并不真正优于递归代码(除了代码中缺少的基本条件)。