Java 中的树实现

我得到了以下树：

然后我们被告知使用last-child/previous-sibling方法来改变这三个的实现。结果如下：

我现在正在研究 Java 实现，以在这棵树上执行不同的功能。我们有一个 Tree 接口和一个 TreeNode 接口。它们都有很多功能需要我们去填补。

节点是这样创建的：

MyTreeNode a = new MyTreeNode ("a");

树是这样创建的（有根）：

MyTree     tree = new MyTree (a);

最后，节点被赋予兄弟姐妹子节点，如下所示：

e.setChild(j);
e.setSibling(d);

我已经编写了 setChild、setSibling、getNextSibling、getFirstChild 和 getChildren 的方法。例如，这是 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;
}

我现在完全不知道如何编写节点子树的高度、深度、大小、获取 PreOrder、PostOrder 和树大小的方法。

由于树现在采用这种不同的表示形式，因此我不确定如何编写递归方法来检查节点的高度或深度。通常，据我了解，您会递归地检查左/右子树..但现在没有（据我所知）。我能想到的唯一方法是使用许多 if 语句和 while 循环循环遍历每个节点..但这不是最好的方法。

如何使用树的实现递归地编写这些方法？

另外，我不确定如何获取整个树的详细信息，因为节点不以任何方式存储在一起。它们是按照我上面展示的方式实现的，所以我不确定如何集中收集所有节点的数据。

如何在整个树的所有节点上创建树大小、isEmpty 或 makeEmpty 等方法？

抱歉，解释过于冗长。

假设您的树有这样的节点结构：

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

以下是我对如何构建新树的看法：当您向树添加新节点时，您仍然会维护树结构。根据将节点添加到树的方式，您仍将继续添加到父级的左侧或右侧。

可视化新树的一种可能方法是这样的：

                A
               /
              E
            /   \
           D     J
         /   \   / \
        C    H  I   K
       /
      B
     /
    G
   /    
  F

注意：我在这里假设，如果它是一个单独的孩子，它将被添加到您父母的左侧。但这最好取决于您的要求

如果您可以用这种方式可视化这棵树，那么用于获取高度、前序、后序遍历的递归函数仍然保持不变。

还有一些提示：

• 添加兄弟节点就像在节点父节点的左侧或右侧添加一个节点一样，即，如果当前节点位于其父节点的左侧，则将在右侧添加新节点。

• 添加孩子将保持不变。根据您的逻辑，您可以将新节点添加为当前节点的左子节点或右子节点。