Java中的树实现 [英] Tree Implementation in Java
问题描述
我得到了以下树:
然后我们被告知使用 last-child/previous-sibling 方法来更改三者的实现.结果如下:
And then we were told to use last-child/previous-sibling method to change the implementation of the three. That resulted in the following:
我现在正在研究 Java 实现以在这棵树上执行不同的功能.我们有一个 Tree 接口和一个 TreeNode 接口.它们都有许多我们要填写的功能.
I am now working on Java implementation to perform different functions on this tree. We have a Tree interface, and a TreeNode interface. They both have many functions that we are to fill out.
节点是这样创建的:
MyTreeNode a = new MyTreeNode ("a");
树是这样创建的(有根):
The tree is created (with a root) in this way:
MyTree tree = new MyTree (a);
最后，节点被赋予兄弟姐妹孩子:
And lastly, nodes are given siblings children as such:
e.setChild(j);
e.setSibling(d);
我已经为 setChild、setSibling、getNextSibling、getFirstChild 和 getChildren 编写了方法.例如，这是 getChildren 的代码:
I already wrote the methods for setChild, setSibling, getNextSibling, getFirstChild, and getChildren. For example, this is the code for getChildren:
public List getChildren ()
{
List <MyTreeNode> children = new ArrayList <MyTreeNode> ();
MyTreeNode x = this.child;
children.add(x);
while (x != null && x.sibling != null) {
x = x.sibling;
children.add(x);
}
return children;
}
我现在完全不知道如何编写节点子树的高度、深度、大小、getPreOrder、getPostOrder 和树大小的方法.
I am now completely lost on how to write the methods for height, depth, size of a node's subtree, getPreOrder, getPostOrder, and tree size.
由于树现在处于这种不同的表示中，我不确定如何编写递归方法来检查节点的高度或深度.通常，据我所知，您会递归检查左/右子树......但现在没有(据我所知).我能想到的唯一方法是使用许多 if 语句和 while 循环遍历每个节点……但这不是最好的方法.
Since the tree is now in this different representation, I am not sure how to write recursive methods to check the height or depth of a node. Normally, as I understand, you would recursively check left/right subtrees.. but now there aren't any (as far as I can see). The only way I can think to do it would be looping through each and every node with many if statements and while loops.. but that can't be the best way to do it.
如何使用树的这种实现递归地编写这些方法?
How can I write these methods recursively with this implementation of a tree?
此外，我不确定如何获取有关整棵树的详细信息，因为节点没有以任何方式存储在一起.它们是按照我上面展示的方式实现的，所以我不确定如何共同收集所有节点的数据.
Also, I am not sure how to get details about the whole tree since nodes are not stored together in any way. They are implemented in the way I showed above, so I'm not sure how to gather data about all the nodes collectively.
如何在作为整棵树的所有节点上创建树大小、isEmpty 或 makeEmpty 等方法?
How can I create methods such as tree size, isEmpty, or makeEmpty, on all the nodes as a whole tree?
抱歉解释过于冗长.
推荐答案
假设您的树有这样的节点结构:
Assuming that you have a node structure like this for your tree:
public class Node{
String nodeName;
Node left;
Node right;
public Node(String nodeName, Node left, Node right){
this.nodeName = nodeName;
this.left = left;
this.right= right;
}
}
以下是我对如何构建新树的看法:当您向树中添加新节点时，您仍将保持树结构.根据您将节点添加到树的方式，您仍将继续添加到父节点的左侧或右侧.
Here's what I think of how I would construct your new tree: When you're adding new nodes to your tree, you would still be maintaining your tree structure. Depending on how you add your nodes to the tree, you would still continue to add either to the left or right of your parent.
可视化新树的一种可能方法是这样的:
One possible way of visualizing the new tree would be something like this:
A
/
E
/ \
D J
/ \ / \
C H I K
/
B
/
G
/
F
注意:我在这里假设如果它是一个孩子，它会被添加到你父母的左边.但这在理想情况下取决于您的要求
如果您能以这种方式可视化这棵树，那么您用于获取高度、前序、后序遍历的递归函数仍然保持不变.
If you can visualize this tree in this way, your recursive functions for getting the height, preorder, postorder traversal still remains the same.
还有一些提示:
添加兄弟节点就像在节点的父节点的左侧或右侧添加一个节点，即如果当前节点位于其父节点的左侧，则您将在右侧添加新节点.
Adding a sibling would be like adding a node to either the left or right of the node's parent, i.e. if the current node is in the left of it's parent, you would add the new node in the right.
添加子项将保持不变.根据您的逻辑，您可以将新节点添加为当前节点的左子节点或右子节点.
Adding a child would remain the same. Depending on your logic, you would add the new node as the left child or the right child of your current node.
这篇关于Java中的树实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
