Jika node di pohon pencarian biner memiliki pointer kembali ke node induknya, apakah mungkin untuk melakukan traversal dalam orde tanpa perlu rekursi atau struktur data tambahan?

0
nish91 5 April 2021, 17:41

3 jawaban

Jawaban Terbaik

Pantau simpul sebelumnya selama traversal, yang akan membantu memutuskan ke mana lagi.

Di C #:

class Node {
    /* ... */
    public void inorder() {
        Node curr = this;
        Node prev = null;
        Node next = null;
        while (curr != null) {
            if (curr.right != null && prev == curr.right) {
                next = curr.parent;
            } else if (curr.left == null || prev == curr.left) {
                Console.WriteLine(curr.data);  // <-- visit the node.
                next = curr.right != null ? curr.right : curr.parent;
            } else {
                next = curr.left;
            }
            prev = curr;
            curr = next;
        }
    }
};

Di C ++ bisa terlihat seperti ini:

void inorder(Node* root) {
    Node * curr = root;
    Node * prev = NULL;
    Node * next = NULL;
    while (curr != NULL) {
        if (curr->right != NULL && prev == curr->right) {
            next = curr->parent;
        } else if (curr->left == NULL || prev == curr->left) {
            cout << curr->data << " ";  // <-- visit the node.
            next = curr->right != NULL ? curr->right : curr->parent;
        } else {
            next = curr->left;
        }
        prev = curr;
        curr = next;
    }
    cout << "\n";
}
1
trincot 5 April 2021, 19:45

Untuk mendapatkan node pertama, Anda baru saja mulai dari root dan pergi ke kiri sejauh mungkin.

Untuk mendapatkan dari node apa pun ke yang berikutnya:

  • Jika node memiliki anak yang tepat, lalu pergi, lalu belok kiri sejauh mungkin.
  • Kalau tidak, ikuti petunjuk orang tua sampai Anda sampai ke nenek moyang di sebelah kanan (mis., Anda sampai di sana dari anak kiri)

Anda selesai ketika Anda naik dari root.

0
Matt Timmermans 5 April 2021, 15:19

Ini adalah contoh kecil.

Map<TreeNode,TreeNode> parent; // available 

Set<TreeNode> set = new HashSet<>(); // maintain visited nodes

TreeNode curr = root;

while(curr!=null){

  if(!set.contains(curr.left) && curr.left!=null){
     curr = curr.left;
  }else if(!set.contains(curr.right) && curr.right!=null){
     System.out.print(curr.value+" ");
     curr = curr.right;
  }else{
     if(curr.right==null){
        System.out.print(curr.value+" ");
     }
     set.add(curr); // mark it as completely visited
     curr = parent.get(curr);
  }
}
0
Maruthi Adithya 5 April 2021, 16:51