자료구조 21.04.02.수업내용

HappyFrog 2021. 4. 2. 15:32

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");

            BSTTree tree = new BSTTree();
            
            tree.Add(50);
            tree.Add(20);            
            tree.Add(10);
            tree.Add(30);
            tree.Add(5);            
            tree.Add(8);            
            tree.Add(7);
            tree.Add(9);
            tree.Add(3);
            tree.Add(4);
            tree.Add(2);
            tree.Add(40);
            tree.Add(45);
            tree.Add(35);
            tree.Add(31);
            tree.Add(38);

            List<BSTNode> bList = new List<BSTNode>();

            

            

            
            var list = tree.ToSortedList();
            tree.Print(list);
            
            
            Console.WriteLine(tree.Search(38));
            Console.WriteLine(tree.Remove(38));



        }
    }
}

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

namespace Study801
{
    public class BSTTree
    {
        private BSTNode root;

        public  BSTTree()
        {

        }

        public void Add(int data)
        {
            if (root == null)
            {
                this.root = new BSTNode(data);
            }
            else
            {
                //변수에 루트 담기
                BSTNode temp = this.root;
                //변수의 값이 null값이 날 때까지 반복 
                while (temp != null)
                {
                    //비교
                    var result = data.CompareTo(temp.data);
                    //같으면 값이 이미 있음
                    if (result == 0)
                    {
                        throw new ApplicationException();
                    }
                    else if (result < 0)
                    {

                        //넣으려고 하는 값이 노드의 값보다 작으면(왼쪽)                        
                        if (temp.left == null)   //왼쪽에 없으면(왼쪽 = 새로 만든 노드 (data))
                        {

                            temp.left = new BSTNode(data);
                            break;
                        }
                        else                    //왼쪽에 값이 있으면 변수에 왼쪽 노드 설정
                        {
                            temp = temp.left;
                        }

                    }
                    else
                    {
                        //넣으려고 하는 값이 노드의 값보다 크면(오른쪽)
                        if(result > 0)//오른쪽에 없으면 새노드 붙이기
                        {
                            if(temp.right == null)
                            {
                                temp.right = new BSTNode(data);
                                break;
                            }
                            else//오른쪽에 있으면 변수에 오른쪽 노드 설정
                            {
                                temp = temp.right;
                            }
                        }                        
                    }
                }




            }
        }

        public bool Search(int data)
        {
            //변수에 루트 넣기
            var node = this.root;

            //변수의 값이 null이 아닐 경우 반복
            while (node != null)
            {
                //검색하는 데이터의 변수에 있는 노드의 값과 비교
                int result = data.CompareTo(node.data);

                //만약에 같다면 true 반환
                if(result == 0)
                {
                    return true;
                }

                //작다면 변수에 왼쪽 노드 반환
                else if (result < 0)
                {
                    //검색하려는 값이 변수에 있는 노드의 데이터보다 작다면
                    //변수의 값을 왼쪽 노드로 설정
                    node = node.left;
                }
                else
                {
                    node = node.right;
                    //검색하려는 값이 변수에 있는 노드의 데이터보다 크다면
                    //변수의 값을 오른쪽 노드로 설정
                }
            }
            //못찾았다면 false반환
            return false;
        }

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

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

            if(node != null)
            {
                Console.WriteLine("삭제하려는 노드 찾음.");
            }
            else
            {
                Console.WriteLine("삭제하려는 노드 찾지 못함.");

                return false;
            }

            if(node.left == null && node.right == null)
            {
                if(prev.left == node)
                {
                    prev.left = null;
                }
                else
                {
                    prev.right = null;
                }

            }

            else if ( node.left !=null || node.right != null)   //자식이 1개인 경우
            {                
                var child = node.left != null ? node.left : node.right;
                var temp = child.left;
                if (prev.left == node)   //node의 왼쪽 노드가 있다면 왼쪽 노드를 child에 할당, 왼쪽노드가 없다면 오른쪽 노드를 할당
                {
                    //부모의 왼쪽 노드와 node 비교
                    //같다면 부모의 왼쪽 노드에 child 할당
                    prev.left = child;
                    Console.WriteLine("[1 child, node = prev.left] target node : {0}", node.data);
                    node = prev.left;   //출력값을 위해서 쓴거임 원래는 node = null해야됨

                    while (temp.right != null)
                    {
                        temp = temp.right;
                    }
                    child = temp;
                    temp = null;
                    Console.WriteLine("[1 child, node = prev.left] child : {0}", child.data);
                    Console.WriteLine("[1 child, node = prev.left] node : {0}", node.data);
                    Console.WriteLine("[1 child, node = prev.left] prev : {0}", prev.data);

                }
                else                    
                {
                    //다르다면 부모노드의 오른쪽 노드에 child 할당
                    prev.right = child;
                    Console.WriteLine("[1 child, node = prev.right] target node : {0}", node.data);
                    node = prev.right;  //출력값을 위해서 쓴거임 원래는 node = null해야됨
                    
                    while(temp.right != null)
                    {
                        temp = temp.right;
                    }
                    child = temp;
                    temp = null;
                    Console.WriteLine("[1 child, node = prev.right] child : {0}", child.data);
                    Console.WriteLine("[1 child, node = prev.right] node : {0}", node.data);
                    Console.WriteLine("[1 child, node = prev.right] prev : {0}", prev.data);
                }
            }
            else if (node.left !=null && node.right != null)
            {

            }

           

            return false;
        }
    }
}

