algorithm
Binaire boom doorkruisen

Invoering

Pre-order, Inorder en Post Order traversal van een binaire boom

Overweeg de binaire boom:

Pre-order traversal (root) doorloopt de knoop en vervolgens de linker subboom van de knoop en vervolgens de rechter subboom van de knoop.

Dus de pre-order doorgang van bovenstaande boom zal zijn:

1 2 4 5 3 6 7

In-volgorde doorkruisen (root) doorkruist de linker subboom van het knooppunt dan de knoop en vervolgens de rechter subboom van het knooppunt.

Dus de volgorde in de volgorde van bovenstaande boom zal zijn:

4 2 5 1 6 3 7

Post-order traversal (root) doorloopt de linker subboom van de knoop en vervolgens de rechter subboom en vervolgens de knoop.

Dus de post-order doorgang van bovenstaande boom zal zijn:

4 5 2 6 7 3 1

Niveau Order doorgang - Implementatie

Als de gegeven boom bijvoorbeeld is:

Niveau order doorgang zal zijn

1 2 3 4 5 6 7

Node-gegevensniveau per niveau afdrukken.

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

Wachtrij-gegevensstructuur wordt gebruikt om het bovenstaande doel te bereiken.