Building general trees in java (with recursion)

Question

I have been stuck on a problem for quite a few days. My end goal is to perform preorder, inorder, and postorder traversals on a general tree. The problem I am having is just populating the tree. I am only able to add nodes to the root and to the root's children. I am not able to move "down" past the roots children. I woke up one morning with the idea of building the tree recursively from a bottom-up approach. I have never used recursion so first of all, is this possible? I would basically build the tree by creating the nodes at the bottom of the tree and then work my way up?

Here is my node class:

//Represents node of the Tree<T> class
public class Node<T>
{
  public T data;   
  public List<Node<T>> children;

  //Default constructor
  public Node()
  {
     super();
     children = new ArrayList<Node<T>>();
  }

  public Node(T data)
  {
     this();
     setData(data);
  }

  //Return the children of Node<T>
  public List<Node<T>> getChildren()
  {
     if(this.children == null)
     {
        return new ArrayList<Node<T>>();
     }  
     return this.children;
  }

  //Sets the children of a Node<T> object
  public void setChildren(List<Node<T>> children)
  {
     this.children = children;
  }

  //Returns the number of immediate children of this Node<T>
  public int getNumberOfChildren()
  {
     if(children == null)
     {
        return 0;
     } 
     return children.size();
  }

  //Adds a child to the list of children for this Node<T>
  public void addChild(Node<T> child)
  {
     if(children == null)
     {
        children = new ArrayList<Node<T>>();
     }
     children.add(child);
  }

  public void addChildAt(int index, Node<T> child) throws IndexOutOfBoundsException
  {
     if(index == getNumberOfChildren())
     {
        addChild(child);
        return;
     }
     else
     {
        children.get(index);
        children.add(index, child);
     }
  }

  public boolean isLeaf()
  {
     if(getNumberOfChildren() == 0)
        return true;
     return false;
  }

  public T getData()
  {
     return this.data;
  }  

  public void setData(T data)
  {
     this.data = data;
  }

  public String toString()
  {
     StringBuilder sb = new StringBuilder();
     sb.append("{").append(getData().toString()).append(",[");
     int i = 0;
     for(Node<T> e : getChildren())
     {
        if(i > 0)
        {
           sb.append(",");
        }
        sb.append(e.getData().toString());
        i++;
     }
     sb.append("]").append("}");
     return sb.toString();
  }
}

Here is my tree class:

//Tree class
public class Tree<T>
{
   private Node<T> root;

   //Default constructor
   public Tree()
   {
      super();
   }

   //Returns the root
   public Node<T> getRoot()
   {
      return this.root;
   }

   //Set the root of the tree
   public void setRoot(Node<T> root)
   {
      this.root = root;
   }

   //Returns the Tree<T> as a List of Node<T> objects
   public List<Node<T>> toList()
   {
      List<Node<T>> list = new ArrayList<Node<T>>();
      walk(root, list);
      return list;
   }

   //String representation of ttree
   public String toString()
   {
      return toList().toString();
   }

   //Preorder traversal
   private void walk(Node<T> element, List<Node<T>> list)
   {
      list.add(element);
      for(Node<T> data : element.getChildren())
      {
         walk(data, list);
      }
   }
}

This is my main driver program:

//Importing packages
import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.*;
import java.io.BufferedReader;
import java.util.List;
import java.util.ArrayList;

