C# 4주차 3일 수업 내용 : Tree (21.03.31)

Notice

Recent Posts

Recent Comments

Link

« 2025/09 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

Tags more

Archives

Today

Total

관리 메뉴

유니티3D 프로그래밍

C# 4주차 3일 수업 내용 : Tree (21.03.31) 본문

C#/자료구조

C# 4주차 3일 수업 내용 : Tree (21.03.31)

tjdgus9955 2021. 3. 31. 15:19

LCRSTree

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    public class App
    {

        public App()
        {
            Console.WriteLine("App");
            LCRSTree tree = new LCRSTree("A");
            LCRSNode A = tree.root;
            LCRSNode B = tree.AddChild(A, "B");
            tree.AddChild(A, "C");
            //B의 형제로 D를 추가 
            var D = tree.AddSibiling(B, "D");
            tree.AddChild(B, "E");
            tree.AddChild(B, "F");
            tree.AddChild(D, "G");

            tree.PrintLevelOrder();

        }

    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    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;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    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()
        {
            //큐 인스턴스 생성 
            var queue = new Queue<LCRSNode>();
            //큐에 root넣기 
            queue.Enqueue(this.root);

            //큐확인 
            while (queue.Count > 0)
            {
                //꺼냄 
                var node = queue.Dequeue();
                //형제 확인 
                while (node != null)
                {
                    //출력 
                    Console.Write("{0} ", node.data);

                    //자식있다면 큐에 등록 
                    if (node.left != null)
                    {
                        queue.Enqueue(node.left);
                    }

                    //다음 형제 확인 
                    node = node.right;
                }
            }
        }

        public void PrintIndent()
        {
            this.PrintIndentImpl(this.root, 1);
        }

        private void PrintIndentImpl(LCRSNode node, int indent)
        {

            if (node == null) return;

            string pad = " ".PadLeft(indent);
            Console.WriteLine("{0}{1}", pad, node.data);

            PrintIndentImpl(node.left, indent + 1);

            PrintIndentImpl(node.right, indent);
        }

    }
}

BinaryTree

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    public class App
    {

        public App()
        {
            Console.WriteLine("App");
            BinaryTreeArray tree = new BinaryTreeArray(7);  //트리 인스턴스화 
            tree.Root = "A";
            tree.SetLeft(0, "B");
            tree.SetRight(0, "C");
            tree.SetLeft(1, "D");
            tree.SetLeft(2, "F");
            tree.Print();
            var parent = tree.GetParent(5);
            Console.WriteLine(parent);
            var left = tree.GetLeft(2);
            Console.WriteLine(left);

        }

    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    public class BinaryTreeArray
    {
        private string[] arr;
        public string Root
        {
            get
            {
                return this.arr[0];
            }
            set
            {
                this.arr[0] = value;
            }
        }
        //생성자 
        public BinaryTreeArray(int capacity)
        {
            //배열 생성 
            this.arr = new string[capacity];
        }

        //왼쪽추가 
        public void SetLeft(int parentIndex, string data)
        {

            int leftIndex = (parentIndex * 2) + 1;

            //부모가 없거나 배열이 full인경우 
            if (this.arr[parentIndex] == null || leftIndex >= this.arr.Length)
            {
                throw new ApplicationException("Error!");
            }

            this.arr[leftIndex] = data;
        }

        //왼쪽 요소 가져오기 
        public string GetLeft(int parentIndex)
        {
            int leftIndex = (parentIndex * 2) + 1;

            return this.arr[leftIndex];
        }

        //오른쪽 추가 
        public void SetRight(int parentIndex, string data)
        {
            int rightIndex = (parentIndex * 2) + 2;

            //부모가 없거나 배열이 full인경우 
            if (this.arr[parentIndex] == null || rightIndex >= this.arr.Length)
            {
                throw new ApplicationException("Error!");
            }

            this.arr[rightIndex] = data;
        }

        //오른쪽 가져오기 
        public string GetRight(int parentIndex)
        {
            int rightIndex = (parentIndex * 2) + 2;
            return this.arr[rightIndex];
        }

        //부모 요소 가져오기 
        public string GetParent(int childIndex)
        {

            if (childIndex == 0) return null;

            int parentIndex = (childIndex - 1) / 2;
            return this.arr[parentIndex];
        }

        //출력 
        public void Print()
        {
            for (int i = 0; i < this.arr.Length; i++)
            {
                Console.Write("{0}", this.arr[i] ?? "-");
            }
            Console.WriteLine();
        }
    }
}

