it-swarm-vi.com

Trình lặp theo thứ tự cho cây nhị phân

Làm cách nào tôi có thể viết a Java iterator (nghĩa là cần các phương thức nexthasNext) lấy gốc của cây nhị phân và lặp qua các nút của cây nhị phân trong theo thứ tự thời trang?

24
Paul S.

Yếu tố đầu tiên của cây con luôn là yếu tố ngoài cùng bên trái. Phần tử tiếp theo sau một phần tử là phần tử đầu tiên của cây con bên phải của nó. Nếu phần tử không có con đúng, phần tử tiếp theo là tổ tiên bên phải đầu tiên của phần tử. Nếu phần tử không có con đúng hay tổ tiên đúng, thì đó là phần tử ngoài cùng bên phải và nó là phần cuối cùng trong lần lặp.

Tôi hy vọng mã của tôi là con người có thể đọc được và bao gồm tất cả các trường hợp.

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

Hãy xem xét cây sau:

     d
   /   \
  b     f
 / \   / \
a   c e   g
  • Phần tử đầu tiên là "hoàn toàn rời khỏi gốc"
  • a không có con phải, vì vậy phần tử tiếp theo là "lên cho đến khi bạn đến từ trái"
  • b không có con đúng, vì vậy lặp lại b cây con đúng
  • c không có con đúng. Đó là cha mẹ của nó là b, đã được duyệt qua. Cha mẹ tiếp theo là d, chưa được duyệt, vì vậy hãy dừng ở đây.
  • d có một cây con đúng. Phần tử ngoài cùng bên trái của nó là e.
  • ...
  • g không có cây con đúng, vì vậy hãy đi lên. f đã được truy cập, vì chúng tôi đến từ bên phải. d đã được truy cập. d không có cha mẹ, vì vậy chúng tôi không thể tiến lên. Chúng tôi đã đến từ nút ngoài cùng bên phải và chúng tôi đã hoàn thành việc lặp lại.
39
John Dvorak

Để có được mục tiếp theo, 'nextEntry ()', đối với trình vòng lặp, tôi đã xem các đoạn trích từ Java.util.TreeMap dán bên dưới. Nói một cách dễ hiểu, tôi muốn nói rằng bạn chắc chắn rằng nút gốc không phải là null trước tiên trả về null. Nếu không, vist nút bên phải nếu nó không null. Sau đó truy cập bên trái (nếu không null) và truy cập bên trái liên tục trong một vòng lặp cho đến khi nhấn null. Nếu nút bên phải ban đầu là null thì thay vì tất cả, hãy truy cập nút cha nếu đó không phải là null. Bây giờ, hãy nhập một vòng lặp while trong đó bạn kiểm tra cha mẹ cho đến khi nó là null hoặc nút mà bạn hiện đang truy cập có nút bên phải (con) bằng với vị trí cuối cùng của bạn. Bây giờ trả lại bất cứ mục nào bạn đang xem. Không thực hiện được tất cả các tùy chọn đó, trả về nút gốc (gốc). 'HasNext ()' chỉ kiểm tra xem "mục tiếp theo" mà bạn đang trả lại có phải là null hay không.

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

final TreeMap.Entry<K,V> nextEntry() {
    TreeMap.Entry<K,V> e = next;
    if (e == null || e.key == fenceKey)
        throw new NoSuchElementException();
    if (m.modCount != expectedModCount)
        throw new ConcurrentModificationException();
    next = successor(e);
    lastReturned = e;
    return e;
}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}
2
apcris