유니티3D 프로그래밍
C# 4주차 5일 수업 내용 : Tree 복습 2, Graph (21.04.02) 본문
Binary Search Tree
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");
BST bst = new BST();
bst.Add(30);
bst.Add(25);
bst.Add(35);
bst.Add(21);
bst.Add(19);
bst.Add(23);
var target = 25;
Console.WriteLine("target: {0}", target);
var result = bst.Search(target);
Console.WriteLine("result: {0}", result);
Console.WriteLine();
target = 50;
Console.WriteLine("target: {0}", target);
result = bst.Search(target);
Console.WriteLine("result: {0}", result);
bst.Remove(23);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
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 Study02
{
public class BST
{
private BSTNode root;
//생성자
public BST()
{
}
//추가
public void Add(int data)
{
if (this.root == null)
{
this.root = new BSTNode(data);
}
else
{
//변수에 루트 담기
var node = this.root;
//변수의 값이 null아닐때까지 반복
while (node != null)
{
//비교
var result = data.CompareTo(node.data);
if (result == 0)
{
//같으면 값이 이미 있음
throw new ApplicationException("duplicated!");
}
else if (result < 0)
{
//넣을려고 하는 값이 노드의 값보다 작으면 (왼쪽)
if (node.left == null)
{
//왼쪽에 값이 없으면 새노드 붙이기
node.left = new BSTNode(data);
//종료
break;
}
else
{
//왼쪽에 값이 있으면 변수에 왼쪽 노드 설정
node = node.left;
}
}
else
{
//넣으려고 하는 값이 노드의 값보다 크면 (오른쪽)
if (node.right == null)
{
//오른쪽에 없으면 새노드 붙이기
node.right = new BSTNode(data);
//종료
break;
}
else
{
//오른쪽에 있으면 변수에 오른쪽 노드 설정
node = node.right;
}
}
}
}
}
//검색
public bool Search(int data)
{
//변수에 루트 넣기
var node = this.root;
//변수의 값이 null아닐경우 반복
while (node != null)
{
//검색하는 데이터와 변수에 있는 노드의 값과 비교
var 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)
{
//삭제할 노드 찾기
//node변수에 루트 넣기
var node = this.root;
BSTNode prev = null;
//node변수가 null이 아닐때까지 반복
while (node != null)
{
//삭제할 데이터와 node변수의 값을 비교
var result = data.CompareTo(node.data);
//같다 (찾았다)
if (result == 0)
{
break;
}
else if (result < 0)
{
//작다면 node변수에 node의 왼쪽 노드를 넣는다.
prev = node;
node = node.left;
}
else
{
//크다면 node변수에 node의 오른쪽 노드를 넣는다
prev = node;
node = node.right;
}
}
if (node != null)
{
Console.WriteLine("삭제하려고 하는 노드를 찾았습니다. {0}노드 ", node.data);
}
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개 인경우
//child 변수 선언 (찾은 노드의 자식)
//node의 왼쪽 노드가 있다면 왼쪽노드를 없다면 오른쪽 노드를 할당
var child = node.left != null ? node.left : node.right;
//부모의 왼쪽 노드와 node 비교
if (prev.left == node)
{
//같다면 부모의 왼쪽 노드에 child 할당
prev.left = child;
}
else
{
//다르다면 부모노드의 오른쪽 노드에 child 할당
prev.right = child;
}
}
return true;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class BST
{
private BSTNode root;
//생성자
public BST()
{
}
//추가
public void Add(int data)
{
if (this.root == null)
{
this.root = new BSTNode(data);
}
else
{
//변수에 루트 담기
var node = this.root;
//변수의 값이 null아닐때까지 반복
while (node != null)
{
//비교
var result = data.CompareTo(node.data);
if (result == 0)
{
//같으면 값이 이미 있음
throw new ApplicationException("duplicated!");
}
else if (result < 0)
{
//넣을려고 하는 값이 노드의 값보다 작으면 (왼쪽)
if (node.left == null)
{
//왼쪽에 값이 없으면 새노드 붙이기
node.left = new BSTNode(data);
//종료
break;
}
else
{
//왼쪽에 값이 있으면 변수에 왼쪽 노드 설정
node = node.left;
}
}
else
{
//넣으려고 하는 값이 노드의 값보다 크면 (오른쪽)
if (node.right == null)
{
//오른쪽에 없으면 새노드 붙이기
node.right = new BSTNode(data);
//종료
break;
}
else
{
//오른쪽에 있으면 변수에 오른쪽 노드 설정
node = node.right;
}
}
}
}
}
//검색
public bool Search(int data)
{
//변수에 루트 넣기
var node = this.root;
//변수의 값이 null아닐경우 반복
while (node != null)
{
//검색하는 데이터와 변수에 있는 노드의 값과 비교
var 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)
{
//삭제할 노드 찾기
//node변수에 루트 넣기
var node = this.root;
BSTNode prev = null;
//node변수가 null이 아닐때까지 반복
while (node != null)
{
//삭제할 데이터와 node변수의 값을 비교
var result = data.CompareTo(node.data);
//같다 (찾았다)
if (result == 0)
{
break;
}
else if (result < 0)
{
//작다면 node변수에 node의 왼쪽 노드를 넣는다.
prev = node;
node = node.left;
}
else
{
//크다면 node변수에 node의 오른쪽 노드를 넣는다
prev = node;
node = node.right;
}
}
if (node != null)
{
Console.WriteLine("삭제하려고 하는 노드를 찾았습니다. {0}노드 ", node.data);
}
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개 인경우
//child 변수 선언 (찾은 노드의 자식)
//node의 왼쪽 노드가 있다면 왼쪽노드를 없다면 오른쪽 노드를 할당
var child = node.left != null ? node.left : node.right;
//부모의 왼쪽 노드와 node 비교
if (prev.left == node)
{
//같다면 부모의 왼쪽 노드에 child 할당
prev.left = child;
}
else
{
//다르다면 부모노드의 오른쪽 노드에 child 할당
prev.right = child;
}
}
else
{
//자식 노드가 2개일경우
//pre 에 node넣기
var pre = node;
//min 에 node의 오른쪽 노드 넣기
var min = node.right;
//min에 왼쪽노드가 없을때까지 반복
while (min.left != null)
{
//있으면 pre 에 min 넣기
pre = min;
//min에 min왼쪽 노드 넣기
min = min.left;
}
//node에 min의 값을 넣기
node.data = min.data;
//pre의 왼쪽노드가 min과 같다면 제거 (null)
if (pre.left == min)
{
pre.left = min.right;
}
else
{
//그렇지 않다면 pre의 오른쪽 노드를 제거 (null)
pre.right = min.right;
}
}
return true;
}
}
}
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");
BSTList bst = new BSTList();
bst.Add(30);
bst.Add(25);
bst.Add(35);
bst.Add(21);
bst.Add(27);
bst.Add(32);
var list = bst.ToSortedList();
bst.Print(list);
var searchTarget = 25;
var result = bst.Search(searchTarget);
Console.WriteLine("searchTarget: {0}, result: {1}", searchTarget, result);
var removeTarget = 25;
result = bst.Remove(removeTarget);
Console.WriteLine("removeTarget: {0}, result: {1}", searchTarget, result);
list = bst.ToSortedList();
bst.Print(list);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class BSTList
{
private BSTNode root;
public void Add(int data)
{
if (this.root == null)
{
this.root = new BSTNode(data);
}
else
{
//변수에 루트 담기
var node = this.root;
//변수의 값이 null아닐때까지 반복
while (node != null)
{
//비교
var result = data.CompareTo(node.data);
if (result == 0)
{
//같으면 값이 이미 있음
throw new ApplicationException("duplicated!");
}
else if (result < 0)
{
//넣을려고 하는 값이 노드의 값보다 작으면 (왼쪽)
if (node.left == null)
{
//왼쪽에 값이 없으면 새노드 붙이기
node.left = new BSTNode(data);
//종료
break;
}
else
{
//왼쪽에 값이 있으면 변수에 왼쪽 노드 설정
node = node.left;
}
}
else
{
//넣으려고 하는 값이 노드의 값보다 크면 (오른쪽)
if (node.right == null)
{
//오른쪽에 없으면 새노드 붙이기
node.right = new BSTNode(data);
//종료
break;
}
else
{
//오른쪽에 있으면 변수에 오른쪽 노드 설정
node = node.right;
}
}
}
}
}
public List<BSTNode> ToSortedList() {
//동적 배열 생성
List<BSTNode> list = new List<BSTNode>();
this.Traversal(this.root, list);
return list;
}
public bool Search(int data)
{
//변수에 루트 넣기
var node = this.root;
//변수의 값이 null아닐경우 반복
while (node != null)
{
//검색하는 데이터와 변수에 있는 노드의 값과 비교
var 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)
{
//삭제할 노드 찾기
//node변수에 루트 넣기
var node = this.root;
BSTNode prev = null;
//node변수가 null이 아닐때까지 반복
while (node != null)
{
//삭제할 데이터와 node변수의 값을 비교
var result = data.CompareTo(node.data);
//같다 (찾았다)
if (result == 0)
{
break;
}
else if (result < 0)
{
//작다면 node변수에 node의 왼쪽 노드를 넣는다.
prev = node;
node = node.left;
}
else
{
//크다면 node변수에 node의 오른쪽 노드를 넣는다
prev = node;
node = node.right;
}
}
if (node != null)
{
Console.WriteLine("삭제하려고 하는 노드를 찾았습니다. {0}노드 ", node.data);
}
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개 인경우
//child 변수 선언 (찾은 노드의 자식)
//node의 왼쪽 노드가 있다면 왼쪽노드를 없다면 오른쪽 노드를 할당
var child = node.left != null ? node.left : node.right;
//부모의 왼쪽 노드와 node 비교
if (prev.left == node)
{
//같다면 부모의 왼쪽 노드에 child 할당
prev.left = child;
}
else
{
//다르다면 부모노드의 오른쪽 노드에 child 할당
prev.right = child;
}
}
else
{
//자식 노드가 2개일경우
//pre 에 node넣기
var pre = node;
//min 에 node의 오른쪽 노드 넣기
var min = node.right;
//min에 왼쪽노드가 없을때까지 반복
while (min.left != null)
{
//있으면 pre 에 min 넣기
pre = min;
//min에 min왼쪽 노드 넣기
min = min.left;
}
//node에 min의 값을 넣기
node.data = min.data;
//pre의 왼쪽노드가 min과 같다면 제거 (null)
if (pre.left == min)
{
pre.left = min.right;
}
else
{
//그렇지 않다면 pre의 오른쪽 노드를 제거 (null)
pre.right = min.right;
}
}
return true;
}
private void Traversal(BSTNode node, List<BSTNode> list)
{
if (node == null) return;
this.Traversal(node.left, list);
list.Add(node); //중위순회
this.Traversal(node.right, list);
}
public void Print(List<BSTNode> list)
{
foreach (var node in list)
{
Console.Write("{0} ", node.data);
}
Console.WriteLine();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class BSTNode
{
public int data;
public BSTNode left;
public BSTNode right;
//생성자
public BSTNode(int data)
{
this.data = data;
}
}
}
Graph
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class App
{
//생성자
public App()
{
Graph graph = new Graph();
//정점 생성
var seoul = new Node("서울");
graph.AddVertex(seoul);
var daejun = new Node("대전");
graph.AddVertex(daejun);
var daeku = new Node("대구");
graph.AddVertex(daeku);
var busan = new Node("부산");
graph.AddVertex(busan);
var kangrung = new Node("강릉");
graph.AddVertex(kangrung);
//간선 연결
graph.AddEdge(seoul, kangrung, 10);
graph.AddEdge(seoul, daeku, 7);
graph.AddEdge(seoul, daejun, 6);
graph.AddEdge(daeku, busan, 3);
graph.AddEdge(kangrung, daeku, 4);
graph.AddEdge(daejun, busan, 7);
graph.Print();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class Graph
{
public List<Node> nodes;
public bool directed;
//생성자
public Graph(bool directed = false)
{
//컬렉션 초기화
this.nodes = new List<Node>();
}
//정점(Vertex) 추가
public void AddVertex(Node node)
{
this.nodes.Add(node);
}
//간선(Edge) 추가
public void AddEdge(Node from, Node to, int weight = 1)
{
from.Neighbors.Add(to);
from.Weights.Add(weight);
if (!this.directed)
{
to.Neighbors.Add(from);
to.Weights.Add(weight);
}
}
//출력
public void Print()
{
foreach (var vertex in this.nodes)
{
var cnt = vertex.Neighbors.Count;
for (int i = 0; i < cnt; i++)
{
Console.WriteLine("{0} -- ({1}) -- {2}",
vertex.Data, vertex.Weights[i], vertex.Neighbors[i].Data);
}
}
}
}
}
Dictionary Graph
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class App
{
//생성자
public App()
{
Graph graph = new Graph();
graph.AddVertex("seoul");
graph.AddVertex("busan");
graph.AddVertex("mokpo");
graph.AddVertex("gangrung");
graph.AddVertex("daejun");
graph.AddVertex("daeku");
graph.AddEdge("seoul", "busan", 10);
graph.AddEdge("seoul", "daejun", 5);
graph.AddEdge("seoul", "daeku", 6);
graph.AddEdge("seoul", "gangrung", 7);
graph.AddEdge("seoul", "mokpo", 8);
graph.AddEdge("daejun", "daeku", 3);
graph.AddEdge("daejun", "busan", 5);
graph.AddEdge("daejun", "mokpo", 4);
graph.Print();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class Graph
{
//컬렉션
private Dictionary<string, List<Node>> dic;
//생성자
public Graph()
{
//인스턴스화
this.dic = new Dictionary<string, List<Node>>();
}
//vertex 추가
public void AddVertex(string key)
{
//키 중복 확인
if (!this.dic.ContainsKey(key))
{
this.dic.Add(key, new List<Node>());
}
}
//Edge 연결
public void AddEdge(string from, string to, int weight)
{
//from에 인접리스트에 vertex추가
var list = this.dic[from];
list.Add(new Node(to, weight));
}
//출력
public void Print()
{
foreach (var pair in this.dic)
{
var from = pair.Key; //from
//from의 인접리스트들
//edge는 vertex
foreach (var edge in pair.Value)
{
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 Study02
{
public class Node
{
public string key; //키
public int weight; //가중치
//생성자
public Node(string key, int weight = 1)
{
this.key = key;
this.weight = weight;
}
}
}
LinkedList Graph
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class App
{
//생성자
public App()
{
Graph graph = new Graph();
graph.AddVertex("seoul");
graph.AddVertex("busan");
graph.AddVertex("mokpo");
graph.AddVertex("gangrung");
graph.AddVertex("daejun");
graph.AddVertex("daeku");
graph.AddEdge("seoul", "busan", 10);
graph.AddEdge("seoul", "daejun", 5);
graph.AddEdge("seoul", "daeku", 6);
graph.AddEdge("seoul", "gangrung", 7);
graph.AddEdge("seoul", "mokpo", 8);
graph.AddEdge("daejun", "daeku", 3);
graph.AddEdge("daejun", "busan", 5);
graph.AddEdge("daejun", "mokpo", 4);
graph.Print();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class Edge
{
//시작
public string from;
//끝
public string to;
//가중치
public int weight;
public Edge(string from, string to, int weight)
{
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 Study02
{
public class Graph
{
public List<Node> nodes;
//생성자
public Graph()
{
this.nodes = new List<Node>();
}
public void AddVertex(string key)
{
this.nodes.Add(new Node(key));
}
public void AddEdge(string from, string to, int weight)
{
//정점리스트에서 from키를 갖는 요소(Node)를 찾는다.
var fromVertexs = this.nodes.Find(x => x.key == from);
//찾은 정점에
fromVertexs.edges.AddLast(new Edge(from, to, weight));
}
public void Print()
{
foreach(var vertex in this.nodes)
{
var from = vertex.key;
foreach(var edge in vertex.edges)
{
Console.WriteLine("[{0}]----[{1}]----[{2}]", edge.from, edge.weight, edge.to);
}
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class Node
{
public string key; //키
public LinkedList<Edge> edges;
//생성자
public Node(string key)
{
this.key = key;
this.edges = new LinkedList<Edge>();
}
}
}
'C# > 자료구조' 카테고리의 다른 글
| C# 5주차 1일 수업내용 : DFS, BFS (21.04.05) (0) | 2021.04.05 |
|---|---|
| C# 4주차 4일 수업 내용 : Tree 복습 (21.04.01) (0) | 2021.04.01 |
| C# 4주차 3일 수업 내용 : Tree (21.03.31) (0) | 2021.03.31 |
| C# 4주차 2일 수업 내용 : 자료구조 (21.03.30) (0) | 2021.03.30 |
'C#/자료구조' Related Articles
more
