如何迭代二叉树？

Question

现在我

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

可以将其更改为迭代而不是递归吗？

Answer 1

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

它的定义方式如下：

• 第一条规则：树中的第一个节点是树中最左边的节点。
• 下一条规则：节点的后继者是：
  • Next-R规则：如果有右子树，则为右子树中最左边的节点。
  • Next-U规则：否则，向上遍历树
    • 如果右转（即该节点是左子节点），则该父节点是后继节点
    • 如果左转（即该节点是右子节点），请继续向上。
    • 如果你不能再往上走，那就没有继任者

正如你所看到的，要使其工作，你需要一个父节点指针。

---

示例：

• 第一个规则：树中的第一个节点是树中最左边的节点：(1)
• Next-U 规则：自 (1)< /code> 没有右子树，我们转到 (3)。这是右转，因此 (3) 是下一个。
• Next-R 规则：由于 (3) 有一个右子树，因此该子树中最左边的节点是下一个：(4)。
• Next-U 规则：由于 (4) 没有右子树，因此我们转到 (6)。这是右转，所以接下来是(6)。
• Next-R 规则：由于 (6) 有一个右子树，因此该子树中最左边的节点是下一个：(7)。
• Next-U 规则：由于 (7) 没有右子树，因此我们转到 (6)。这是左转，因此我们继续前往 (3)。这是左转，因此我们继续前往 (8)。这是右转，所以接下来是(8)。
• Next-R 规则：由于 (8) 有一个右子树，因此该子树中最左边的节点是下一个：(10)。
• Next-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 

另请参阅

• Complete Java ideone.com 上的列表和输出

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

但这并不比递归代码真正优越（除了代码中缺少基本条件）。

Answer 3

当然，您有两种通用算法，深度优先搜索和广度优先搜索。

如果遍历顺序对你来说不重要，那么先考虑广度，这样迭代更容易实现。你的算法应该看起来像这样。

LinkedList queue = new LinkedList();

queue.add(root);

while (!queue.isEmpty()){
    Object element = queue.remove();

    queue.add(element.left);
    queue.add(element.right);

    // Do your processing with element;
}

Answer 4

与每次递归一样，您可以使用额外的数据结构 - 即堆栈。
解决方案的草图：

private static void visitall(BinaryTree foo) {
  Stack<BinaryTree> iterationStack = new Stack<BinaryTree>();
  iterationStack.push(foo);

  while (!iterationStack.isEmpty()) {
      BinaryTree current = iterationStack.pop();
      System.out.println(current.node);
      current.push(current.right);        // NOTE! The right one comes first
      current.push(current.left);
   }

}

Answer 5

我有一棵树（不是二叉树）并最终用这个非常简单的算法解决了它。其他解决方案使用的左和右与示例无关，甚至没有实现。

我的结构是：每个父节点都包含子节点列表，每个子节点都包含一个指向父节点的指针。很常见...

经过一系列重构后，我使用 Kotlin 提出了以下示例。转换为您选择的语言应该很简单。

辅助函数

首先，节点必须提供 2 个简单的函数。这将根据您的 Node 类的实现而有所不同：

leftMost - 这是第一个子节点。如果该节点有子节点，则它是第一个子节点，依此类推。如果没有子节点，则返回 this。

fun leftMost(): Node {
        if (children.isEmpty()) {
            return this
        }
        var n = this
        while (n.children.isNotEmpty()) {
            n = n.children[0]
        }
        return n
}

nextSibling - 该节点的下一个兄弟节点，或 NULL

fun nextSibling(): Node? {
    if (parent == null) return null
    val siblingIndex = parent.children.indexOf(this) + 1
    return if (siblingIndex < parent.children.size) {
        parent.children[siblingIndex]
    } else {
        null
    }
}

迭代

迭代从根的最左边开始。

然后检查下一个兄弟姐妹。

• 如果 NOT NULL，则为同级的 leftMostChild；
• 如果为 NULL，则为父级；如果父级为 NULL，则完成。

就是这样。

这是一个 Kotlin 迭代器函数。

fun iterator(): Iterator<Node> {
    var next: Node? = this.leftMost()

    return object : Iterator<Node> {

        override fun hasNext(): Boolean {
            return next != null
        }

        override fun next(): Node {
            val ret = next ?: throw NoSuchElementException()
            next = ret.nextSibling()?.leftMost() ?: ret.parent
            return ret
        }
    }
}

这是相同的 next() 函数，但对于那些不熟悉语法的人来说，没有处理 NULL 值的 Kotlin 简写。

fun next(): Node {
    val ret = next
    if (ret == null) throw NoSuchElementException()
    val nextSibling = ret.nextSibling()
    if (nextSibling != null) {
        next = nextSibling.leftMost()
    }
    else {
        next = ret.parent
    }
    return ret
}

Answer 6

是的，您可以将其更改为迭代而不是递归，但是这样会变得更加复杂，因为您需要有某种方法来记住从当前节点返回的位置。在递归情况下，Java 调用堆栈会处理该问题，但在迭代解决方案中，您需要构建自己的堆栈，或者可能在节点中存储反向指针。