C# 자료구조 (이진 트리 순회2) 코드 구현
전 페이지에서 알아본 전위 중위 후위 순회를 구현하는 방법은 대표적으로 2가지가 있다.
하나는 재귀함수로 구현을 하는것이고 두번째는 비재귀반복 while문으로 구현을 하는 방법이다.
이진 트리 순회는 재귀함수로 구현하는것이 비교적으로 쉽게 구현이 가능하다.
일단은 재귀함수로 구현을 해보겠다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TreeTraversal
{
class BinaryTreeNode<T>
{
public T Data { get; set; }
public BinaryTreeNode<T> Left { get; set;}
public BinaryTreeNode<T> Right { get; set; }
public BinaryTreeNode(T data)
{
this.Data = data;
}
}
class BinaryTree<T>
{
public BinaryTreeNode<T> Root { get; private set; }
public BinaryTree(T root)
{
Root = new BinaryTreeNode<T>(root);
}
// 트리 데이터 출력 예
public void PreorderTraversal()
{
PreorderTraversal(Root);
}
//전위 순회
private void PreorderTraversal(BinaryTreeNode<T> node)
{
if (node == null)
return;
Console.WriteLine("{0}", node.Data);
PreorderTraversal(node.Left);
PreorderTraversal(node.Right);
}
public void InorderTraversal()
{
InorderTraversal(Root);
}
//중위 순회
private void InorderTraversal(BinaryTreeNode<T> node)
{
if (node == null)
return;
InorderTraversal(node.Left);
Console.WriteLine("{0}", node.Data);
InorderTraversal(node.Right);
}
public void PostorderTraversal()
{
PostorderTraversal(Root);
}
//후위 순회
private void PostorderTraversal(BinaryTreeNode<T> node)
{
if (node == null)
return;
PostorderTraversal(node.Left);
PostorderTraversal(node.Right);
Console.WriteLine("{0}", node.Data);
}
}
class Program
{
static void Main(string[] args)
{
BinaryTree<string> binaryTree = new BinaryTree<string>("A");
binaryTree.Root.Left = new BinaryTreeNode<string>("B");
binaryTree.Root.Right = new BinaryTreeNode<string>("C");
binaryTree.Root.Left.Left = new BinaryTreeNode<string>("D");
binaryTree.Root.Left.Right = new BinaryTreeNode<string>("E");
binaryTree.Root.Right.Left = new BinaryTreeNode<string>("F");
binaryTree.Root.Left.Right.Left = new BinaryTreeNode<string>("G");
binaryTree.Root.Left.Right.Right = new BinaryTreeNode<string>("H");
binaryTree.PostorderTraversal();
}
}
}
PreorderTraversal 전위 순회
메서드를 호출을 하면 오버로딩을 통한 최상위 노드를 넣어서 최상위 노드를 출력
그다음엔 왼쪽 자식 노드로 접근 계속 그렇게 해서 출력을 하다가 왼쪽 자식에 노드가 없으면 리턴 그다음에 오른쪽 자식노드를 출력 이런식으로 재귀함수를 반복해서 호출한다.
InordeTraversal 중위 순회
처음엔 왼쪽 자식 노드로 접근 왼쪽 자식 노드가 없으면 자기 자신 노드를 출력한 다음에 오른쪽 노드로 접근 이런식으로 재귀함수를 반복해서 호출
PostorderTraversal 후위 순회
처음엔 똑같이 왼쪽 자식 노드로 접근 왼쪽 자식이 없으면 오른쪽 자식 노드에 접근 없으면 자기 자신 노드 출력 이런식으로 재귀함수를 반복해서 호출
이런식으로 재귀함수는 비교적 쉽게 구현이 가능하다.
이번엔 비재귀반복은 while문을 통해서 구현을 하는것이다.
비재귀반복은 보통 Stack 자료구조로 구현한다.
코드로 구현해보겠다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TreeTravesalStack
{
class BinaryTreeNode<T>
{
public T Data { get; set; }
public BinaryTreeNode<T> Left { get; set; }
public BinaryTreeNode<T> Right { get; set; }
public BinaryTreeNode(T data)
{
this.Data = data;
}
}
class BinaryTree<T>
{
public BinaryTreeNode<T> Root { get; private set; }
public BinaryTree(T root)
{
Root = new BinaryTreeNode<T>(root);
}
// 전위 순회
public void PreorderTraversal()
{
if (Root == null)
return;
Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
stack.Push(Root);
while (stack.Count != 0)
{
BinaryTreeNode<T> node = stack.Pop();
Console.WriteLine(node);
if (node.Right != null)
{
stack.Push(node.Right);
}
if (node.Left != null)
{
stack.Push(node.Left);
}
}
}
//중위 순회
public void InorderTraversal()
{
if (Root == null)
return;
Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
var node = Root;
while (node != null || stack.Count != 0)
{
while (node != null)
{
stack.Push(node);
node = node.Left;
}
node = stack.Pop();
Console.WriteLine(node.Data);
node = node.Right;
}
}
//후위 순회
public void PostorderTraversal()
{
var stack = new Stack<BinaryTreeNode<T>>();
var node = Root;
while (node != null || stack.Count > 0)
{
while (node != null)
{
if (node.Right != null)
{
stack.Push(node.Right);
}
stack.Push(node);
node = node.Left;
}
node = stack.Pop();
if (node.Right != null && stack.Count > 0 && node.Right == stack.Peek())
{
var right = stack.Pop();
stack.Push(node);
node = right;
}
else
{
Console.WriteLine(node.Data);
node = null;
}
}
}
}
class Program
{
static void Main(string[] args)
{
BinaryTree<string> binaryTree = new BinaryTree<string>("A");
binaryTree.Root.Left = new BinaryTreeNode<string>("B");
binaryTree.Root.Right = new BinaryTreeNode<string>("C");
binaryTree.Root.Left.Left = new BinaryTreeNode<string>("D");
binaryTree.Root.Left.Right = new BinaryTreeNode<string>("E");
binaryTree.Root.Right.Left = new BinaryTreeNode<string>("F");
binaryTree.Root.Left.Right.Left = new BinaryTreeNode<string>("G");
binaryTree.Root.Left.Right.Right = new BinaryTreeNode<string>("H");
binaryTree.Postorderlterative();
}
}
}
스택으로 이용한 전위 중위 후위 순회는 좀 복잡하다.
전위 순회는 비교적 쉽게 구현이 가능하다.
PreorderTraversal 전위 순회
처음엔 최상위 부모 노드를 스택에다 넣고 stack에 요소가 없어질때 까지 While문 호출
처음엔 자기 노드를 출력하고 오른쪽 왼쪽 노드를 널인지 체크한 다음에 스택에다 넣는다.
이러면 왼쪽을 마지막에 넣었으니 먼저 출력을 할것이도 그 자식노드들은 넣을거니깐 오른쪽 서브트리는
마지막에 접근하게 된다.
InorderTraversal 중위 순회
중위 순회도 이해를 하면 전위 순회랑 비슷한 구현 난이도다.
중위 순회는 왼쪽 서브트리를 먼저 출력해야 하니깐 while문을 통해서 왼쪽 서브트리 끝까지 접근
그다음에 스택에 넣고 그다음에 노드 오른쪽 자식노드가 있는지 체크 있으면 오른쪽 자식노드에 왼쪽 서브트리가
존재 하는지 체크 이런식으로 스택에다 저장한후 출력을 한다.
PostorderTraversal 후위 순회
후위 순회는 이해를 해도 구현하기가 좀 복잡하다.
후위 순회 순서는 왼쪽 오른쪽 노드인데 일단 while문을 통해 노드가 널인지 또는 스택 요소가 0이 아닌지 체크
노드 오른쪽 자식 노드가 널이 아니면 스택에다 저장 그다음에 자기 노드를 스택에다 정하고 오른쪽 노드로 접근
자기 노드가 널이거나 오른쪽 노드가 널이면 while문에서 빠져나오고 가장 왼쪽 서브트리에 있는 노드를 빼온다.
만약에 오른쪽 노드가 존재하거나 스택에 가장 최근에 넣은 요소가 자기 오른쪽 자식 노드가 같으면 자신 노드를
다시 스택에다 넣고 오른쪽 자식 노드로 접근
아니면 현재 노드를 출력
비재귀반복 구현은 스택 자료구조를 아직 배우지 않거나 이해하지 못했다면 좀 어려운 구현인거 같다.
나도 스택 자료구조를 배웠지만 중위 후위 순회는 다시 복습을 해야할거 같다.