BinaryTree 전위, 중위, 후위

using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    public class App
    {

        public App()
        {
            Console.WriteLine("App");
            BinaryTree tree = new BinaryTree("A");
            tree.root.left = new BinaryNode("B");
            tree.root.right = new BinaryNode("C");
            tree.root.left.left = new BinaryNode("D");
            tree.root.left.right = new BinaryNode("E");
            tree.root.right.left = new BinaryNode("F");

            tree.PreorderTraversal();
        }

    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    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 = child;    //부모의 왼쪽에 붙임 
            }
            //자식이 있다면 
            else
            {
                //자식의 형제 확인
                var temp = parent.left; //parent는 A일때 B의 형제 확인
                while (temp.right != null)
                { //형제가 있다면 반복 
                    temp = temp.right;  //다음형제 확인 
                }
                //temp의 형제가 없을 경우 temp의 오른쪽에 붙임 
                temp.right = child;
            }

            return child;   //붙인 자식을 나중에 부모로 사용하기 위해 반환함 
        }

        public LCRSNode AddSibiling(LCRSNode node, string data)
        {

            //새 노드를 생성 
            LCRSNode sibling = new LCRSNode(data);

            //형제가 있을경우 반복 
            while (node.right != null)
            {
                node = node.right;
            }
            //node는 형제가 없음 
            //node의 오른쪽에 새 노드 추가 
            node.right = sibling;

            //새롭게 추가된 노드를 반환 
            return sibling;
        }
        //전위 순회(Preorder Traversal)
        public void PreorderTraversal()
        {
            this.PreorderTraversalmple(root);
        }


        //전위 순회 구현

        private void PreorderTraversalmple(LCRSNode node)
        {
            if (node == null) return;
            Console.WriteLine(node.data);

            this.PreorderTraversalmple(node.left);
            this.PreorderTraversalmple(node.right);
        }

        public void InorderTraversal()
        {
            this.InorderTraversalmple(root);
        }

        private void InorderTraversalmple(LCRSNode node)
        {
            if (node == null) return;

            this.InorderTraversalmple(node.left);
            Console.WriteLine(node.data);
            this.InorderTraversalmple(node.right);
        }

        public void PostorderTraversal()
        {
            this.PostorderTraversalmple(root);
        }

        private void PostorderTraversalmple(LCRSNode node)
        {
            if (node == null) return;

            this.PostorderTraversalmple(node.left);
            Console.WriteLine(node.data);
            this.PostorderTraversalmple(node.right);
        }

    }
}

