如何实现非二叉树 [英] How to implement a Non-Binary tree

问题描述

我无法实现一个非二叉树，其中根节点可以拥有任意数量的子节点。基本上，我想要一些关于这个方面的想法，因为我已经编写了一些代码，但是我现在就停止了下一步做什么。 BTW我根本不能使用任何Collections类。我只能使用系统。

I am having trouble implementing a non-binary tree, where the root node can have an arbitrary amount of child nodes. Basically, I would like some ideas on how where to go with this, since I do have some code written, yet I'm stuck at this point on what to do next. BTW I cannot use any of the Collections classes at all. I can only use System.

using System;

namespace alternate_solution
{
 //            [root]
 //        /  /      \    \
 //    text  text  text  text

class Node//not of type TreeNode (since Node is different from TreeNode)
{
    public string data;
    public Node child;

    public Node(string data)
    {
        this.data = data;
        this.child = null;
    }

}

}

推荐答案

到目前为止，Jerska的解决方案是最好的，但不必要的复杂。

So far Jerska's solution is the best but it is needlessly complicated.

由于我认为这是一个家庭作业，让我给你你应该去的方向。你想要的数据结构是：

Since I assume this is a homework exercise let me give you the direction you should head in. The data structure you want is:

class TreeNode
{
  public string Data { get; private set; }
  public TreeNode FirstChild { get; private set; }
  public TreeNode NextSibling { get; private set; }
  public TreeNode (string data, TreeNode firstChild, TreeNode nextSibling)
  {
    this.Data = data;
    this.FirstChild = firstChild;
    this.NextSibling = nextSibling;
  }
}

现在我们重新绘制你的图表 - 垂直线是第一个孩子，横线是下一个兄弟姐妹

Let's now redraw your diagram -- vertical lines are "first child", horizontal lines are "next sibling"

Root
 |
 p1 ----- p2 ----- p4 ----- p6  
 |        |         |       |
 c1       p3       c4       p7
          |                 |
          c2 - c3           c5

有意义吗？

现在，您可以使用此数据结构编写生成此树的代码吗？

Now, can you write code that produces this tree using this data structure? Start from the rightmost leaves and work your way towards the root:

TreeNode c5 = new TreeNode("c5", null, null);
TreeNode p7 = new TreeNode("p7", c5, null);
TreeNode p6 = new TreeNode("p6", p6, null);
... you do the rest ...

请注意，任意树只是一个二叉树旋转45度，其中根没有一个正确的孩子。二叉树和任意树是同样的东西;您只需为两个孩子分配不同的含义。

Notice that an arbitrary tree is just a binary tree "rotated 45 degrees", where the root never has a "right" child. Binary trees and arbitrary trees are the same thing; you just assign different meanings to the two children.

这篇关于如何实现非二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！