[3.30] Tree (일반적인 트리)

Tree의 대표적 형태인 Binary Tree, 이진트리이다.

정의

• 여러 노드들이 가지처럼 연결되어 있는 비선형적 자료구조.
• 나무를 뒤집어놓은 것 처럼 생겼다 (Root 노드부터 시작해서 여러개의 Child 노드로 이어진다)
• 자식은 부모노드를 하나만 가질 수 있고 부모노드는 여러개의 자식노드를 가질 수 있다.
• 표현은 N-링크 표현법과 왼쪽 자식, 오른쪽 형제 표현법이 있다.

1. N-링크 표현법

using System.Collections.Generic;

namespace Study01
{
    public class TreeNode
    {
        public string data;
        public List<TreeNode> links;

        public TreeNode(string data, int max = 3)
        {
            this.data = data;
            this.links = new List<TreeNode>();
        }
    }
}

 

2. 왼쪽 자식, 오른쪽 형제 표현법

namespace Study01
{
    public class LCRSNode
    {
        public string data;
        public LCRSNode left;       //child
        public LCRSNode right;      //silbling

        public LCRSNode(string data)
        {
            this.data = data;
        }
    }
}

using System;
using System.Collections.Generic;

namespace Study01
{
    public class Tree
    {
        private Node root;

        public Tree()
        {
            this.root = null;
        }

        public Node AddChild(Node parent, string data)
        {
            Node addNode = new Node(data);

            //루트노드가 없을때
            if (this.root == null)
            {
                this.root = new Node(data);
            }
            else
            {
                if (parent == null) return null;

                //루트노드가 있으면
                if (parent.left == null)
                {
                    parent.left = addNode;
                }
                else
                {
                    Node discover = parent.left;
                    while (discover.right != null)
                    {
                        discover = discover.right;
                    }
                    discover.right = addNode;
                }
            }
            return addNode;
        }

        public Node AddChild(Node parent, Node data)
        {
            Node addNode = data;

            //루트노드가 없을때
            if (this.root == null)
            {
                this.root = data;
            }
            else
            {
                if (parent == null) return null;

                //루트노드가 있으면
                if (parent.left == null)
                {
                    parent.left = addNode;
                }
                else
                {
                    Node discover = parent.left;
                    while (discover.right != null)
                    {
                        discover = discover.right;
                    }
                    discover.right = addNode;
                }
            }
            return addNode;
        }

        public Node AddSilbling(Node node, string data)
        {
            Node addNode = new Node(data);

            if (node == null) return null;

            if (node.right == null)
            {
                node.right = addNode;
            }
            else
            {
                while (node.right != null)
                {
                    node = node.right;
                }
                node.right = addNode;
            }
            return addNode;
        }

        //Preorder로 트리순회
        public void Print(Node node)
        {
            Console.Write("{0} ", node.data);

            if (node.left != null)
            {
                Print(node.left);
            }
            if (node.right != null)
            {
                Print(node.right);
            }
        }

        public void BFS()
        {
            Queue<Node> bfs = new Queue<Node>();

            bfs.Enqueue(this.root);
            while (bfs.Count > 0)
            {
                var item = bfs.Dequeue();
                while(item != null)
                {
                    Console.Write("{0} ",item.data);
                    if(item.left != null)
                    {
                        bfs.Enqueue(item.left);
                    }

                    item = item.right;
                }
                Console.WriteLine();
            }
        }
    }
}

using System;

namespace Study01
{
    public class App
    {
        public App()
        {
            Tree tree = new Tree();

            //root노드 설정
            Node root = new Node("홍길동");
            tree.AddChild(null, root);

            Node firstChild = new Node("임꺽정");
            tree.AddChild(root, firstChild);

            tree.AddSilbling(firstChild, "장길산");
            tree.AddSilbling(firstChild, "고길동");

            tree.AddChild(firstChild, "둘리");


            Console.WriteLine("BFS RESULT : ");
            tree.BFS();
            Console.WriteLine();

            Console.WriteLine("DFS RESULT : ");
            tree.Print(root);
            Console.WriteLine();
        }
    }
}

 

*DFS : 깊이 우선 탐색 (세로로 탐색)

 BFS : 너비 우선 탐색 (가로로 탐색)