using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    public class App
    {

        public App()
        {
            Console.WriteLine("App");
            BinaryTree tree = new BinaryTree("A");
            tree.root.left = new BinaryNode("B");
            tree.root.right = new BinaryNode("C");
            tree.root.left.left = new BinaryNode("D");
            tree.root.left.right = new BinaryNode("E");
            tree.root.right.left = new BinaryNode("F");

            tree.InorderTraversal();
        }

    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    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 = child;    //부모의 왼쪽에 붙임 
            }
            //자식이 있다면 
            else
            {
                //자식의 형제 확인
                var temp = parent.left; //parent는 A일때 B의 형제 확인
                while (temp.right != null)
                { //형제가 있다면 반복 
                    temp = temp.right;  //다음형제 확인 
                }
                //temp의 형제가 없을 경우 temp의 오른쪽에 붙임 
                temp.right = child;
            }

            return child;   //붙인 자식을 나중에 부모로 사용하기 위해 반환함 
        }

        public LCRSNode AddSibiling(LCRSNode node, string data)
        {

            //새 노드를 생성 
            LCRSNode sibling = new LCRSNode(data);

            //형제가 있을경우 반복 
            while (node.right != null)
            {
                node = node.right;
            }
            //node는 형제가 없음 
            //node의 오른쪽에 새 노드 추가 
            node.right = sibling;

            //새롭게 추가된 노드를 반환 
            return sibling;
        }
        //전위 순회(Preorder Traversal)
        public void PreorderTraversal()
        {
            this.PreorderTraversalmple(root);
        }


        //전위 순회 구현

        private void PreorderTraversalmple(LCRSNode node)
        {
            if (node == null) return;
            Console.WriteLine(node.data);

            this.PreorderTraversalmple(node.left);
            this.PreorderTraversalmple(node.right);
        }

        public void InorderTraversal()
        {
            this.InorderTraversalmple(root);
        }

        private void InorderTraversalmple(LCRSNode node)
        {
            if (node == null) return;

            this.InorderTraversalmple(node.left);
            Console.WriteLine(node.data);
            this.InorderTraversalmple(node.right);
        }

        public void PostorderTraversal()
        {
            this.PostorderTraversalmple(root);
        }

        private void PostorderTraversalmple(LCRSNode node)
        {
            if (node == null) return;

            this.PostorderTraversalmple(node.left);
            Console.WriteLine(node.data);
            this.PostorderTraversalmple(node.right);
        }

    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    public class App
    {

        public App()
        {
            Console.WriteLine("App");
            BinaryTree tree = new BinaryTree("A");
            tree.root.left = new BinaryNode("B");
            tree.root.right = new BinaryNode("C");
            tree.root.left.left = new BinaryNode("D");
            tree.root.left.right = new BinaryNode("E");
            tree.root.right.left = new BinaryNode("F");

            tree.PostorderTraversal();
        }

    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    public class BinaryTree
    {
        public BinaryNode root;

        //생성자 
        public BinaryTree(string data)
        {
            //배열 생성 
            this.root = new BinaryNode(data);
        }

        //출력 
        public void Print()
        {
            
        }

        public void PreorderTraversal()
        {
            this.PreorderTraversalmple(root);
        }


        //전위 순회 구현

        private void PreorderTraversalmple(BinaryNode node)
        {
            if (node == null) return;
            Console.WriteLine(node.data);

            this.PreorderTraversalmple(node.left);
            this.PreorderTraversalmple(node.right);
        }

        public void InorderTraversal()
        {
            this.InorderTraversalmple(root);
        }

        private void InorderTraversalmple(BinaryNode node)
        {
            if (node == null) return;

            this.InorderTraversalmple(node.left);
            Console.WriteLine(node.data);
            this.InorderTraversalmple(node.right);
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    public class BinaryNode
    {
        public string data;
        public BinaryNode left;
        public BinaryNode right;
        public BinaryNode(string data)
        {
            this.data = data;
        }
    }
}

Stack Preorder

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    public class App
    {

        public App()
        {
            Console.WriteLine("App");
            BinaryTree tree = new BinaryTree("A");
            tree.root.left = new BinaryNode("B");
            tree.root.right = new BinaryNode("C");
            tree.root.left.left = new BinaryNode("D");
            tree.root.left.right = new BinaryNode("E");
            tree.root.right.left = new BinaryNode("F");

            tree.PreorderIterative();
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study02
{
    public class BinaryTree
    {
        public BinaryNode root;

        //생성자 
        public BinaryTree(string data)
        {
            //배열 생성 
            this.root = new BinaryNode(data);
        }
        
        //출력
        public void PreorderIterative()
        {
            //스택을 만든다 
            var stack = new Stack<BinaryNode>();
            //루트를 넣는다 
            stack.Push(this.root);
            //스택요소가 있다면 반복 한다 
            while (stack.Count > 0)
            {
                //꺼낸다 
                var node = stack.Pop();
                //출력한다
                Console.Write("{0} ", node.data);

                //오른쪽 넣는다 
                if (node.right != null)
                {
                    stack.Push(node.right);
                }

                //왼쪽 넣는다 
                if (node.left != null)
                {
                    stack.Push(node.left);
                }
            }
        }
    }
}

'C# > 자료구조' 카테고리의 다른 글

C# 5주차 1일 수업내용 : DFS, BFS (21.04.05) (0)	2021.04.05
C# 4주차 5일 수업 내용 : Tree 복습 2, Graph (21.04.02) (0)	2021.04.02
C# 4주차 4일 수업 내용 : Tree 복습 (21.04.01) (0)	2021.04.01
C# 4주차 2일 수업 내용 : 자료구조 (21.03.30) (0)	2021.03.30

'C#/자료구조' Related Articles

유니티3D 프로그래밍

C# 4주차 3일 수업 내용 : Tree (21.03.31) 본문

C# 4주차 3일 수업 내용 : Tree (21.03.31)

'C# > 자료구조' 카테고리의 다른 글

티스토리툴바