자료구조: 다중 트리 (Multi-Tree)

자료구조의 트리란,

부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조다. 단, 자식 노드의 자식이 부모로 연결되는 경우는 보통 트리로 인정하지 않는다.

이라고 나무위키에 설명되어 있습니다. 트리에 대한 자세한 설명은 나무위키를 참고하세요.
보통 이진 트리 (Binary Tree)를 많이 사용하는데 저는 자식 노드를 2개 이상 가지는 다중 트리(Multi-Tree)가 필요해서 구현해 봤습니다.
 

이진 트리 - 위키백과, 우리 모두의 백과사전

 
 

---

 
 

✅ 다중 트리 (Multi-Tree)

 
 
 

다중 트리

 
 

---

 
 

Interface

ITreeNode.cs

public interface ITreeNode<T>
{
    T Data { get; set; }    
    IEnumerable<ITreeNode<T>> Children { get; }
    void AddChild(T data);
    void RemoveChild(T data);
    ITreeNode<T> FindNode(T data);        
}

Node는
Data,
하위노드,
하위노드 추가,
하위노드 삭제,
노드 검색 의 기능을 가집니다.
 
 

ITree.cs

public interface ITree<T>
{
    ITreeNode<T> Root { get; set; }
}

 
 

---

 
 

class

TreeNode.cs

public class TreeNode<T> : ITreeNode<T>
{
    public string? Name { get; set; }
    public T Data { get; set; }
    private List<ITreeNode<T>> _children;
    public IEnumerable<ITreeNode<T>> Children => _children.AsReadOnly();

    [AllowNull]
    public ITreeNode<T> Parent { get; set; }

    public TreeNode(T data)
    {
        Data = data;
        _children = new List<ITreeNode<T>>();
    }

    public void AddChild(T data)
    {
        TreeNode<T> child = new TreeNode<T>(data);
        _children.Add(child);
    }

    public void RemoveChild(T data)
    {
        _children.RemoveAll(child => EqualityComparer<T>.Default.Equals(child.Data, data));
    }

    public ITreeNode<T> FindNode(T data)
    {
        if (EqualityComparer<T>.Default.Equals(Data, data))
        {
            return this;
        }

        foreach (var child in Children)
        {
            var foundNode = child.FindNode(data);
            if (foundNode != null)
            {
                return foundNode;
            }
        }

        return null;
    }        
}

 
 

Tree.cs

public class Tree<T> : ITree<T>
{
    public ITreeNode<T> Root { get; set; }

    public Tree(T data) => Root = new TreeNode<T>(data);

    public void Traverse(ITreeNode<T> node, Action<ITreeNode<T>> action)
    {
        if (node == null)
            return;

        action(node);

        foreach (var child in node.Children)
        {
            Traverse(child, action);
        }
    }

}

 
Tree 클래스는 Root 노드를 가지고 있고 전체 트리를 깊이우선탐색 (DPS)으로 순회하는 Traverse 함수를 제공합니다.
 
 

---

 

사용 예제

 

Tree<string> tree = new Tree<string>("root");
tree.Root.AddChild("1");
tree.Root.AddChild("2");

tree.Root.Children.ElementAt(0).AddChild("1.1");
tree.Root.Children.ElementAt(0).AddChild("1.2");

tree.Root.Children.ElementAt(1).AddChild("2.1");
tree.Root.Children.ElementAt(1).AddChild("2.2");

tree.Root.FindNode("2.2");

tree.Traverse(tree.Root, n => Debug.WriteLine(n.Data));

 

 

✅ 다중 트리 (Multi-Tree) - 끝

관련 포스팅

 

WPF로 Windows 파일탐색기 만들기 #3 (TreeView)

 

WPF로 Windows 파일탐색기 만들기 #4 (Directory)