java - 在 Java 中构建通用树(使用递归)

Question

我被一个问题困了好几天了。我的最终目标是在一般树上执行前序、中序和后序遍历。我遇到的问题只是填充树。我只能将节点添加到根和根的子节点。我无法“向下”移动过根部 child 。一天早上醒来，我想到了用自下而上的方法递归地构建树。我从来没有使用过递归，所以首先，这可能吗？我基本上会通过在树的底部创建节点然后向上移动来构建树？

这是我的节点类:

//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();
  }
}

这是我的树类:

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

这是我的主要驱动程序:

//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());
        }
     }
  }

最后，这是提供的文本文件:

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

请提供任何帮助，我将不胜感激，我一直坚持自己的方法，所以我想问:如果我采用递归方法，我该如何开始？

Answer 1

我暂时忽略了顺序，只给出了一个Tree.insert(parentData, data)。希望这有助于您入门。

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

如您所见，使用find(data) 方法检索(父)节点会有所帮助。此处的搜索方法 find 忽略值的任何排序，并进行预排序搜索。

就顺序而言，通常 on 具有以下形式的节点:

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

使用排序顺序:

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

可以按此顺序保留整个树中的值。排序和前序/后序游走和面包优先/深度优先游走是不同的概念。