Melintasi Pokok

Dalam tutorial ini, anda akan belajar mengenai teknik melintasi pokok yang berbeza. Anda juga akan dapati contoh kerja kaedah melintasi pokok yang berbeza di C, C ++, Java dan Python.

Melintasi pokok bermaksud mengunjungi setiap simpul di pokok. Anda mungkin, misalnya, ingin menambahkan semua nilai dalam pokok atau mencari nilai yang paling besar. Untuk semua operasi ini, anda perlu melawat setiap simpul pokok.

Struktur data linier seperti tatasusunan, tumpukan, barisan, dan senarai terpaut hanya mempunyai satu cara untuk membaca data. Tetapi struktur data hierarki seperti pokok dapat dilalui dengan cara yang berbeza.

Melintasi pokok

Mari fikirkan bagaimana kita dapat membaca unsur-unsur pokok dalam gambar yang ditunjukkan di atas.

Bermula dari atas, Kiri ke kanan

 1 -> 12 -> 5 -> 6 -> 9

Bermula dari bawah, Kiri ke kanan

 5 -> 6 -> 12 -> 9 -> 1

Walaupun proses ini agak mudah, proses ini tidak menghormati hierarki pokok, hanya kedalaman simpul.

Sebaliknya, kami menggunakan kaedah melintasi yang mengambil kira struktur asas pokok iaitu

 struct node ( int data; struct node* left; struct node* right; )

Nod struktur yang ditunjukkan oleh kiri dan kanan mungkin mempunyai anak kiri dan kanan yang lain jadi kita harus menganggapnya sebagai sub-pokok dan bukan sub-nod.

Menurut struktur ini, setiap pokok adalah gabungan dari

  • Nod membawa data
  • Dua pokok kecil
Subtree Kiri dan Kanan

Ingat bahawa tujuan kami adalah untuk melawat setiap nod, jadi kami perlu melawat semua nod di subtree, lawati simpul root dan lawati semua node di subtree kanan juga.

Bergantung pada urutan di mana kita melakukan ini, terdapat tiga jenis traversal.

Melintang dalam

  1. Pertama, lawati semua nod di subtree kiri
  2. Kemudian nod akar
  3. Lawati semua nod di subtree kanan
 inorder(root->left) display(root->data) inorder(root->right)

Preorder melintasi

  1. Lawati nod akar
  2. Lawati semua nod di subtree kiri
  3. Lawati semua nod di subtree kanan
 display(root->data) preorder(root->left) preorder(root->right)

Melintasi pasca pesanan

  1. Lawati semua nod di subtree kiri
  2. Lawati semua nod di subtree kanan
  3. Lawati nod akar
 postorder(root->left) postorder(root->right) display(root->data)

Mari kita gambarkan traversal dalam urutan. Kami bermula dari simpul akar.

Subtree Kiri dan Kanan

Kami melintasi subtree kiri terlebih dahulu. Kita juga perlu ingat untuk mengunjungi simpul akar dan subtree yang betul semasa pokok ini selesai.

Mari letakkan semua ini dalam timbunan agar kita ingat.

Timbunan

Sekarang kita melintasi subtree yang ditunjukkan di bahagian atas timbunan.

Sekali lagi, kami mengikuti peraturan inorder yang sama

 Subtree kiri -> root -> subtree kanan

Setelah melintasi subtree kiri, kita ditinggalkan

Tumpuan Akhir

Oleh kerana node "5" tidak mempunyai subtrees, kami mencetaknya secara langsung. Selepas itu kami mencetak induknya "12" dan kemudian anak yang tepat "6".

Menempatkan semuanya di timbunan sangat membantu kerana sekarang subtree kiri dari simpul akar telah dilalui, kita dapat mencetaknya dan pergi ke subtree kanan.

Setelah melalui semua elemen, kita dapat melintasi inorder sebagai

 5 -> 12 -> 6 -> 1 -> 9

Kita tidak perlu membuat timbunan sendiri kerana rekursi mengekalkan urutan yang betul untuk kita.

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

Artikel menarik...