유니티3D 프로그래밍
C# 4주차 4일 수업 내용 : Tree 복습 (21.04.01) 본문
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");
BinaryTree tree = new BinaryTree("A");
tree.root.left = new BinaryTreeNode("B");
tree.root.right = new BinaryTreeNode("C");
tree.root.left.left = new BinaryTreeNode("D");
tree.root.left.right = new BinaryTreeNode("E");
tree.root.right.left = new BinaryTreeNode("F");
//tree.PrintPreorderIterative();
tree.PrintInorderIterative();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class BinaryTree
{
public BinaryTreeNode root;
//생성자
public BinaryTree(string data)
{
this.root = new BinaryTreeNode(data);
}
public void PrintPreorderTraversal()
{
this.PreorderTraversal(this.root);
}
private void PreorderTraversal(BinaryTreeNode node)
{
if (node == null) return;
//출력
Console.Write("{0} ", node.data);
this.PreorderTraversal(node.left);
this.PreorderTraversal(node.right);
}
public void PrintPreorderIterative()
{
//스택을 만든다
var stack = new Stack<BinaryTreeNode>();
//루트 넣는다
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);
}
}
public void PrintInorderIterative()
{
//스택을 만든다
var stack = new Stack<BinaryTreeNode>();
//변수에 루트 넣기
var node = this.root;
//루트노드에서 최좌측 까지 스택에 저장
while (node != null)
{
stack.Push(node);
node = node.left;
}
//스택에 요소가 있다면 반복
while (stack.Count > 0)
{
//꺼낸다
var popNode = stack.Pop();
//출력한다
Console.WriteLine(popNode.data);
if (popNode.right != null)
{
//오른쪽 노드가 있는지 확인해서 있으면
//오른쪽 노드의 서브트리의 최좌측까지 스택에 저장
var temp = popNode.right;
while (temp != null)
{
stack.Push(temp);
temp = temp.left;
}
}
}
}
}
}
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;
}
}
}
-----------------------------------------------------------------------------------------------------------------------------------
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 BinaryTreeNode("B");
tree.root.right = new BinaryTreeNode("C");
tree.root.left.left = new BinaryTreeNode("D");
tree.root.left.right = new BinaryTreeNode("E");
tree.root.right.left = new BinaryTreeNode("F");
//tree.PrintPreorderIterative();
//tree.PrintInorderIterative();
tree.PrintInorderIterative2();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class BinaryTree
{
public BinaryTreeNode root;
//생성자
public BinaryTree(string data)
{
this.root = new BinaryTreeNode(data);
}
public void PrintPreorderTraversal()
{
this.PreorderTraversal(this.root);
}
private void PreorderTraversal(BinaryTreeNode node)
{
if (node == null) return;
//출력
Console.Write("{0} ", node.data);
this.PreorderTraversal(node.left);
this.PreorderTraversal(node.right);
}
public void PrintPreorderIterative()
{
//스택을 만든다
var stack = new Stack<BinaryTreeNode>();
//루트 넣는다
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);
}
}
//중위순회
//D B E A C
public void PrintInorderIterative()
{
//스택을 만든다
var stack = new Stack<BinaryTreeNode>();
//변수에 루트를 넣는다
var node = this.root;
//최좌측 노드들을 스택에 넣는다
while (node != null)
{
stack.Push(node);
node = node.left;
}
//스택에 요소가 있다면 반복
while (stack.Count > 0)
{
//꺼낸다
var popNode = stack.Pop();
//출력
Console.Write("{0} ", popNode.data);
//오른쪽 노드 확인
var temp = popNode.right;
if (temp != null)
{
//오른쪽 노드를 포함한 최좌측 노드들을 스택에 넣기
stack.Push(temp);
temp = popNode.left;
}
}
}
public void PrintInorderIterative2()
{
//스택 만든다
var stack = new Stack<BinaryTreeNode>();
//변수에 루트 넣는다
var node = this.root;
//변수에 노드가 있거나 스택에 요소가 있다면 반복
while (node != null || stack.Count > 0)
{
//변수에 노드가 있다면 반복
while (node != null)
{
//변수의 노드를 스택에 넣는다
stack.Push(node);
//변수에 노드의 왼쪽 노드를 넣는다
node = node.left;
}
//스택에서 꺼냄
node = stack.Pop();
//출력
Console.WriteLine("{0} ", node.data);
//변수에 오른쪽 노드를 넣는다 (스택에 오른쪽에 있는 서브루트에서 최좌측까지 넣기 위함)
node = node.right;
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class BinaryTreeNode
{
public string data;
public BinaryTreeNode left;
public BinaryTreeNode right;
//생성자
public BinaryTreeNode(string data)
{
this.data = data;
}
}
}
namespace Study02
{
public class App
{
//생성자
public App()
{
Console.WriteLine("App");
BinaryTree tree = new BinaryTree("A");
tree.root.left = new BinaryTreeNode("B");
tree.root.right = new BinaryTreeNode("C");
tree.root.left.left = new BinaryTreeNode("D");
tree.root.left.right = new BinaryTreeNode("E");
tree.root.left.left.left = new BinaryTreeNode("F");
tree.root.right.right = new BinaryTreeNode("G");
tree.root.right.right.left = new BinaryTreeNode("H");
tree.root.right.right.right = new BinaryTreeNode("I");
//tree.PrintPreorderIterative();
//tree.PrintInorderIterative();
tree.PostorderIterative();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class BinaryTree
{
public BinaryTreeNode root;
//생성자
public BinaryTree(string data)
{
this.root = new BinaryTreeNode(data);
}
public void PrintPreorderTraversal()
{
this.PreorderTraversal(this.root);
}
private void PreorderTraversal(BinaryTreeNode node)
{
if (node == null) return;
//출력
Console.Write("{0} ", node.data);
this.PreorderTraversal(node.left);
this.PreorderTraversal(node.right);
}
public void PrintPreorderIterative()
{
//스택을 만든다
var stack = new Stack<BinaryTreeNode>();
//루트 넣는다
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);
}
}
//중위순회
//D B E A C
public void PrintInorderIterative()
{
//스택을 만든다
var stack = new Stack<BinaryTreeNode>();
//변수에 루트를 넣는다
var node = this.root;
//최좌측 노드들을 스택에 넣는다
while (node != null)
{
stack.Push(node);
node = node.left;
}
//스택에 요소가 있다면 반복
while (stack.Count > 0)
{
//꺼낸다
var popNode = stack.Pop();
//출력
Console.Write("{0} ", popNode.data);
//오른쪽 노드 확인
var temp = popNode.right;
if (temp != null)
{
//오른쪽 노드를 포함한 최좌측 노드들을 스택에 넣기
stack.Push(temp);
temp = popNode.left;
}
}
}
public void PrintInorderIterative2()
{
//스택 만든다
var stack = new Stack<BinaryTreeNode>();
//변수에 루트 넣는다
var node = this.root;
//변수에 노드가 있거나 스택에 요소가 있다면 반복
while (node != null || stack.Count > 0)
{
//변수에 노드가 있다면 반복
while (node != null)
{
//변수의 노드를 스택에 넣는다
stack.Push(node);
//변수에 노드의 왼쪽 노드를 넣는다
node = node.left;
}
//스택에서 꺼냄
node = stack.Pop();
//출력
Console.WriteLine("{0} ", node.data);
//변수에 오른쪽 노드를 넣는다 (스택에 오른쪽에 있는 서브루트에서 최좌측까지 넣기 위함)
node = node.right;
}
}
public void PostorderIterative()
{
//스택을 만든다
var stack = new Stack<BinaryTreeNode>();
//변수에 루트를 넣는다
var node = this.root;
//왼쪽 끝까지 오른쪽 노드와 루트노드를 넣는다
while (node != null)
{
if (node.right != null)
{
stack.Push(node.right);
}
stack.Push(node);
node = node.left;
}
//스택에 요소가 있으면 반복
while (stack.Count > 0)
{
//꺼낸다
node = stack.Pop();
//꺼낸거의 오른쪽 노드와 Top에 있는 요소와 비교한다
if (node.right != null && stack.Count > 0 && node.right == stack.Peek())
{
//같다면 꺼낸다
var right = stack.Pop();
//루트를 넣는다
stack.Push(node);
node = node.right;
//마지막 왼쪽노드가 없을때까지 반복
while (node != null)
{
//우측노드 넣고 루트 넣고
if (node.right != null)
{
stack.Push(node.right);
}
stack.Push(node);
//왼쪽 노드 확인
node = node.left;
}
}
else
{
//출력한다
Console.WriteLine("{0} ", node.data);
}
}
}
}
}
BinarySearchTree
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");
BinarySearchTree tree = new BinarySearchTree();
tree.Add(10);
tree.Add(11);
tree.Add(8);
tree.Add(7);
tree.Add(13);
tree.Add(15);
tree.Add(2);
tree.Add(3);
tree.Add(1);
tree.Add(12);
var result = tree.Search(1);
Console.WriteLine(result);
}
}
}using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Study02
{
public class BinarySearchTree
{
private BSTNode root;
//생성자
public BinarySearchTree()
{
}
//추가
public void Add(int data)
{
if (root == null)
{
this.root = new BSTNode(data);
return;
}
//비교
var node = this.root;
while (node != null)
{
//추가 하려는 값과 노드의 값을 비교
var result = data.CompareTo(node.data);
if (result == 0)
{
//같다
throw new ApplicationException("duplicate!!");
}
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;
while (node != null)
{
//찾으려고 하는 데이터와 노드의 데이터 비교
var result = data.CompareTo(node.data);
//같을경우 true반환
if (result == 0)
{
//찾음
return true;
}
else if (result < 0)
{
//작을경우 node에 왼쪽 노드를 할당
node = node.left;
}
else
{
//클경우 node에 오른쪽 노드를 할당
node = node.right;
}
}
//다 확인했는데도 업다면 false를 반환(못찾음)
return false;
}
}
}
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;
}
}
}
'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주차 3일 수업 내용 : Tree (21.03.31) (0) | 2021.03.31 |
| C# 4주차 2일 수업 내용 : 자료구조 (21.03.30) (0) | 2021.03.30 |
'C#/자료구조' Related Articles
more
