Results 1 to 4 of 4
 03272012, 06:05 AM #1Member
 Join Date
 Mar 2012
 Posts
 2
 Rep Power
 0
Traversing Binary Tree from Root to each Branch
I have a couple of other questions. I need to get all the different combinations in a binary tree and store them into a data structure. For example, in the attached diagram of a binary tree the combinations would be:
1) A, A1, A2, B1, B2
2) A, A1, B1, A2, B2
3) A, A1, B1, B2, A24) A, B1, A1, A2, B2
5) A, B1, A1, B2, A2
6) A, B1, B2, A1, A2
I understand that this is very similar to the preorder traversal, but preorder does not output the parent nodes another time when the node splits into a left and right node. Any suggestions?
Java Code:/* * To change this template, choose Tools  Templates * and open the template in the editor. */ package binarytreetest; import java.util.ArrayList; import java.util.Iterator; /** * * @author vluong */ public class BinaryTreeTest { /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here int countA = 0; int countB = 0; ArrayList listA = new ArrayList(); ArrayList listB = new ArrayList(); listA.add("A1"); listA.add("A2"); listA.add("A3"); listB.add("B1"); listB.add("B2"); listB.add("B3"); //listB.add("B1"); Node root = new Node("START"); constructTree(root, countA, countB, listA, listB); //printInOrder(root); //printFromRoot(root); } public static class Node{ private Node left; private Node right; private String value; public Node(String value){ this.value = value; } } public static void constructTree(Node node, int countA, int countB, ArrayList listA, ArrayList listB){ if(countA < listA.size()){ if(node.left == null){ System.out.println("There is no left node. CountA is " + countA); System.out.println("Created new node with value: " + listA.get(countA).toString() + " with parent, " + node.value); System.out.println(); node.left = new Node(listA.get(countA).toString()); constructTree(node.left, countA+1, countB, listA, listB); }else{ System.out.println("There is a left node. CountA + 1 is " + countA+1); constructTree(node.left, countA+1, countB, listA, listB); } } if(countB < listB.size()){ if(node.right == null){ System.out.println("There is no right node. CountB is " + countB); System.out.println("Created new node with value: " + listB.get(countB).toString() + " with parent, " + node.value); System.out.println(); node.right = new Node(listB.get(countB).toString()); constructTree(node.right, countA, countB+1, listA, listB); }else{ System.out.println("There is a right node. CountB + 1 is " + countB+1); constructTree(node.right, countA, countB+1, listA, listB); } } }
Java Code:public static class Node{ private Node left; private Node mid; private Node right; private String value; public Node(String value){ this.value = value; } }
Node left = listA, Node mid = listB, Node right = listC
The code for the 3 lists is below.
3 lists (A, B, C):
Java Code:/* * To change this template, choose Tools  Templates * and open the template in the editor. */ package binarytreetest; import java.util.ArrayList; /** * * @author vluong */ public class BinaryTreeTest { /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here /* insert(root, "A1"); insert(root, "A2"); insert(root, "B1"); insert(root, "B2"); insert(root, "A2"); * */ int countA = 0; int countB = 0; int countC = 0; ArrayList listA = new ArrayList(); ArrayList listB = new ArrayList(); ArrayList listC = new ArrayList(); listA.add("A1"); listA.add("A2"); //listA.add("A3"); listB.add("B1"); listB.add("B2"); //listB.add("B3"); //listB.add("B1"); listC.add("C1"); listC.add("C2"); Node root = new Node("START"); constructTree(root, countA, countB, countC, listA, listB, listC); //ConstructTree(root, countA, countB, listA, listB); //ConstructTree(root, countA, countB, listA, listB); printInOrder(root); //printFromRoot(root); } public static class Node{ private Node left; private Node mid; private Node right; private String value; public Node(String value){ this.value = value; } } public static void constructTree(Node node, int countA, int countB, int countC, ArrayList listA, ArrayList listB, ArrayList listC){ if(countA < listA.size()){ if(node.left == null){ System.out.println("There is no left node. CountA is " + countA); System.out.println("Created new node with value: " + listA.get(countA).toString() + " with parent, " + node.value); System.out.println(); node.left = new Node(listA.get(countA).toString()); constructTree(node.left, countA+1, countB, countC, listA, listB, listC); }else{ System.out.println("There is a left node. CountA + 1 is " + countA+1); constructTree(node.left, countA+1, countB, countC, listA, listB, listC); } } if(countB < listB.size()){ if(node.mid == null){ System.out.println("There is no mid node. CountB is " + countB); System.out.println("Created new node with value: " + listB.get(countB).toString() + " with parent, " + node.value); System.out.println(); node.mid = new Node(listB.get(countB).toString()); constructTree(node.mid, countA, countB+1, countC, listA, listB, listC); }else{ System.out.println("There is a right node. CountB + 1 is " + countB+1); constructTree(node.mid, countA, countB+1, countC, listA, listB, listC); } } if(countC < listC.size()){ if(node.right == null){ System.out.println("There is no right node. CountC is " + countC); System.out.println("Created new node with value: " + listC.get(countC).toString() + " with parent, " + node.value); System.out.println(); node.right = new Node(listC.get(countC).toString()); constructTree(node.right, countA, countB, countC+1, listA, listB, listC); }else{ System.out.println("There is a right node. CountC + 1 is " + countC+1); constructTree(node.mid, countA, countB, countC+1, listA, listB, listC); } } }
 03272012, 09:26 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,372
 Blog Entries
 7
 Rep Power
 25
Re: Traversing Binary Tree from Root to each Branch
Two possibilities come to mind:
1) if you have an algorithm that can traverse to each leaf node, add another parameter to that method: a List<Node> object and add the current Node to that list each time you visit a new node (which is 'deeper' in the tree). When you reach a leaf Node the List<Node> contains the path from the root to it.
2) add another element to each Node, pointing to the parent of the Node. For the same method as above, as soon as it reaches a leaf Node, traverse upwards using the parent Nodes and find the path to the root; reverse the path as soon as you reach the root Node.
kind regards,
JosThe only person who got everything done by Friday was Robinson Crusoe.
 04112012, 01:21 AM #3Member
 Join Date
 Mar 2012
 Posts
 2
 Rep Power
 0
Re: Traversing Binary Tree from Root to each Branch
Thank you for the help, JosAH!
 04162012, 05:28 PM #4Member
 Join Date
 Oct 2011
 Location
 New Jersey
 Posts
 44
 Rep Power
 0
Similar Threads

Binary Tree Help  Find the largest subtree
By joshhazel in forum New To JavaReplies: 2Last Post: 01302012, 03:08 AM 
binary tree
By Dedo in forum Advanced JavaReplies: 15Last Post: 05262011, 09:11 PM 
Help: traversing huffman tree
By Reploids in forum New To JavaReplies: 0Last Post: 05242011, 09:42 AM 
binary tree
By ryamz in forum New To JavaReplies: 2Last Post: 08122010, 02:45 AM 
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04042010, 07:40 AM
Bookmarks