CODEWITHSUNDEEP
javatree
user2277918
user2277918

Reputation: 247

traversing a non binary tree in java

I have a tree which is a non-binary tree and each node has more than 2 children.

I am looking for an algorithm to traverse the tree and print nodes, I am really new to learning data structure.

I know how to traverse a binary tree but I get lost when it comes to traversing a non-binary tree.

Could anyone give me a hint on how may I change the binary-tree traversal algorithm into a non-binary-tree traversal?

Assuming that we have the Binary tree traversal code using the DFS algorithm pre-order (Root-Left-Right).

public static class Node {
        private Integer val;
        private Node left;
        private Node right;
// setters and getters
}

public static void dfsPreOrderTraverseByRecursion(Node root) {
    if(root!=null) {
        System.out.println(root.getVal());
        dfsPreOrderTraverseByRecursion(root.getLeft());
        dfsPreOrderTraverseByRecursion(root.getRight());
    }
}

And this binary-tree

enter image description here

The above code should print it like this :

0
1
11
12
121
1211
122
2
21

In the case of the non-binary tree. I need to modify the above code to traverse this tree in a similar way (Root-Left....Right) enter image description here

With the new class Node as follows

public static class Node {
        private Integer val;
        private List<Node> children;
// setters and getters
}

And print the tree like this:

0
1
6
7
11
12
13
2
8
3
9
10
14
4

Upvotes: 17

Views: 30305

Answers (4)

Tarik
Tarik

Reputation: 11209

Well, when traversing a binary tree, in preorder, you visit the parent node, then recursively traverse the left subtree then recursively traverse the right subtree. With a tree with more than two children, you recursively traverse the subtrees headed by each children. You would do the recursive calls in a for loop.

Upvotes: 8

Cratylus
Cratylus

Reputation: 54074

The algorithm for pre-post order is the same as a binary tree.
There is no such thing as in-order traversal for a general tree i.e. does not make sense (unless you define some order)

Upvotes: 0

An SO User
An SO User

Reputation: 24998

In a non-binary tree, there will be a Vector or some other structure that has references to all the children. Make a recursive method as so: 

public void traverse(Node child){ // post order traversal
    for(Node each : child.getChildren()){
        traverse(each);
    }
    this.printData();
}

Something along those lines.

Upvotes: 29

Joseph
Joseph

Reputation: 13178

You'll need to use recursion since you can't determine how many children are at each node (breadth) or how far the tree goes (depth). Depending on how you want to traverse, you can use Breadth-first-search or Depth-first-search.

There is a ton of information on this topic, so give it an attempt to implement one of these recursive methods and please come back if you have trouble along the way!

Upvotes: 6

Related Questions