자료구조 21.04.01.수업내용

 

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

namespace Study801
{
    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 == null)
            {
                this.root.left = child;
            }

            else if (parent.left == null)
            {
                parent.left = child;
            }

            else
            {
                LCRSNode 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);

            if(node.right == null)
            {
                node.right = sibling;
            }
            else
            {
                LCRSNode temp = node.right;
                while(temp.right != null)
                {
                    temp = temp.right;
                }
                temp.right = sibling;
            }

            return sibling;               
        }

        public void PrintLevelOrder(LCRSNode node, int indent)
        {
            if (node == null) return;

            
            Console.WriteLine("{0}, {1}", node.data, indent);

            this.PrintLevelOrder(node.left, indent+1);

            this.PrintLevelOrder(node.right, indent);            
        }
    }
}

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

namespace Study801
{
    class LCRSNode
    {
        public LCRSNode left;
        public LCRSNode right;
        public string data;

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

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

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

            LCRSTree tree = new LCRSTree("A");
            
            LCRSNode A = tree.root;
            

            LCRSNode B = tree.AddChild(A, "B");
            LCRSNode C = tree.AddSibling(B, "C");
            LCRSNode D = tree.AddChild(B, "D");
            LCRSNode E = tree.AddSibling(D, "E");
            LCRSNode F = tree.AddChild(C, "F");

            tree.PrintLevelOrder(tree.root, 1);
            
        }
    }
}

============================================================================

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

namespace Study801
{
    class BinaryTreeUsingArray
    {

        public string[] arr;
        public string root
        {
            get
            {
                return this.arr[0];
            }
            set
            {
                this.arr[0] = value;
            }
        }

        //생성자
        public BinaryTreeUsingArray(int capacity)
        {
            //배열 생성
            this.arr = new string[capacity];
        }

        //왼쪽 추가
        public void AddLeft(int parentIndex, string data)
        {
            var leftIndex = (parentIndex * 2) + 1;
            this.arr[leftIndex] = data;
        }

        //오른쪽 추가
        public void AddRight(int parentIndex, string data)
        {
            var rightIndex = (parentIndex * 2) + 2;
            this.arr[rightIndex] = data;
        }

        //왼쪽 가져오기
        public string GetLeft(int parentIndex)
        {
            var leftIndex = (parentIndex * 2) + 1;
            return this.arr[leftIndex]; 
        }

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

        //부모요소 가져오기
        public string GetParent(int childIndex)
        {
            var parentIndex = (childIndex - 1) / 2;
            return this.arr[parentIndex];
        }

        //트리 출력
        public void Print()
        {
            for(int i = 0; i < this.arr.Length; i++)
            {
                var element = this.arr[i];
                if(element == null)
                {
                    Console.Write("-");
                }
                else
                {
                    Console.Write("{0}", element);
                }
            }
        }
    }
}

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

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

            BinaryTreeUsingArray bTree = new BinaryTreeUsingArray(10);

            bTree.root = "A";
            bTree.AddLeft(0, "B");
            bTree.AddRight(0, "C");
            bTree.AddLeft(1, "D");
            bTree.AddRight(1, "E");
            bTree.AddLeft(2, "F");
            bTree.AddRight(2, "G");

            bTree.Print();
        }
    }
}

============================================================================

이진 탐색 트리

 

줄 왼쪽 노드의 값이 루트 노드의 값보다 작고, 오른쪽노드의 값이 루트노드의 값보다 더 큰 값을 갖는 트리를 가리키는데, 이러한 값 순서는 이진탐색트리의 모든 서브트리에 적용된다. 이진 탐색 트리는 왼쪽에서 루트를 통해 오른쪽으로 순서에 맞춰 키가 정렬되어 있어서 Odered BIanry  Tree 또는 Sorted Bianary트리로 불린다.

주로 중위 순회 방식을 사용한다.

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

namespace Study801
{
    public class BinarySearchTree
    {
        public BSTNode root;
        public BinarySearchTree(int data)
        {
            this.root = new BSTNode(data);
        }
        
