Как реализовать небинарное дерево
У меня проблемы с реализацией недвоичного дерева, где корневой узел может иметь произвольное количество дочерних узлов. По сути, я хотел бы получить некоторые идеи о том, как с этим работать, поскольку у меня действительно есть некоторый написанный код, но я застрял в этой точке, что делать дальше. Кстати, я не могу использовать любой из классов Коллекции вообще. Я могу использовать только Систему.
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;
}
}
}
6 ответов
Пока решение Jerska является лучшим, но оно излишне сложно.
Поскольку я предполагаю, что это домашнее задание, позвольте мне дать вам направление, в котором вы должны идти. Структура данных, которую вы хотите:
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;
}
}
Давайте теперь перерисоваем вашу диаграмму - вертикальные линии - "первый ребенок", горизонтальные - "следующий брат"
Root
|
p1 ----- p2 ----- p4 ----- p6
| | | |
c1 p3 c4 p7
| |
c2 - c3 c5
Есть смысл?
Теперь, вы можете написать код, который создает это дерево, используя эту структуру данных? Начните с самых правых листьев и двигайтесь к корню:
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 градусов", где корень никогда не имеет "правильного" потомка. Бинарные деревья и произвольные деревья - это одно и то же; Вы просто назначаете разные значения двум детям.
Поскольку вы не можете использовать коллекцию, почему бы вам не создать свой собственный список?
class Child {
Node node;
Child next = null;
public Child (Node node) {
this.node = node;
}
public void addChild (Node node) {
if (this.next == null)
this.next = new Child (node);
else
this.next.addChild (node);
}
}
class Node {
public string data;
public Child children = null;
public Node (string data) {
this.data = data;
}
public void addChild (Node node) {
if (this.children == null)
this.children = new Child (node);
else
this.children.addChild (node);
}
}
И используйте это так:
Node root = new Node ("Hey");
root.addChild (new Node ("you"));
root.addChild (new Node ("me"));
Теперь у вас будет:
Node ("Hey")
/ \
Node ("you") Node ("me")
Тогда вам нужно будет реализовать различные функции (геттеры, смывки и т. Д.). Но это твоя работа.
Если вы не можете использовать какие-либо Коллекции, сохраните ссылку во всех дочерних элементах на родительский. Вы можете смоделировать свой график, используя следующую структуру данных:
class Node
{
public string Data { get; set; }
public Node Parent { get; set; }
public Node(string data, Node parent)
{
Data = data;
Parent = parent;
}
}
Теперь вы можете иметь столько дочерних элементов для каждого узла, сколько захотите:
var root = new Node("root", null);
var parent = new Node("parent", root);
var anotherParent = new Node("yetAnotherParent", root);
var child = new Node("Child", parent);
var anotherchild = new Node("anotherchild", parent);
class Node
{
public string data;
public Node parent;
public IEnumerable<Node> children;
public Node(string data, Node parent, IEnumerable<Node> children)
{
this.data = data;
this.parent = parent;
this.children = children;
}
}
Вы можете представить многоходовое дерево, используя тип узла, который имеет только следующий указатель и дочерний указатель.
Узел next указатель используется для указания на следующий дочерний элемент, реализованный в виде простого связанного списка.
Узел child указатель используется для указания на первый дочерний элемент узла.
Вот пример кода, который демонстрирует, как собрать это воедино. Он не содержит никакой обработки ошибок и не предназначен для полного решения, но вы должны быть в состоянии скомпилировать его и - при необходимости - запустить его под отладчиком, чтобы полностью понять, как он работает.
Я также добавил перечисляемый пример, чтобы показать, как можно перебирать узлы дерева. Возможно, вы захотите поиграть с этим, чтобы получить результаты в разных порядках. Если использование перечислимого является слишком сложным для того, что вам нужно, вам нужно написать свой собственный простой рекурсивный метод для посещения всех узлов.
Обратите внимание, что тип узла является общим в этом примере, и я использую его только для хранения строковых данных. Вы могли бы просто заменить T с типом, который вы хотите, если вы не хотите универсальный тип.
using System;
using System.Collections;
using System.Collections.Generic;
namespace Demo
{
sealed class Node<T>
{
public T Data; // Payload.
public Node<T> Next; // This will point to the next sibling node (if any), forming a linked-list.
public Node<T> Child; // This will point to the first child node (if any).
}
sealed class Tree<T>: IEnumerable<T>
{
public Node<T> Root;
public Node<T> AddChild(Node<T> parent, T data)
{
parent.Child = new Node<T>
{
Data = data,
Next = parent.Child // Prepare to place the new node at the head of the linked-list of children.
};
return parent.Child;
}
public IEnumerator<T> GetEnumerator()
{
return enumerate(Root).GetEnumerator();
}
private IEnumerable<T> enumerate(Node<T> root)
{
for (var node = root; node != null; node = node.Next)
{
yield return node.Data;
foreach (var data in enumerate(node.Child))
yield return data;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
class Program
{
void run()
{
var tree = new Tree<string>();
tree.Root = new Node<string>{Data = "Root"};
var l1n3 = tree.AddChild(tree.Root, "L1 N3");
var l1n2 = tree.AddChild(tree.Root, "L1 N2");
var l1n1 = tree.AddChild(tree.Root, "L1 N1");
tree.AddChild(l1n1, "L2 N1 C3");
tree.AddChild(l1n1, "L2 N1 C2");
var l2n1 = tree.AddChild(l1n1, "L2 N1 C1");
tree.AddChild(l1n2, "L2 N2 C3");
tree.AddChild(l1n2, "L2 N2 C2");
tree.AddChild(l1n2, "L2 N2 C1");
tree.AddChild(l1n3, "L2 N3 C3");
tree.AddChild(l1n3, "L2 N3 C2");
tree.AddChild(l1n3, "L2 N3 C1");
tree.AddChild(l2n1, "L3 N1 C3");
tree.AddChild(l2n1, "L3 N1 C2");
tree.AddChild(l2n1, "L3 N1 C1");
tree.Print();
}
static void Main()
{
new Program().run();
}
}
static class DemoUtil
{
public static void Print(this object self)
{
Console.WriteLine(self);
}
public static void Print(this string self)
{
Console.WriteLine(self);
}
public static void Print<T>(this IEnumerable<T> self)
{
foreach (var item in self)
Console.WriteLine(item);
}
}
}
(Я знаю, что это похоже на ответ Эрика выше, и если бы я прочитал этот ответ перед тем, как написать этот, я бы, наверное, не потрудился - но я уже написал это и не хотел просто выбросить его.)
Несколько случайных идей:
- Узлу понадобится какой-то список дочерних узлов, рассмотрите возможность использования реализации, защищенной от параллелизма, скорее всего
IEnumerable<NodeType>будет отвечать всем требованиям - Возможно, вы захотите или не захотите использовать обратный указатель для родителя, а тот - для быстрого (читай: не слишком хромого) обхода
- Я рекомендую вам создать
NodeType<T>облегчить жизнь при употреблении дерева