1
Я застрял в проблеме в течение довольно многих дней. Моя конечная цель - выполнить предзаказ, по порядку и постобработки на общем дереве. Проблема, с которой я столкнулась, - это просто заполнить дерево. Я могу только добавить узлы к корню и к корневым детям. Я не могу двигаться «вниз» мимо корней детей. Однажды утром я проснулся с идеей рекультивирования дерева из подхода снизу вверх. Я никогда не использовал рекурсию, прежде всего, возможно ли это? Я бы в основном построил дерево, создав узлы в нижней части дерева, а затем проработал мой путь вверх?Строительство общих деревьев в java (с рекурсией)
Вот мой класс узел:
//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
Пожалуйста, любая помощь будет оценена по достоинству, я придерживаюсь своего подхода, поэтому я спрашиваю: как я мог бы начать, если я собираюсь использовать рекурсивный подход?
Для общего дерева нет обходного пути. –
вы имеете в виду, что не реализованы в стандартном java, но, безусловно, есть библиотеки. – jediz