In diesem Tutorial lernen Sie verschiedene Baumdurchquerungstechniken kennen. Außerdem finden Sie Arbeitsbeispiele für verschiedene Baumdurchlaufmethoden in C, C ++, Java und Python.
Das Durchqueren eines Baums bedeutet, jeden Knoten im Baum zu besuchen. Möglicherweise möchten Sie beispielsweise alle Werte im Baum hinzufügen oder den größten finden. Für all diese Vorgänge müssen Sie jeden Knoten des Baums besuchen.
Lineare Datenstrukturen wie Arrays, Stapel, Warteschlangen und verknüpfte Listen bieten nur eine Möglichkeit, die Daten zu lesen. Eine hierarchische Datenstruktur wie ein Baum kann jedoch auf unterschiedliche Weise durchlaufen werden.
Baumdurchquerung
Lassen Sie uns darüber nachdenken, wie wir die Elemente des Baums im oben gezeigten Bild lesen können.
Von oben nach links
1 -> 12 -> 5 -> 6 -> 9
Von unten nach links
5 -> 6 -> 12 -> 9 -> 1
Obwohl dieser Vorgang etwas einfach ist, wird die Hierarchie des Baums nicht berücksichtigt, sondern nur die Tiefe der Knoten.
Stattdessen verwenden wir Traversal-Methoden, die die Grundstruktur eines Baums berücksichtigen, d. H.
struct node ( int data; struct node* left; struct node* right; )
Der Strukturknoten, auf den links und rechts zeigen, kann andere linke und rechte untergeordnete Knoten haben, daher sollten wir sie als Unterbäume anstelle von Unterknoten betrachten.
Nach dieser Struktur ist jeder Baum eine Kombination aus
- Ein Knoten, der Daten trägt
- Zwei Teilbäume
Linker und rechter Teilbaum
Denken Sie daran, dass unser Ziel darin besteht, jeden Knoten zu besuchen. Daher müssen wir alle Knoten im Teilbaum besuchen, den Stammknoten besuchen und auch alle Knoten im rechten Teilbaum besuchen.
Abhängig von der Reihenfolge, in der wir dies tun, kann es drei Arten der Durchquerung geben.
Inorder Traversal
- Besuchen Sie zunächst alle Knoten im linken Teilbaum
- Dann der Wurzelknoten
- Besuchen Sie alle Knoten im rechten Teilbaum
inorder(root->left) display(root->data) inorder(root->right)
Durchlauf vorbestellen
- Besuchen Sie den Stammknoten
- Besuchen Sie alle Knoten im linken Teilbaum
- Besuchen Sie alle Knoten im rechten Teilbaum
display(root->data) preorder(root->left) preorder(root->right)
Nachbestellungsdurchquerung
- Besuchen Sie alle Knoten im linken Teilbaum
- Besuchen Sie alle Knoten im rechten Teilbaum
- Besuchen Sie den Stammknoten
postorder(root->left) postorder(root->right) display(root->data)
Lassen Sie uns die Durchquerung in der richtigen Reihenfolge visualisieren. Wir beginnen am Wurzelknoten.
Linker und rechter Teilbaum
Wir durchqueren zuerst den linken Teilbaum. Wir müssen auch daran denken, den Stammknoten und den richtigen Teilbaum zu besuchen, wenn dieser Baum fertig ist.
Lassen Sie uns das alles auf einen Stapel legen, damit wir uns erinnern.
Stapel
Nun gehen wir zu dem Teilbaum, der oben auf dem Stapel liegt.
Auch hier folgen wir der gleichen Inorder-Regel
Linker Teilbaum -> Wurzel -> rechter Teilbaum
Nachdem wir den linken Teilbaum durchlaufen haben, bleiben wir mit
Final Stack
Da der Knoten "5" keine Teilbäume hat, drucken wir ihn direkt. Danach drucken wir das übergeordnete "12" und dann das rechte untergeordnete "6".
Es war hilfreich, alles auf einen Stapel zu legen, da der linke Teilbaum des Wurzelknotens jetzt durchlaufen wurde und wir ihn drucken und zum rechten Teilbaum wechseln können.
Nachdem wir alle Elemente durchlaufen haben, erhalten wir die Inorder Traversal as
5 -> 12 -> 6 -> 1 -> 9
Wir müssen den Stapel nicht selbst erstellen, da die Rekursion die richtige Reihenfolge für uns beibehält.
Beispiele für Python, Java und 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);