노드의 자식은 하나지만 그 자식이 자식노드를 더 가지고 있을때를 위한 식을 추가했다.

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");

            BSTTree tree = new BSTTree();
            
            tree.Add(50);
            tree.Add(20);            
            tree.Add(10);
            tree.Add(30);
            tree.Add(5);            
            tree.Add(8);            
            tree.Add(7);
            tree.Add(9);
            tree.Add(3);
            tree.Add(4);
            tree.Add(2);
            tree.Add(40);
            tree.Add(45);
            tree.Add(35);
            tree.Add(31);
            tree.Add(38);

            Console.WriteLine("30삭제");
            tree.Remove(30);
            Console.WriteLine("================================");
            Console.WriteLine("10삭제");
            tree.Remove(10);

        }
    }
}

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

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");

            Graph gr = new Graph();

            var seoul = new Node("서울");
            var daejeon = new Node("대전");
            var daegu = new Node("대구");
            var busan = new Node("부산");
            var gangrung = new Node("강릉");
            gr.AddVertex(seoul);
            gr.AddVertex(daejeon);
            gr.AddVertex(daegu);
            gr.AddVertex(busan);
            gr.AddVertex(gangrung);

            foreach (var vertex in gr.list)
            {
                Console.WriteLine(vertex.data);
            }

            gr.AddEdge(seoul, daejeon, 4);
            gr.AddEdge(seoul, daegu, 7);
            gr.AddEdge(seoul, busan, 10);
            gr.AddEdge(seoul, gangrung, 5);
            gr.AddEdge(daejeon, busan, 6);
            gr.AddEdge(daegu, gangrung, 4);
            gr.AddEdge(daegu, busan, 2); 

            
        }
    }
}

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

namespace Study801
{
    public class Graph
    {
        public List<Node> list;
      
        //생성자
        public Graph()
        {
            this.list = new List<Node>();
        }

        public void AddVertex(Node node)
        {            
            this.list.Add(node);
        }
        
        public void AddEdge(Node from, Node to, int weight)
        {
            from.neighbors.Add(to);
            from.Weights.Add(weight);
        }

        public void Print()
        {

        }

       
    }
}

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

namespace Study801
{
    public class Node
    {
        public string data
        {
            get; private set;
        }
        public int weight
        {
            get; private set;
        }
        public List<Node> neighbors;
        public List<int> Weights;

        public Node(string data)
        {
            this.data = data;
            this.neighbors = new List<Node>();
            this.Weights = new List<int>();
        }

        
    }
}

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

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

namespace Study801
{
    public class Graph
    {
        //컬렉션
        private Dictionary<string, List<Node>> dic;

        //생성자
        public Graph()
        {
            dic = new Dictionary<string, List<Node>>();
        }

        //추가
        public void AddVertex(string key)
        {
            if (!this.dic.ContainsKey(key))
            {
                this.dic.Add(key, new List<Node>());    //key값의 딕셔너리 생성.
            }           
        }

        public void AddEdge(string from, string to, int weight)
        {
            //from의 인접 리스트에 vertex 추가
            var list = this.dic[from];          //this.dic의 키값으로 from을 넣어서(만약 from이 이미 있을때.
            list.Add(new Node(to, weight));     //this.dic에 대한 value값 생성
        }

        //출력
        public void Print()
        {
            foreach(var pair in this.dic)   //this.dic 딕셔너리의 키 값을 각각 떼어내서
            {
                var from = pair.Key;    //"서울"

                
                foreach (var edge in pair.Value)    //딕셔너리에 대한 value들을 불러온다.
                {
                    //from에 인접한 리스트
                    Console.WriteLine("{0} -- ({1}) -- {2}", from, edge.weight, edge.key);
                }
            }
        }
    }
}

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");

            Graph gr = new Graph();

            gr.AddVertex("서울");
            gr.AddVertex("대전");
            gr.AddVertex("대구");
            gr.AddVertex("부산");
            gr.AddVertex("강릉");

            gr.AddEdge("서울", "대전", 5);

            gr.Print();
        }
    }
}

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

namespace Study801
{
    class Node
    {
        public string key;
        public int weight;

        //작성자
        public Node(string key, int weight = 1)
        {
            this.key = key;
            this.weight = weight;
        }
    }
}

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

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

namespace Study801
{
    public class Node
    {
        //키
        public string key;

        //간선들
        public LinkedList<Edge> edges;

        //생성자
        public Node(string key)
        {
            //컬렉션 초기화
            this.edges = new LinkedList<Edge>();
            
            this.key = key;
        }
    }
}

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

namespace Study801
{
    public class Graph
    {
        //정점 관리용 컬렉션 선언
        public List<Node> nodes;
        
        public Graph()
        {
            //컬렉션 인스턴스화
            nodes = new List<Node>();
        }

        public void AddVertex(string key)
        {
            this.nodes.Add(new Node(key));
        }

        public void AddEdge(string from, string to, int weight = 1)
        {
            //정점리스트에서 from키를 갖는 요소(Node)를 찾는다.
            var fromVertex = this.nodes.Find(x => x.key == from);
            //찾은 정점에 인접리스트에 간선 추가
            fromVertex.edges.AddLast(new Edge(from, to, weight));
        }

        public void Print()
        {
            foreach (var vertex in nodes)
            {
                var from = vertex.key;
                foreach(var edge in vertex.edges)
                {
                    Console.WriteLine("{0} -- ({1}) -- {2}", from, edge.weight, edge.to);
                }
            }
        }
    }
}

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

namespace Study801
{
    public class Edge
    {
        //어디로부터
        public string from;
        //어디를 향해
        public string to;
        //가중치
        public int weight;

        //생성자
        public Edge(string from, string to, int weight = 1)
        {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
}

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");

            Graph gr = new Graph();
            gr.AddVertex("서울");
            gr.AddVertex("부산");

            gr.AddEdge("서울", "부산", 10);

            gr.Print(); 
        }
    }
}