0330 Tree 트리

여러 노드들이 가지처럼 연결되어 있는 비선형적 자료구조(Non-linear Data Structure)

트리는 계층적 구조를 가지는 사이클이 없는 그래드(Acrylic graph)의 일종이다.

 

가장 위에 루트로부터 출발하며, 그 밑에 여러 자식 노드들을 가지는 구조 (순회 x)

그 밑에 0개 이상의 자식 노드를 가질 수 있고, 그 자식 노드 각각은 다시 자기 자신의 자식 노드를 가질 수 있다.

 

루트

간선 edge 두 모드를 잇는 링크

자식 child

부모 parent

형제 sibling 부모가 같은 노드들

단말 leaf 자식을 갖지 않는 하단의 노드

높이 height 특정 노드에서 루트 사이의 길이 (윗쪽 방향으로 계산, 간선으로 측정)

깊이 depth 루트에서 노드까지 길이 (아랫쪽 방향)

트리 높이 가장 먼 거리에 있는 리프 노드와 루트 사이의 길이

레벨 루트 노트부터 수평적 깊이

노드의 차수 한 노드의 서브트리의 갯수

 

●n- 링크 표현법

각 노드에 최대 차수 n개 만큼의 링크를 두어 트리를 표현하는 방식

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>();
        }
    }

public class App
    {
        public App()
        {
            Console.WriteLine("App");

            var A = new TreeNode("A");
            var B = new TreeNode("B");
            var C = new TreeNode("C");
            var D = new TreeNode("D");

            A.links.Add(B);
            A.links.Add(C);
            A.links.Add(D);

            B.links.Add(new TreeNode("E"));
            B.links.Add(new TreeNode("F"));

            D.links.Add(new TreeNode("G"));

            //A의 자식 노드들을 출력 
            foreach (var node in A.links)
            {
                Console.Write("{0} ", node.data);
            }

        }
    }

 

public class TreeNode
    {
        public string data;
        public TreeNode[] links;
        //생성자 
        public TreeNode(string data, int max = 3)
        {
            this.data = data;
            this.links = new TreeNode[max];
        }
    }

public class App
    {
        public App()
        {
            Console.WriteLine("App");

            var A = new TreeNode("A");
            var B = new TreeNode("B");
            var C = new TreeNode("C");
            var D = new TreeNode("D");

            A.links[0] = B;
            A.links[1] = C;
            A.links[2] = D;

            B.links[0] = new TreeNode("E");
            B.links[1] = new TreeNode("F");

            D.links[0] = new TreeNode("G");

            //A의 자식 노드들을 출력 
            foreach (var node in A.links)
            {
                Console.Write("{0} ", node.data);
            }

        }
    }

 

 

●왼쪽자식-오른쪽형제노드 표현법

public class LCRSNode
    {
        public string data;
        public LCRSNode left;   //child
        public LCRSNode right;  //sibiling 
        //생성자 
        public LCRSNode(string data)
        {
            this.data = data;
        }
    }

public class App
    {
        public App()
        {
            Console.WriteLine("App");

            var A = new LCRSNode("A");
            var B = new LCRSNode("B");
            var C = new LCRSNode("C");
            var D = new LCRSNode("D");
            var E = new LCRSNode("E");
            var F = new LCRSNode("F");
            var G = new LCRSNode("G");

            A.left = B;
            B.right = C;
            C.right = D;

            B.left = E;
            E.right = F;

            D.left = G;

            //A의 자식들 출력 
            var temp = A.left;
            Console.Write("{0} ", temp.data);
            while (temp.right != null)
            {
                temp = temp.right;
                Console.Write("{0} ", temp.data);
            }
        }
    }

 

● LeftChildRightSibling 구현

public class LCRSTree
    {
        public LCRSNode root;
        public LCRSTree(string data) 
        {
            
        }
        public LCRSNode AddChild(LCRSNode parent, string data) 
        {
            if (parent == null) return null; 
            
            var node = new LCRSNode(data);

            //부모의 왼쪽 노드가 있는지 보고 없으면 넣고
            if (parent.left == null)
            {
                parent.left = node;
            }
            else 
            {
                //있으면 노드의 오른쪽 형제가 있는 지 검사
                //(오른쪽이 없을 때까지)
                var temp = parent.left;
                while(temp.right != null)
                {
                    temp = temp.right;
                }
                //오른쪽 형제가 없는 노드를 찾았다.
                temp.right = node;
            }
            return node;
        }
        public LCRSNode AddSibling(LCRSNode node, string data) 
        {
            if (node == null) return null;

            while (node.right != null) 
            {
                node = node.right;
            }
            var sibling = new LCRSNode(data);
            node.right = sibling;
            return sibling;
        }
    }

