当前位置: 首页 > 知识库问答 >
问题:

在Java中构造通用树(带有递归)

康元凯
2023-03-14

我被一个问题缠住好几天了。我的最终目标是在一个通用树上执行预排序、中排序和后排序遍历。我遇到的问题只是填充树。我只能将节点添加到根和根的子节点。我不能通过根的孩子“向下”移动。一天早上,我醒来时想到了一个从下至上的方法递归地构建树的想法。我从来没有用过递归,所以首先,这可能吗?我基本上是通过在树的底部创建节点来构建树,然后再向上工作?

下面是我的节点类:

//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

请,任何帮助都将非常感谢,我被我自己的方法卡住了,所以我想问:如果我使用递归方法,我怎么开始呢?

共有1个答案

何华灿
2023-03-14

我暂时忽略了顺序,只是给出了一个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]

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

 类似资料:
  • 问题内容: 我正在构造一个二叉树。让我知道这是否是正确的方法。如果没有,请告诉我怎么做?我在构建通用二进制树的代码已找到的地方找不到合适的链接。BST的每个地方都已编码。 这是我要制作的二叉树。我应该能够进行所有的树遍历。 问题答案: 我认为这是您要寻找的:

  • 问题内容: 为什么供应商仅支持无参数构造函数? 如果存在默认构造函数,则可以执行以下操作: 但是,如果唯一的构造函数采用字符串,则必须这样做: 问题答案: 这只是方法引用语法的局限性,您不能传入任何参数。语法就是这样工作的。

  • 我有一个通用的树结构。我需要一个算法来遍历它,并删除一些不包含在给定列表中的叶子。如果所有的叶子都从子树中删除,那么也删除整个子树。 示例树: 要保留的叶子:{4,6} 结果树: 输入数据结构包含在 HashMap 中,其中键是节点的父 ID,值是父节点正下方的节点列表(但不是递归所有子节点)。根节点的父 ID 为空字符串。 我想,某种递归DFS遍历算法应该可以工作,但我不知道它是如何工作的。

  • 我试图从一个ArrayList中构造N元树,N元树表示为带有子指针和兄弟指针的二进制。这里是类节点,每个节点元素携带的数据应该通过预购遍历打印出来。 这是类树。 在主程序中,我将根设置为一个parentID为0的节点,并且节点的数组列表是好的。为了添加树节点,我必须有哪个是父节点和哪个是新节点。当调用preorder函数时,它在:preorder(root.child);我认为这棵树的创建存在一些

  • 我正在研究如何将自定义构造与SnakeYAML一起使用,但不确定如何实现嵌套。我用这个例子作为参考。 在链接的示例中,相关的YAML和构造是, 现在,让我们将YAML更改为, 我想使用另一个来解析对象,但要在上下文中进行。我对关系的理解非常不稳定,我对如何在自定义构造函数中使用自定义构造函数感到困惑。有什么想法或资源吗?

  • 问题内容: 我有一个带有字段的“页面”对象列表。此父字段引用列表中的另一个对象。我想基于此字段从此列表创建树层次结构。 这是我原始列表的样子: 我想将其转换为这样的树结构: 我希望可以在任何时候针对任意列表调用的可重用函数。有人知道解决这个问题的好方法吗?任何帮助或建议,将不胜感激! 问题答案: 小提琴