08/17

General Tree
기존 Linear 방식의 자료구조에서 벗어난 새로운 자료구조
실행활과 컴퓨터에서 폭넓게 사용된다.
Linked List를 구현하 듯이 Node를 구현하여 사용
학술적으로, 트리구조는 계층 구조의 추상적인 형태라고 정의함
트리의 각 Node는 Parent와 Child 관계를 가지고 있음
사용 사례 : 차트정리, 파일 시스템, 프로그래밍 환경 등

General Tree Node
트리의 각 데이터는 Linked List 처럼 Node를 이용해 구현
트리의 각 Node는 Parent와 Child 관계를 가지고 있다
각 Node는 1개의 Parent와 N개의 Child를 가진다

용어 정리 General Tree Teminology
Root : Parent가 없는 노드
internal Node : 자식이 있는 노드
External Node : 자식이 없는 노드
Ancestors : 부모와 그 위에 존재하는 모든 Node
Depth : 해당 노드부터 부모 Node까지 조상의 숫자
Height : 트리 내의 최대 Depth
Descendant : 해당 Node와 그 아래의 모든 Node들
SubTree 어떤 노드의 아래의 모든 트리
Descendant와 SubTree 차이 : Descendant는 트리 구조를 포함하지 않음

Tree Basic Algorithm
Depth 구하기
해당 노드부터 부모 노드까지의 조상의 숫자를 구합니다. 자신은 제외하고 카운트합니다.

Height 구하기
모든 external 노드의 depth를 비교해 가장 큰 값이 Height가 됩니다.

바이너리 노드 트리
노드가 자식을 0개 가지고 있거나 최대 2개 가지고 있는 트리, 각 노드는 left, right, element
프로퍼 바이너리 트리 : 0개 혹은 2개만 가능한 트리

바이너리 트리 구현
Root가 있어야함
Count, IsEmpty가 있어야함
Add, Remove가 있어야함
Preorder Traversal로 출력하는 함수

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

namespace LearnAlgorithm_DataStructure
{
	public class bsNode<T> where T : IComparable
	{
		public T Data
		{
			get; set;
		}

		public bsNode<T> Parent
		{
			get; set;
		}

		public bsNode<T> Left
		{
			get; set;
		}
		public bsNode<T> Right
		{
			get; set;
		}

		public bsNode()
		{
			Data = default(T);
			Parent = Left = Right = default(bsNode<T>);
		}

		public bsNode(T data)
		{
			Data = data;
			Parent = Left = Right = default(bsNode<T>);
		}

		public bsNode(T data, bsNode<T> parent)
		{
			Data = data;
			Parent = parent;
			Left = Right = default(bsNode<T>);
		}
	}

	class MyBinaryTree<T> where T : IComparable
	{
		public bsNode<T> Root { get; private set; }
		public int Count { get; private set; }

		public MyBinaryTree()
		{
			Root = null;
			Count = 0;
		}

		public bool Add(T data)
		{
			if (Root == null)
			{
				Root = new bsNode<T>(data);
				Count++;
				return true;
			}

			return Add(data, Root);
		}

		// 재귀용
		private bool Add(T data, bsNode<T> parentNode)
		{
			if (data.CompareTo(parentNode.Data) == 0)
			{
				Console.WriteLine($"Add : 동일한 값({data})이 입력되었습니다. 동일한 값 입력은 지원하지 않습니다.");
				return false;
			}

			if (data.CompareTo(parentNode.Data) < 0)
			{
				if (parentNode.Left == default(bsNode<T>))
				{
					parentNode.Left = new bsNode<T>(data, parentNode);
					Count++;
					return true;
				}

				return Add(data, parentNode.Left);
			}
			else if (data.CompareTo(parentNode.Data) > 0)
			{
				if (parentNode.Right == default(bsNode<T>))
				{
					parentNode.Right = new bsNode<T>(data, parentNode);
					Count++;
					return true;
				}

				return Add(data, parentNode.Right);
			}

			Console.WriteLine("Add : 알 수 없는 오류입니다.");
			return false;
		}