        public void Add(int data)
        {
            if (this.root == null)
            {
                this.root = new BSTNode(data);
            }

            BSTNode node = this.root;
            var result = data.CompareTo(node.data);

            while (node != null)
            {
                if (result == 0)
                {
                    throw new ApplicationException();
                }
                else if (result > 0)
                {
                    if (node.right == null)
                    {
                        node.right = new BSTNode(data);
                        break;
                    }
                    else
                    {
                        node = node.right;
                        continue;
                    }
                }
                else
                {
                    if (node.left == null)
                    {
                        node.left = new BSTNode(data);
                        break;
                    }
                    else
                    {
                        node = node.left;
                        continue;
                    }
                }
            }
        }

        public bool Search(int data)
        {
            var node = this.root;
            while(node != null)
            {
                var result = data.CompareTo(node.data);

                if(result == 0)
                {
                    return true;
                }

                else if(result < 0)
                {
                    node = node.left;
                }
                else
                {
                    node = node.right;
                }
            }
            return false;
        }
        public bool SearchRecursive(int data)
        {
            return SearchRecursiveImple(this.root, data);
        }

        private bool SearchRecursiveImple(BSTNode node, int data)
        {
            if (node == null)
                return false;

            var result = data.CompareTo(node.data);

            if(result == 0)            
                return true;                       

            return SearchRecursiveImple(node.left, data) || SearchRecursiveImple(node.right, data);
        }


        public bool Remove(int data)
        {
            BSTNode node= this.root;
            BSTNode prev = null;

            while (node != null)
            {
                var comp = data.CompareTo(node.data);
                if(comp == 0)
                {
                    break;
                }
                else if(comp < 0)
                {
                    prev = node;
                    node = node.left;
                }
                else
                {
                    prev = node;
                    node = node.right;
                }
            }

            if (node == null) return false;

            //노드를 찾음(삭제 진행)
            //왼쪽노드 오른쪽노드가 없는경우
            if(node.left == null && node.right == null)
            {
                if(prev.left == node)
                {
                    prev.left = null;
                }
                else
                {
                    prev.right = null;
                }

                node = null;
            }

            //둘 중 하나라도 자식노드가 있는 경우
            else if (node.left != null || node.right != null)
            {
                //왼쪽 노드 또는 오른쪽 노드가 있는 경우
                var child = node.left != null ? node.left : node.right; //삼항연산자
                if(prev.left == node)
                {
                    prev.left = child;
                }
                else
                {
                    prev.right = child;
                }
                node = null;
            }

            else
            {
                //왼쪽 노드, 오른쪽 노드 둘 다 있는 경우
                //현재 노드
                var pre = node;
                //검색된 노드의 오른쪽 자식
                var min = node.right;

                while(min.left != null) //노드로 대체할 값 중 가장 작은 값을 찾는다. (min) right로 한 번 가고 그 다음부턴 계속 left로 실행.
                {                       //ex)5를 제거하고싶을 때 5다음으로 가장 작은 수는 최소 6일 것이기 때문에 right로 한 번 가고 left로 반복 이동해주면 최소값이 나오게 된다.
                    pre = min;          
                    min = min.left;
                }

                node.data = min.data;   //구한 최소값 대입하며 없애려 했던 data는 사라짐


                //min 노드의 오른쪽 노드 처리
                if(pre.left == min)
                {
                    pre.left = min.right;
                }
                else
                {
                    pre.right = min.right;  //min의 부모노드는 left right가 있고 min은 left가 없는경우.
                }

                return true;

            }
            
        }
    }   
}

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

namespace Study801
{
    public class BSTNode
    {
        public int data;
        public BSTNode left;
        public BSTNode right;

        public BSTNode(int data)
        {
            this.data = data;
        }
    }
}

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

namespace Study801
{
    public class App
    {
        //생성자 
        public App()
        {
            Console.WriteLine("App");

            BinarySearchTree tree = new BinarySearchTree(4);
            tree.Add(3);
            tree.Add(2);
            tree.Add(1);
            tree.Add(5);
            tree.Add(6);
            tree.Add(7);
            tree.Add(8);

            var result = tree.Search(3);
            Console.WriteLine(result);
        }
    }
}

코드가 간단해서 그런지 이해도 잘 되고 코드도 잘 만들어진다. 스택때와는 다르게

++)간단하다는말은 취소

 

============================================================================