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

问题描述

我无法实现非二进制树，其中根节点可以有子节点的任意金额。基本上，我想就如何在那里与此去一些想法，因为我确实有一些代码写的，但我卡在下一步该怎么做了这一点。顺便说一句，我不能在所有使用任何的集合类。我只能用系统。

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

意义

Make sense?

现在，你可以写一个使用产生这个数据结构这棵树代码？的从最右边的叶子开始朝根你的工作方式的：

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屋！