CODEWITHSUNDEEP
c++treetraversal
user2775084
user2775084

Reputation: 105

Traverse a n-ary tree

I am trying to understand pre-order traversal for an n-ary tree. I have been reading and all the examples that i found use a Left Subtree and a right subtree but, in an n-ary tree, what is the left and what is the right subtree? Can someone give a good explanation or a pseudo code?

Upvotes: 0

Views: 2299

Answers (2)

Khatri
Khatri

Reputation: 636

Here is my C++ Implementation for level order traversal of n dimensional tree.You can tweak a bit for pre-order traversal.It assumes that one node can have at most 50 branches but you can always modify that part.Hope this helps and Please Let me know if you found any bug. Thanks!

#include <iostream>
#include <map>
#include <vector>
using namespace std;
#define MAXSIZE 50

typedef struct node{
    int data;
    node** bArray;
} Node;


Node* newNode(int data){
    Node* newnode = new Node;
    newnode->data = data;
    newnode->bArray = new Node* [MAXSIZE];
    for(int i=0;i<50;i++){
        newnode->bArray[i] = NULL;
    }
    return newnode;
}

void mapFun(Node* root,int level,map<int,vector<int> >&m){
    if(root == NULL)return;
    m[level].push_back(root->data);

    for(int i=0;i<MAXSIZE;i++)
        mapFun(root->bArray[i],level+1,m);

    return;
}

void print_level(map<int,vector<int> >&m, int level){
    cout<<level<<"th level traversal is........";
    vector<int> v = m[level];
    vector<int>::iterator it;
    for(it=v.begin();it!=v.end();it++){
        cout<<*it<<" ";
    }

}

void levelOrder(Node* root, map<int,vector<int> >&m){
    mapFun(root,1,m);
    int mapsize = m.size();
    for(int i=1;i<=mapsize;i++){
        print_level(m,i);
        cout<<endl;
    }
}

int main(){
    int i;
    map<int,vector<int> >mymap;
    map<int,vector<int> > :: iterator it;
    Node *root = newNode(1);
    root->bArray[0] = newNode(2);
    root->bArray[1] = newNode(3);
    root->bArray[2] = newNode(4);
    Node* first = root->bArray[1];
    first->bArray[0] = newNode(8);
    first->bArray[1] = newNode(9);
    first->bArray[2] = newNode(10);
    Node *second = first->bArray[1];
    second->bArray[0] = newNode(55);
    second->bArray[1] = newNode(65);
    second->bArray[2] = newNode(75);
    cout << "level order traversal is \n";
    levelOrder(root,mymap);
    return 0;
}

Upvotes: 1

David Weiser
David Weiser

Reputation: 5195

Instead of thinking in specifics of left and right, as in:

def preorder_traversal(tree)
   preorder_traversal(tree->left)
   preorder_traversal(tree->right)
end

What if instead, you thought of it as branches:

def preorder_traversal(tree)
   branches = tree->branches // e.g. [left, middle, next-to-right, right]
   branches.each do |branch|
     preorder_traversal(branch)
   end
end

Does that help you?

Upvotes: 4

Related Questions