다음 포인터와 자식 포인터가있는 노드 유형을 사용하여 다중 경로 트리를 나타낼 수 있습니다.
노드의 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);
}
}
}
(I이 위 에릭의 대답과 비슷합니다 알고, 내가 아마 귀찮게하지 않았을이 하나를 쓰기 전에 그 답을 읽어 줄 경우 -하지만 난 이미 작성된 것입니다 내가하지 않았다 그냥 던져 버리고 싶다.)
노드 자식 대신리스트을 사용하지 않는 이유는 무엇입니까? –
Jerska
Collections 클래스를 사용할 수 없습니다. 나는 이것을 구현하기 위해서만 시스템을 사용할 수있다. –
'나는 Collections 클래스를 사용하지 않습니다. 왜 그런가요? 숙제 나 면접 과제입니까? –