Dalam tutorial ini, Anda akan belajar tentang berbagai teknik penjelajahan pohon. Selain itu, Anda akan menemukan contoh kerja dari metode penjelajahan pohon yang berbeda di C, C ++, Java dan Python.
Melintasi pohon berarti mengunjungi setiap simpul di pohon. Anda mungkin, misalnya, ingin menambahkan semua nilai pada pohon atau mencari yang terbesar. Untuk semua operasi ini, Anda perlu mengunjungi setiap node pada pohon.
Struktur data linier seperti array, tumpukan, antrian, dan daftar tertaut hanya memiliki satu cara untuk membaca data. Tetapi struktur data hierarkis seperti pohon dapat dilintasi dengan cara yang berbeda.
Penjelajahan pohon
Mari kita pikirkan tentang bagaimana kita bisa membaca elemen pohon pada gambar yang ditunjukkan di atas.
Mulai dari atas, Kiri ke kanan
1 -> 12 -> 5 -> 6 -> 9
Mulai dari bawah, Kiri ke kanan
5 -> 6 -> 12 -> 9 -> 1
Meskipun proses ini agak mudah, ini tidak menghormati hierarki pohon, hanya kedalaman node.
Sebagai gantinya, kami menggunakan metode traversal yang memperhitungkan struktur dasar pohon, yaitu
struct node ( int data; struct node* left; struct node* right; )
Simpul struct yang ditunjukkan oleh kiri dan kanan mungkin memiliki anak kiri dan kanan lainnya jadi kita harus menganggapnya sebagai sub-pohon daripada sub-simpul.
Menurut struktur ini, setiap pohon adalah kombinasi dari
- Sebuah node membawa data
- Dua pohon subpohon
Subpohon Kiri dan Kanan
Ingatlah bahwa tujuan kita adalah mengunjungi setiap node, jadi kita perlu mengunjungi semua node di subtree, mengunjungi node root, dan mengunjungi semua node di subtree kanan juga.
Bergantung pada urutan kami melakukan ini, bisa ada tiga jenis traversal.
Traversal inorder
- Pertama, kunjungi semua node di subtree kiri
- Kemudian simpul akar
- Kunjungi semua node di subtree kanan
inorder(root->left) display(root->data) inorder(root->right)
Preorder traversal
- Kunjungi node root
- Kunjungi semua node di subtree kiri
- Kunjungi semua node di subtree kanan
display(root->data) preorder(root->left) preorder(root->right)
Traversal pasca pesanan
- Kunjungi semua node di subtree kiri
- Kunjungi semua node di subtree kanan
- Kunjungi simpul akar
postorder(root->left) postorder(root->right) display(root->data)
Mari kita visualisasikan traversal berurutan. Kami mulai dari simpul akar.
Subpohon Kiri dan Kanan
Kami melintasi subtree kiri terlebih dahulu. Kita juga perlu mengingat untuk mengunjungi simpul akar dan subpohon kanan ketika pohon ini selesai.
Mari kita taruh semua ini dalam satu tumpukan agar kita ingat.
Tumpukan
Sekarang kita melintasi subpohon yang menunjuk ke TOP tumpukan.
Sekali lagi, kami mengikuti aturan inorder yang sama
Subpohon kiri -> akar -> subtree kanan
Setelah melintasi subtree kiri, kita mendapatkan
Tumpukan Terakhir
Karena node "5" tidak memiliki subpohon, kami mencetaknya secara langsung. Setelah itu kita cetak induknya "12" dan kemudian anak kanannya "6".
Menempatkan semuanya di tumpukan sangat membantu karena sekarang setelah subpohon kiri dari simpul akar telah dilintasi, kita dapat mencetaknya dan pergi ke subpohon kanan.
Setelah melalui semua elemen, kita mendapatkan inorder traversal sebagai
5 -> 12 -> 6 -> 1 -> 9
Kami tidak harus membuat tumpukan sendiri karena rekursi mempertahankan urutan yang benar untuk kami.
Contoh Python, Java dan C / C ++
Python Java C C + # Tree traversal in Python class Node: def __init__(self, item): self.left = None self.right = None self.val = item def inorder(root): if root: # Traverse left inorder(root.left) # Traverse root print(str(root.val) + "->", end='') # Traverse right inorder(root.right) def postorder(root): if root: # Traverse left postorder(root.left) # Traverse right postorder(root.right) # Traverse root print(str(root.val) + "->", end='') def preorder(root): if root: # Traverse root print(str(root.val) + "->", end='') # Traverse left preorder(root.left) # Traverse right preorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Inorder traversal ") inorder(root) print("Preorder traversal ") preorder(root) print("Postorder traversal ") postorder(root)
// Tree traversal in Java class Node ( int item; Node left, right; public Node(int key) ( item = key; left = right = null; ) ) class BinaryTree ( // Root of Binary Tree Node root; BinaryTree() ( root = null; ) void postorder(Node node) ( if (node == null) return; // Traverse left postorder(node.left); // Traverse right postorder(node.right); // Traverse root System.out.print(node.item + "->"); ) void inorder(Node node) ( if (node == null) return; // Traverse left inorder(node.left); // Traverse root System.out.print(node.item + "->"); // Traverse right inorder(node.right); ) void preorder(Node node) ( if (node == null) return; // Traverse root System.out.print(node.item + "->"); // Traverse left preorder(node.left); // Traverse right preorder(node.right); ) public static void main(String() args) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("Inorder traversal"); tree.inorder(tree.root); System.out.println("Preorder traversal "); tree.preorder(tree.root); System.out.println("Postorder traversal"); tree.postorder(tree.root); ) )
// Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // preorderTraversal traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // postorderTraversal traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
// Tree traversal in C++ #include using namespace std; struct Node ( int data; struct Node *left, *right; Node(int data) ( this->data = data; left = right = NULL; ) ); // Preorder traversal void preorderTraversal(struct Node* node) ( if (node == NULL) return; cout left); preorderTraversal(node->right); ) // Postorder traversal void postorderTraversal(struct Node* node) ( if (node == NULL) return; postorderTraversal(node->left); postorderTraversal(node->right); cout left); cout right); ) int main() ( struct Node* root = new Node(1); root->left = new Node(12); root->right = new Node(9); root->left->left = new Node(5); root->left->right = new Node(6); cout << "Inorder traversal "; inorderTraversal(root); cout << "Preorder traversal "; preorderTraversal(root); cout << "Postorder traversal "; postorderTraversal(root);
