二叉树的有序迭代器 [英] In-order iterator for binary tree

问题描述

如何编写Java迭代器（即需要 next 和 hasNext 方法）二进制树并以按顺序方式遍历二叉树的节点？

How can I write a Java iterator (i.e. needs the next and hasNext methods) that takes the root of a binary tree and iterates through the nodes of the binary tree in in-order fashion?

推荐答案

子树的第一个元素始终是最左边的元素。元素之后的下一个元素是其右子树的第一个元素。如果元素没有正确的子元素，则下一个元素是元素的第一个右祖先。如果元素既没有右子也没有右祖先，它是最右边的元素，它是迭代中的最后一个元素。

The first element of a subtree is always the leftmost one. The next element after an element is the first element of its right subtree. If the element does not have a right child, the next element is the element's first right ancestor. If the element has neither a right child nor a right ancestor, it is the rightmost element and it's last in iteration.

我希望我的代码是人类可读的，涵盖所有情况。

I hope my code is human readable and covers all cases.

public class TreeIterator {
    private Node next;

    public TreeIterator(Node root) {
        next = root;
        if(next == null)
            return;

        while (next.left != null)
           next = next.left;
    }

    public boolean hasNext(){
        return next != null;
    }

    public Node next(){
        if(!hasNext()) throw new NoSuchElementException();
        Node r = next;

        // If you can walk right, walk right, then fully left.
        // otherwise, walk up until you come from left.
        if(next.right != null) {
            next = next.right;
            while (next.left != null)
                next = next.left;
            return r;
        }

        while(true) {
            if(next.parent == null) {
                next = null;
                return r;
            }
            if(next.parent.left == next) {
                next = next.parent;
               return r;
            }
            next = next.parent;
        }
     }
 }

考虑以下树：

     d
   /   \
  b     f
 / \   / \
a   c e   g

• 第一个元素是完全离开根


• a 没有合适的孩子，所以下一个元素是直到你从左边来


• b 确实有一个正确的孩子，所以迭代 b 的右子树


• c 没有合适的孩子。它的父级是 b ，已遍历。下一个父级是 d ，尚未遍历，所以请在此处停止。


• d 有一个正确的子树。它最左边的元素是 e 。


• ...


• g 没有正确的子树，所以走吧。因为我们来自右边，所以已经访问过 f 。已访问 d 。 d 没有父母，所以我们无法继续前进。我们来自最右边的节点，我们已经完成迭代。


• The first element is "fully left from the root"
• a does not have a right child, so the next element is "up until you come from left"
• b does have a right child, so iterate b's right subtree
• c does not have a right child. It's parent is b, which has been traversed. The next parent is d, which has not been traversed, so stop here.
• d has a right subtree. Its leftmost element is e.
• ...
• g has no right subtree, so walk up. f has been visited, since we've come from right. d has been visited. d has no parent, so we cannot move further up. We have come from the rightmost node and we're done iterating.

这篇关于二叉树的有序迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！