有一个树实现，它需要对如何实现逻辑进行修正和思考。
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* @param <T>
*/
class TreeNode<T> implements Iterable<TreeNode<T>> {
private final List<TreeNode<T>> elementsIndex;
public T data;
public TreeNode<T> parent;
public List<TreeNode<T>> children;
/**
* @param data
*/
public TreeNode(T data) {
this.data = data;
this.children = new LinkedList<TreeNode<T>>();
this.elementsIndex = new LinkedList<TreeNode<T>>();
this.elementsIndex.add(this);
}
/**
* @param depth
* @return Indentation
*/
private static String createIndent(int depth) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < depth; i++) {
sb.append('-');
}
return sb.toString();
}
/**
* @return parent
*/
public boolean isRoot() {
return parent == null;
}
/**
* @return check the size of child
*/
public boolean isLeaf() {
return children.size() == 0;
}
/**
* @param child
* @return child node
*/
public TreeNode<T> addChild(T child) {
TreeNode<T> childNode = new TreeNode<T>(child);
childNode.parent = this;
this.children.add(childNode);
this.registerChildForSearch(childNode);
return childNode;
}
/**
* @return the depth of the level
*/
public int getLevel() {
if (this.isRoot())
return 0;
else
return parent.getLevel() + 1;
}
/**
* @param node
*/
private void registerChildForSearch(TreeNode<T> node) {
elementsIndex.add(node);
if (parent != null)
parent.registerChildForSearch(node);
}
/**
* @param cmp
* @return finds the element
*/
public TreeNode<T> findTreeNode(Comparable<T> cmp) {
for (TreeNode<T> element : this.elementsIndex) {
T elData = element.data;
if (cmp.compareTo(elData) == 0)
return element;
}
return null;
}
/**
* @return the root
*/
@Override
public String toString() {
return data != null ? data.toString() : "[data null]";
}
/**
* @return iterator
*/
@Override
public Iterator<TreeNode<T>> iterator() {
TreeNodeIter<T> iter = new TreeNodeIter<T>(this);
return iter;
}
/**
* @param treeRoot
* @param data
* @return the data else null if not found
*/
public TreeNode<T> search(TreeNode<T> treeRoot, T data) {
Comparable<T> searchCriteria = new Comparable<T>() {
@Override
public int compareTo(Object treeData) {
if (treeData == null)
return 1;
boolean nodeOk = treeData.equals(data);
return nodeOk ? 0 : 1;
}
};
TreeNode<T> found = treeRoot.findTreeNode(searchCriteria);
return found;
}
/**
* @param treeRoot
* @return the whole tree
*/
public StringBuilder display(TreeNode<T> treeRoot) {
StringBuilder print = new StringBuilder();
print.append('\n');
for (TreeNode<T> node : treeRoot) {
String indent = createIndent(node.getLevel());
print.append(indent + node.data);
print.append("\n|");
}
if (print.length() > 0)
print.deleteCharAt(print.length() - 1);
return print;
}
}
/**
* @param <T>
*/
class TreeNodeIter<T> implements Iterator<TreeNode<T>> {
private final TreeNode<T> treeNode;
private final Iterator<TreeNode<T>> childrenCurNodeIter;
private ProcessStages doNext;
private TreeNode<T> next;
private Iterator<TreeNode<T>> childrenSubNodeIter;
/**
* @param treeNode
*/
public TreeNodeIter(TreeNode<T> treeNode) {
this.treeNode = treeNode;
this.doNext = ProcessStages.ProcessParent;
this.childrenCurNodeIter = treeNode.children.iterator();
}
/**
* @return true if there is nay element
*/
@Override
public boolean hasNext() {
if (this.doNext == ProcessStages.ProcessParent) {
this.next = this.treeNode;
this.doNext = ProcessStages.ProcessChildCurNode;
return true;
}
if (this.doNext == ProcessStages.ProcessChildCurNode) {
if (childrenCurNodeIter.hasNext()) {
TreeNode<T> childDirect = childrenCurNodeIter.next();
childrenSubNodeIter = childDirect.iterator();
this.doNext = ProcessStages.ProcessChildSubNode;
return hasNext();
} else {
this.doNext = null;
return false;
}
}
if (this.doNext == ProcessStages.ProcessChildSubNode) {
if (childrenSubNodeIter.hasNext()) {
this.next = childrenSubNodeIter.next();
return true;
} else {
this.next = null;
this.doNext = ProcessStages.ProcessChildCurNode;
return hasNext();
}
}
return false;
}
/**
* @return the next element
*/
@Override
public TreeNode<T> next() {
return this.next;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
enum ProcessStages {
ProcessParent,
ProcessChildCurNode,
ProcessChildSubNode
}
}所以，问题是我有这样的数据
Gen
|-Test1
|--Mat
|-Test2
|--123
|---Child's Child
|----Child's Child's Child
|----2406
|-Test3
|--24但要实现这一点，我必须硬编码这样的东西
public static TreeNode<String> getSet() {
TreeNode<String> root = new TreeNode<String>("Gen");
{
TreeNode<String> node0 = root.addChild("Test1");
{
TreeNode<String> node00 = node0.addChild("Mat");
}
TreeNode<String> node1 = root.addChild("Test2");
{
TreeNode<String> node10 = node1.addChild("123");
{
TreeNode<String> node100 = node10.addChild("Child's Child");
{
TreeNode<String> node1000 = node100.addChild("Child's Child's Child");
TreeNode<String> node1001 = node100.addChild("2406");
}
}
}
TreeNode<String> node2 = root.addChild("Test3");
{
TreeNode<String> node20 = node2.addChild("24");
}
}
return root;
}}
在上面，我调用了helper方法 getPartentChildPart() 方法，该方法用于获取Map<parent，list>，即 Map<String,List<String>> ```
Gen
|-Test1
|--Mat
|-Test2
|--123
|---Child's Child
|----Child's Child's Child
|----2406
|-Test3
|--24
例如，如果我 `Gen` 作为参数 `getPartentChildPart()` 然后它就会回来Map<Gen,<Test1,Test2,Test3>>
到目前为止我能做到的是public void Build(Map<String, List> ROOT) {
TreeNode root = null;
TreeNode node = null;
for (Map.Entry<String, List> i : ROOT.entrySet()) {
root = new TreeNode<>(i.getKey());
for (String j : i.getValue())
{
node = root.addChild(j);
parent = getPartentChildPart(j);
Build(parent);
}
System.out.println("Root"+root.display(root));
}
}
public void Show() {
Map<String, List<String>> rt = null;
rt = getPartentChildPart("Gen");
Build(rt);
}我得到的结果是Gen
|-Test1
|-Test2
|-Test3
我不明白为什么递归不起作用，我怎么能实现这个。。。虽然如果我硬编码这个它可以工作，如果我的树在未来增长，那么硬编码将不工作。
2条答案
按热度按时间thigvfpy1#
错误是我每次都需要创建一个新节点，并且需要将根放在递归之外。
inn6fuwd2#
首先要做的是添加一个返回子对象列表的方法。从那里递归变得非常简单。
这将遍历整个树。根据您是想在子对象之前（我相信这是您的情况）还是之后执行操作，您可以将代码放在函数的顶部或底部。
让我知道这是否适合你。