Binary Tree Traversierung

Question

Welche Arten von Traversierung gibt es für einen Binary Tree?

Answer 1

Die drei grundlegenden Traversierungsarten sind In-Order, Pre-Order und Post-Order

Inorder-Traversierung: Hierbei werden die Knoten in der Reihenfolge "links, Wurzel, rechts" durchlaufen. In einem Binärbaum mit aufsteigend sortierten Werten werden die Knoten in aufsteigender Reihenfolge ausgegeben.

void inorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

Preorder-Traversierung: Hierbei werden die Knoten in der Reihenfolge "Wurzel, links, rechts" durchlaufen. Das bedeutet, dass der Wurzelknoten zuerst besucht wird, gefolgt von seinen linken und rechten Kindknoten.

void preorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

Postorder-Traversierung: Hierbei werden die Knoten in der Reihenfolge "links, rechts, Wurzel" durchlaufen. Das bedeutet, dass die linken und rechten Kindknoten zuerst besucht werden und dann der Wurzelknoten.

void postorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->data);
    }
}