public class TreeNode
    {
        public string data;
        public TreeNode[] links;
        //생성자 
        public TreeNode(string data, int max = 3)
        {
            this.data = data;
            this.links = new TreeNode[max];
        }
    }

public class LCRSNode
    {
        public string data;
        public LCRSNode left;   //child
        public LCRSNode right;  //sibiling 
        //생성자 
        public LCRSNode(string data)
        {
            this.data = data;
        }
    }

 

public class LCRSTree
    {
        public LCRSNode root;
        //생성자 
        public LCRSTree(string data)
        {
            root = new LCRSNode(data);
        }

        public LCRSNode AddChild(LCRSNode parent, string data)
        {

            if (parent == null) return null;

            var node = new LCRSNode(data);

            //부모의 왼쪽노드 있는지 보고 없으면 넣고 
            if (parent.left == null)
            {
                parent.left = node;
            }
            else
            {
                //있으면 그 노드의 오른쪽 있는지 검사 (오른쪽이 없을때까지)
                var temp = parent.left;
                while (temp.right != null)
                {
                    temp = temp.right;
                }
                //오른쪽 형제가 없는 노드를 찾았다
                temp.right = node;
            }

            return node;
        }

        public LCRSNode AddSibiling(LCRSNode node, string data)
        {

            if (node == null) return null;

            while (node.right != null)
            {
                node = node.right;
            }
            var sibiling = new LCRSNode(data);
            node.right = sibiling;
            return sibiling;
        }

        public void PrintLevelOrder()
        {
            //Queue에 Root 노드 추가 
            var queue = new Queue<LCRSNode>();
            queue.Enqueue(this.root);

            //Queue에 요소가 있으면 계속 
            while (queue.Count > 0)
            {
                //꺼내서 
                var node = queue.Dequeue();

                //자식있는지 확인해서 있으면 Queue에 등록 
                if (node.left != null)
                {
                    queue.Enqueue(node.left);
                }

                //오른쪽 형제가 있는지 검사 
                while (node != null)
                {
                    //출력 
                    Console.Write("{0}", node.data);
                    node = node.right;
                }
            }
        }
    }

public App()
        {
            Console.WriteLine("App");
            LCRSTree tree = new LCRSTree("A");
            var A = tree.root;

            var B = tree.AddChild(A, "B");
            tree.AddChild(A, "C");

            var D = tree.AddSibiling(B, "D");

            tree.AddChild(B, "E");
            tree.AddChild(B, "F");

            tree.AddChild(D, "G");
            tree.PrintLevelOrder();

        }

 

 

부모가 가진 자식들을 알아내기 위해서 부모의 왼쪽 자식 노드를 거쳐 계속 오른쪽 형제 노드를 찾아가야 한다.

public class LCRSTree
    {
        public LCRSNode root;
        public LCRSTree(string data) 
        {
            this.root = new LCRSNode(data);
        }
        public LCRSNode AddChild(LCRSNode parent,string data) 
        {
            LCRSNode child = new LCRSNode(data);
            //자식이 없다면
            if (parent.left != null)
            {
                parent.left = new LCRSNode(data);
            }
            //자식이 있다면
            else {
                var temp = parent.left; //자식의 형제 확인
                while (temp.right != null) //형제가 있다면 반복 
                {
                    temp = temp.right;
                }
                //자식의 형제가 없다면 빠져나온다
                temp.right = child;
            } return child; //붙힌 자식을 나중에 부모로 사용하기 위해 반환함
        }
        public LCRSNode AddSibling(LCRSNode node, string data) 
        {
            //새 노드 생성
            LCRSNode sibling = new LCRSNode(data);
            
            //형제가 있을 경우 반복
            while (node.right != null) 
            {
                node = node.right;
            }
            //형제가 없을 경우 새 노드에 추가
            node.right = sibling;
            
            return sibling;
            
        }
    }

public class App
    {
        public App() 
        {
            LCRSTree tree = new LCRSTree("A");
            LCRSNode A = tree.root;
            LCRSNode B = tree.AddChild(A, "B");
            LCRSNode C = tree.AddChild(A, "C");
            LCRSNode D = tree.AddSibling(B, "D");
            tree.AddChild(B, "E");
            tree.AddChild(B, "F");
            tree.AddChild(D, "G");
        }
    }