Doorkruisen van bomen

In deze tutorial leer je over verschillende technieken voor het doorlopen van bomen. Ook vindt u werkende voorbeelden van verschillende methoden voor het doorlopen van bomen in C, C ++, Java en Python.

Een boom doorkruisen betekent elk knooppunt in de boom bezoeken. U kunt bijvoorbeeld alle waarden in de boomstructuur toevoegen of de grootste zoeken. Voor al deze bewerkingen moet u elk knooppunt van de structuur bezoeken.

Lineaire gegevensstructuren zoals arrays, stapels, wachtrijen en gekoppelde lijsten hebben maar één manier om de gegevens te lezen. Maar een hiërarchische gegevensstructuur zoals een boom kan op verschillende manieren worden doorlopen.

Doorkruisen van bomen

Laten we eens kijken hoe we de elementen van de boom in de bovenstaande afbeelding kunnen lezen.

Beginnend van boven, van links naar rechts

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

Beginnend van beneden, van links naar rechts

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

Hoewel dit proces enigszins eenvoudig is, respecteert het niet de hiërarchie van de boom, alleen de diepte van de knooppunten.

In plaats daarvan gebruiken we traversale methoden die rekening houden met de basisstructuur van een boom, dwz

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

Het struct-knooppunt waarnaar links en rechts verwijzen, kan andere linker- en rechterkinderen hebben, dus we moeten ze beschouwen als subbomen in plaats van subknooppunten.

Volgens deze structuur is elke boom een ​​combinatie van

  • Een knooppunt met gegevens
  • Twee substructuren
Links en rechts subboom

Onthoud dat het ons doel is om elk knooppunt te bezoeken, dus we moeten alle knooppunten in de substructuur bezoeken, het hoofdknooppunt bezoeken en ook alle knooppunten in de rechter substructuur bezoeken.

Afhankelijk van de volgorde waarin we dit doen, kunnen er drie soorten traversal zijn.

In volgorde doorlopen

  1. Bezoek eerst alle knooppunten in de linker substructuur
  2. Dan het root-knooppunt
  3. Bezoek alle knooppunten in de rechter substructuur
 inorder(root->left) display(root->data) inorder(root->right)

Doorloop reserveren

  1. Bezoek het hoofdknooppunt
  2. Bezoek alle knooppunten in de linker substructuur
  3. Bezoek alle knooppunten in de rechter substructuur
 display(root->data) preorder(root->left) preorder(root->right)

Traversal postorder

  1. Bezoek alle knooppunten in de linker substructuur
  2. Bezoek alle knooppunten in de rechter substructuur
  3. Bezoek het hoofdknooppunt
 postorder(root->left) postorder(root->right) display(root->data)

Laten we in-order traversal visualiseren. We beginnen vanaf het hoofdknooppunt.

Links en rechts subboom

We doorlopen eerst de linker substructuur. We moeten ook onthouden om het hoofdknooppunt en de juiste substructuur te bezoeken wanneer deze boom is voltooid.

Laten we dit allemaal op een stapel leggen, zodat we het ons herinneren.

Stapel

Nu gaan we naar de substructuur die op de BOVENKANT van de stapel wijst.

Nogmaals, we volgen dezelfde regel van volgorde

 Linker substructuur -> root -> rechter substructuur

Nadat we de linker substructuur hebben doorlopen, blijven we met

Laatste stapel

Omdat het knooppunt "5" geen substructuren heeft, printen we het direct. Daarna printen we de ouder "12" en dan het juiste kind "6".

Alles op een stapel plaatsen was handig, want nu de linker substructuur van de root-node is doorlopen, kunnen we het afdrukken en naar de rechter substructuur gaan.

Nadat we alle elementen hebben doorlopen, krijgen we de in volgorde doorlopen als

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

We hoeven de stapel niet zelf te maken, omdat recursie voor ons de juiste volgorde houdt.

Python, Java en C / C ++ voorbeelden

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

Interessante artikelen...