//Class header
public class treeTraversals
{
   //Main method
   public static void main (String[] args) throws IOException
   {
      //Defining variables
      String file;
      int size = 0;
      int id = 1;
      int counter = 1;

      Scanner keyboard = new Scanner(System.in);

      //Request file
      System.out.print("Enter the filename: ");
      file = keyboard.nextLine();

      //Read file
      File treeFile = new File(file);
      Scanner inputFile = new Scanner(treeFile);
      BufferedReader reader = new BufferedReader(new FileReader(file));

      //Find size of input file
      while(reader.readLine() != null)
      {
         size++;
      }
      reader.close();

      String[] parent = new String[size+1];
      String[] child = new String[size+1];

      //Add file vaules to arrays
      while(inputFile.hasNext())
      {       
            String line = inputFile.nextLine();
            StringTokenizer st = new StringTokenizer(line);

            while(st.hasMoreTokens())
            {    
               String previousValue = st.nextToken();
               String nextValue = st.nextToken();

               parent[counter] = previousValue;
               child[counter] = nextValue;

               counter++;
            }
      }
      System.out.println();

      //Output to the screen
      System.out.println("The Tree");
      System.out.println();

      for(int l = 1; l <= size; l++)
      {
         System.out.print(parent[l] + " ");
         System.out.println(child[l]);
      }

      //Create the root of the tree
      Tree tree = new Tree();
      Node root = new Node(parent[id]);
      tree.setRoot(root);

      Node active = new Node();

      //Fill tree with nodes  
      for(id = 1; id <= size; id++)
      {       
         Node parentNode = new Node(parent[id]);
         Node childNode = new Node(child[id]);
         active = root; 
         int passage = 0;

         //Adds children to the root node
         if(parentNode.getData().equals(active.getData()))
         {       
            active.addChild(childNode);

            System.out.println(tree.toList());
         }
         //Adds children to the root's children
         else if(!parentNode.getData().equals(active.getData()))
         {         
            boolean marked = false;
            int i = -1;
            int n = 0;


            while(i != active.getNumberOfChildren() && marked == false && n <= 2)
            {
               active = root;     
               active = (Node)active.getChildren().get(n);

               if(active.getData().equals(parentNode.getData()))
               {
                  active.addChild(childNode);
                  marked = true;
               }
               i++;
               n++; 
            }   

            active = root;
            if(n >= 3 && marked == false)
            {
               for(int p=0; p < active.getNumberOfChildren(); p++)
               {
                   active = (Node)active.getChildren().get(p);

                   if(active.getData().equals(parentNode.getData()))
                   {
                      active.addChild(childNode);
                      //p++;
                      marked = true;
                   }
                   else
                   {  
                       active = root;
                       active = (Node)active.getChildren().get(p);
                       active = (Node)active.getChildren().get(p);
                       if(active.getData().equals(parentNode))
                       {
                           active.addChild(childNode);
                           System.out.println("No");
                           p = 0;
                       }
                    }
                 }
              }
           }
           //See the nodes in the tree
           System.out.println(tree.toList());
        }
     }
  }

Lastly, here is the text file that is provided:

a  b
a  c
a  d
b  e
b  f
d  g
d  h
d  i
e  j
e  k
g  l
g  m
k  n
k  o
k  p

Please, any help would be appreciated, I'm stuck on my own approach so I'm asking: how would I even start if I'm going with a recursive approach?

Answer 1

I have neglected the order for now, and just given an Tree.insert(parentData, data). With the hope that this helps getting you started.

public class Node<T> {
    private T data;   
    private List<Node<T>> children;

    Node<T> find(T data) {
        if (this.data.equals(data)) {
            return this;
        }
        for (Node<T> node : children) {
            Node<T> found = node.find(data);
            if (found != null) {
                return found;
            }
        }
        return null; // Not found.
    }

public class Tree<T> {

    public find(T data) {
        return root == null ? null : root.find(data);
    }

    public boolean insert(T parentData, T data) {
        Node<T> found = find(parentData);
        if (found == null) {
            return false;
        }
        found.getChildren().add(new Node(data));
        return true;
    }

As one sees, having a find(data) method for retrieving the (parent) Node helps. The search method find here disregards any sorting of the values, and does a preorder search.

As far as order is concerned, normally on has nodes of the form:

class Node<T> {
    List<Node<T>> children; // 0, 1, ... N
    List<T> values; // 0, 1, ... N-1
}

With an sort ordering:

children[0]
values[0}
children[1}
values[0]
children[2]
...
children[N-1]
values[N-1]
children[N]

One might retain the values in the entire tree in this order. Sorting and preorder/postorder walks and bread fírst/depth first walks are different notions.

Answer 2

import java.util.*;
public class GeneralTree {
    class Node {
        int value;
        ArrayList<Node> list;

        public Node(int value, ArrayList<Node> list) {
            this.value = value;
            this.list = list;
        }
    }

    public void traverse(Node node) {
        System.out.print(node.value + " ");
        for (int i = 0; i < node.list.size(); i++) {
            traverse(node.list.get(i));
        }
    }

    public static void main(String[] args) {
        GeneralTree tree = new GeneralTree();
        GeneralTree.Node node5 = tree.new Node(5, new ArrayList(Arrays.asList()));
        GeneralTree.Node node6 = tree.new Node(3, new ArrayList(Arrays.asList()));
        GeneralTree.Node node1 = tree.new Node(1, new ArrayList(Arrays.asList(node5, node6)));
        GeneralTree.Node node3 = tree.new Node(99, new ArrayList(Arrays.asList(node6)));
        GeneralTree.Node node2 = tree.new Node(45, new ArrayList(Arrays.asList(node1, node3)));
        tree.traverse(node2);

    }
}