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

Question

Làm cách nào để viết một trình lặp Java (tức là cần các phương thức next và hasNext) 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 ?

Answer 1

Yếu tố đầu tiên của cây con luôn là phần tử ngoài cùng bên trái. Phần tử tiếp theo sau 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 đầu tiên của phần tử. Nếu phần tử không có đúng con hoặc tổ tiên đúng, nó là phần tử ngoài cùng bên phải và nó là phần tử cuối cùng trong lần lặp.

Tôi hy vọng mã của tô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 những cây sau đây:

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

• Yếu tố đầu tiên là "hoàn toàn trái từ gốc"
• a không có một đứa con đúng, vì vậy các yếu tố tiếp theo là "lên cho đến khi bạn đến từ bên trái "
• b không có con phù hợp, do đó hãy lặp lại b 's subtree phải
• c không có con phù hợp. Đó là phụ huynh là b, đã được duyệt qua. Phụ huynh kế tiếp là d, chưa được duyệt qua, vì vậy hãy dừng ở đây.
• d có một cây con phù hợp. Phần tử ngoài cùng bên trái của nó là e.
• ...
• g không có cây con phù hợp, vì vậy hãy đi bộ. 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ể di chuyển xa hơn. Chúng tôi đã đến từ nút ngoài cùng bên phải và chúng tôi đã thực hiện lặp lại.

Answer 2

Nó khá thẳng về phía trước, cho traversal trong trật tự mà bạn đến thăm con trái nếu có một, sau đó nút gốc, thì đứa trẻ phải:

visit_node(node) 
    if node.left: visit_node(node.left) 
    // visit the root node 
    if node.right: visit_node(node.right) 

Diagram:

 a 
/ \  (in-order traversal would give bac) 
    b  c 

Answer 3

Để có được mục nhập tiếp theo, 'nextEntry()', cho trình vòng lặp, tôi đã xem các đoạn mã từ java.util.TreeMap được dán bên dưới. Trong tiếng Anh đơn giản, 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 đầu tiên trả về null. Nếu không, hãy nhấn nút phải nếu nó không phải là null. Sau đó, truy cập vào bên trái (nếu không null) và ghé thăm của một trong những trái liên tục trong một vòng lặp trong khi 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 nó không phải là null. Bây giờ nhập một vòng lặp while, nơi bạn vist cha mẹ cho đến khi nó hoặc là null hoặc nút bạn đang truy cập có nút phải (con) của nó bằng với vị trí cuối cùng của bạn. Bây giờ trả lại bất kỳ mục nhập nào bạn đang truy cập. Không thực hiện tất cả các tùy chọn đó, hãy trả về nút gốc (gốc). 'HasNext()' chỉ kiểm tra nếu "mục nhập tiếp theo" bạn đang trả về 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; 
    } 
}