algorithm
Binäre Baumdurchquerungen

Einführung

Vorbestellung, Nachbestellung und Nachbestellung eines binären Baums

Betrachten Sie den binären Baum:

Durchlauf vor der Bestellung (Wurzel) durchläuft den Knoten, dann den linken Unterbaum des Knotens und dann den rechten Unterbaum des Knotens.

Die Vorbestellung des obigen Baums lautet also:

1 2 4 5 3 6 7

Durchlauf in der Reihenfolge (Wurzel) durchläuft den linken Teilbaum des Knotens, dann den Knoten und dann den rechten Teilbaum des Knotens.

Der Durchlauf in der Reihenfolge des obigen Baums ist also:

4 2 5 1 6 3 7

Durchlauf nach der Reihenfolge (Wurzel) durchläuft den linken Teilbaum des Knotens, dann den rechten Teilbaum und dann den Knoten.

Die Nachbestellung des obigen Baums lautet also:

4 5 2 6 7 3 1

Level Order Traversal - Implementierung

Zum Beispiel, wenn der angegebene Baum ist:

Level Order Traversal wird sein

1 2 3 4 5 6 7

Knotendaten werden Stufe für Stufe gedruckt.

Code:

#include<iostream>
#include<queue>
#include<malloc.h>

using namespace std;

struct node{
    
    int data;
    node *left;
    node *right;
};

void levelOrder(struct node *root){
    
        if(root == NULL)    return;
        
        queue<node *> Q;
        Q.push(root);
        
        while(!Q.empty()){
        struct    node* curr = Q.front();
            cout<< curr->data <<" ";
            if(curr->left != NULL) Q.push(curr-> left);
                if(curr->right != NULL) Q.push(curr-> right);
                
                Q.pop();
            
            
        }
}
struct node* newNode(int data)
{
    struct node* node = (struct node*)
                        malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return(node);
}

int main(){
    
    struct node *root = newNode(1);
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(4);
    root->left->right = newNode(5);
    root->right->left  = newNode(6);
    root->right->right = newNode(7);
 
 
    printf("Level Order traversal of binary tree is \n");
    levelOrder(root);
    
    return 0;
    
    
}

Die Warteschlangendatenstruktur wird verwendet, um das obige Ziel zu erreichen.