Koku šķērsošana

Šajā apmācībā jūs uzzināsit par dažādām koku šķērsošanas metodēm. Jūs atradīsit arī dažādu koku šķērsošanas metožu piemērus C, C ++, Java un Python.

Pārbraukt kokā nozīmē apmeklēt visus koka mezglus. Piemēram, jūs varētu vēlēties pievienot visas vērtības kokā vai atrast lielāko vērtību. Veicot visas šīs darbības, jums būs jāapmeklē katrs koka mezgls.

Lineārām datu struktūrām, piemēram, masīviem, kaudzēm, rindām un saistītajam sarakstam, ir tikai viens veids, kā lasīt datus. Bet hierarhisku datu struktūru, piemēram, koku, var šķērsot dažādi.

Koku šķērsošana

Padomāsim par to, kā mēs varam izlasīt koka elementus attēlā, kas parādīts iepriekš.

Sākot no augšas, no kreisās uz labo

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

Sākot no apakšas, no kreisās uz labo

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

Lai gan šis process ir nedaudz viegls, tas neievēro koka hierarhiju, tikai mezglu dziļumu.

Tā vietā mēs izmantojam šķērsošanas metodes, kas ņem vērā koka pamatstruktūru, ti

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

Strukturālajā mezglā, uz kuru norāda kreisā un labā puse, varētu būt citi kreisie un labie bērni, tāpēc mums tie būtu jādomā kā par apakkokiem, nevis apakšmezgliem.

Saskaņā ar šo struktūru katrs koks ir kombinācija

  • Mezgls, kas ved datus
  • Divi apakškoki
Kreisais un labais apakškoks

Atcerieties, ka mūsu mērķis ir apmeklēt katru mezglu, tāpēc mums jāapmeklē visi apakškoka mezgli, jāapmeklē saknes mezgls un jāapmeklē visi mezgli arī labajā apakškokā.

Atkarībā no kārtības, kādā mēs to darām, var būt trīs šķērsošanas veidi.

Iekšējā šķērsošana

  1. Vispirms apmeklējiet visus mezglus kreisajā apakškokā
  2. Tad saknes mezgls
  3. Apmeklējiet visus mezglus labajā apakškokā
 inorder(root->left) display(root->data) inorder(root->right)

Iepriekš pasūtīt šķērsošanu

  1. Apmeklējiet saknes mezglu
  2. Apmeklējiet visus mezglus kreisajā apakškokā
  3. Apmeklējiet visus mezglus labajā apakškokā
 display(root->data) preorder(root->left) preorder(root->right)

Pasta pasūtījuma šķērsošana

  1. Apmeklējiet visus mezglus kreisajā apakškokā
  2. Apmeklējiet visus mezglus labajā apakškokā
  3. Apmeklējiet saknes mezglu
 postorder(root->left) postorder(root->right) display(root->data)

Vizualizēsim kārtīgu šķērsošanu. Mēs sākam no saknes mezgla.

Kreisais un labais apakškoks

Vispirms mēs šķērsojam kreiso apakškoku. Kad šis koks ir pabeigts, mums arī jāatceras apmeklēt saknes mezglu un labo apakškoku.

Saliksim to visu kaudzē, lai atcerētos.

Kaudze

Tagad mēs šķērsojam apakšgrupu, kas norādīta kaudzes augšpusē.

Atkal mēs ievērojam to pašu kārtību

 Kreisais apakškoks -> sakne -> labais apakškoks

Pēc šķērsošanas pa kreiso apakškoku mums paliek

Galīgā kaudze

Tā kā mezglā "5" nav apakškoku, mēs to tieši izdrukājam. Pēc tam mēs izdrukājam tā vecāku "12" un pēc tam pareizo bērnu "6".

Visu salikšana uz kaudzes bija noderīga, jo tagad, kad saknes mezgla kreisā apakškoks ir šķērsots, mēs to varam izdrukāt un doties uz labo apakškoku.

Izgājuši visus elementus, mēs iegūstam iekšējo šķērsošanu kā

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

Mums pašiem nav jāizveido kaudze, jo rekursija uztur mums pareizo secību.

Python, Java un C / C ++ piemēri

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

Interesanti raksti...