		public bool Remove(T data)
		{
			if(Root != null)
			{
				bsNode<T> root = Root;
				bool result = Remove(data, ref root);
				Root = root;
				return result;
			}

			return true;
		}

		private bool Remove(T data, ref bsNode<T> node)
		{
			if (IsEmptyNode(node) == false && data.Equals(node.Data))
			{
				bsNode<T> parent = node.Parent; //지워질 노드의 parent 값을 저장해둠

				if (IsEmptyNode(node.Left) == false)
				{
					// Left, Right 중 Left가 있으면 Left 쪽을 끌어올림
					bsNode<T> right = node.Right; //지워질 노드의 Right 값을 저장해둠
					node = node.Left; // 왼쪽에서 위로 한칸씩 올라오며 node의 기존 값을 지움

					if ((IsEmptyNode(node.Left) == false) || (IsEmptyNode(node.Right) == false))
					{
						// 지워진 자리를 대신한 노드가 internal 노드인 경우
						if (IsEmptyNode(right) == false)
						{
							bsNode<T> LastRightOfLeft = node.Right; // 지워진 노드의 right를 연결할 left중 가장 오른쪽의 노드를 찾기

							while (IsEmptyNode(LastRightOfLeft))
							{
								LastRightOfLeft = LastRightOfLeft.Right;
							}
							LastRightOfLeft.Right = right;
							node.Right = LastRightOfLeft;
							node.Parent = parent;
						}
					}
					else
					{
						// 지워진 자리를 대신한 노드가 external 노드인 경우
						if (node.Data.CompareTo(right.Data) < 0)
						{
							node.Left = right;
							right.Parent = node;
						}
						else if (node.Data.CompareTo(right.Data) > 0)
						{
							node.Right = right;
							right.Parent = node;
						}
						else
						{
							Count--;
							Console.WriteLine("Remove : 알 수 없는 오류(동일한 값이 발견되었습니다)");
							return false;
						}
					}

					Count--;
					return true;
				}

				// Right만 있는 경우에만 Right 쪽을 끌어올림
				if (IsEmptyNode(node.Right) == false)
				{
					node = node.Right;
					node.Parent = parent;
					Count--;
					return true;
				}

				//Left도 Right도 없는 External Node인 경우, 부모와 자신의 연결을 끊음
				if (node.Parent.Left.Equals(node))
				{
					node.Parent.Left = null;
					node = null;
					return true;
				}
				
				if (node.Parent.Right.Equals(node))
				{
					node.Parent.Right = null;
					node = null;
					return true;
				}

				Console.WriteLine("Remove : 알 수 없는 오류가 발생했습니다.");
				return false;
			}

			if (IsEmptyNode(node) == false && data.CompareTo(node.Data) < 0)
			{
				bsNode<T> left = node.Left;
				bool result = Remove(data, ref left);
				node.Left = left;
				return result;
			}
			else if (IsEmptyNode(node) == false && data.CompareTo(node.Data) > 0)
			{
				bsNode<T> right = node.Right;
				bool result = Remove(data, ref right);
				node.Right = right;
				return result;
			}

			Console.WriteLine($"Remove : 입력된 값({data})을 찾을 수 없습니다.");
			return false;
		}

		private static bool IsEmptyNode(bsNode<T> node)
		{
			return node == default(bsNode<T>);
		}

		public void Print(bsNode<T> node = default, string locate = default)
		{
			if (node == default)
			{
				node = Root;
			}

			if(locate == default)
            {
				locate = "Root";
            }

			Console.Write(node.Data);
			Console.WriteLine(" : " + locate);

			if (IsEmptyNode(node.Left) == false)
            {
				Print(node.Left, locate + " L");
            }

			if (IsEmptyNode(node.Right) == false)
            {
				Print(node.Right, locate + " R");
			}
		}
	}
}