[알고리즘] 이진트리 자료구조 정리 및 구현

 

이진 탐색트리 gif 출처 : https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node

- 트리 관련 용어 정리-

• 루트(Root) : 트리의 최상단 노드
• 간선(Edge) : 두 노드를 잇는 선
• 브랜치(Branch) : 한 노드에서 갈라져 나온 자식 노드의 수
• 형제(Sibling) : 부모가 같은 자식노드들
• 리프(Leaf) : 자식노드가 없는 하단의 노드
• 높이(Height) : 특정 노드에서 루트 사이의 길이
• 깊이(Depth) : 루트 노드에서 특정 노드까지의 길이
• 트리 높이(Tree Height) : 가장 먼 거리에 있는 Leaf 노드와 루트 사이의 길이
• 트리 깊이(Tree Depth) : 루트 노드에서 가장 먼 리프 노드까지의 길이
• 레벨(Level) : 루트 노드로부터의 깊이
• 노드의 차수(Node Degree) : 한 노드의 서브트리의 갯수(자식노드의 수)
• 트리의 차수(Tree Degree) : 트리 안 노드들의 차수 중 최대 차수

-이진트리 구현 및 순회-

 

순회에는 세가지 종류가 있는데 전위순회와 중위순회 그리고 후위순회로 총 세가지가 있다.

 

전위순회의 경우 부모노드 출력 => 왼쪽 자식 노드 방문 => 오른쪽 자식노드 방문 순으로 순회가 이루어 진다.

중위순회의 경우 왼쪽 자식노드 방문 =>  자기 자신을 방문 => 오른쪽 자식노드 방문 순으로 순회가 이루어 진다.

부모노드의 경우 왼쪽 자신노드 방문 => 오른쪽 자식노드 방문 => 자기 자신을 방문 순으로 순회가 이루어 진다.

위와 같은 이진트리가 있다고 할때 코드로 표현해보자

using System;
using static BinarySearchTree.BinarySearchTree;

namespace BinarySearchTree
{

    internal class Program
    {
        static void Main(string[] args)
        {
            Node n7 = new Node(7, null, null);
            Node n6 = new Node(6, null, null);
            Node n5 = new Node(5, null, null);
            Node n4 = new Node(4, null, null);
            Node n3 = new Node(3, n6, n7);
            Node n2 = new Node(2, n4, n5);
            Node n1 = new Node(1, n2, n3);

            Console.WriteLine(" 전위 순회\n");
            BinarySearchTree.PreOrder(n1);
            Console.WriteLine();

            Console.WriteLine(" 중위 순회\n");
            BinarySearchTree.InOrder(n1);
            Console.WriteLine();

            Console.WriteLine(" 후위 순회\n");
            BinarySearchTree.PostOrder(n1);
            Console.WriteLine();
        }
    }

    public class BinarySearchTree
    {
        public class Node
        {
            public int data;
            public Node leftChild;
            public Node rightChild;
            public Node(int data, Node left, Node Right)
            {
                this.data = data;
                this.leftChild = left;
                this.rightChild = Right;
            }
        }

        //전위순회 구현
        //자기 자신을 출력
        //왼쪽 자식 노드 방문
        //오른쪽 자식 노드 방문
        public static void PreOrder(Node root)
        {
            if (root != null)
            {
                Console.WriteLine(root.data);
                PreOrder(root.leftChild);
                PreOrder(root.rightChild);
            }
        }
        //중위 순회
        //1. 왼쪽 자식을 방문한다.
        //2. 자기 자신을 출력한다.
        //3. 오른쪽 자식을 방문한다.
        public static void InOrder(Node root)
        {
            if (root != null)
            {
                InOrder(root.leftChild);
                Console.WriteLine(root.data);
                InOrder(root.rightChild);
            }
        }

        //후위 순회
        //1. 왼쪽 자식을 방문한다.
        //2. 오른쪽 자식을 방문한다.
        //3. 자기 자신을 출력한다.
        public static void PostOrder(Node root)
        {
            if (root != null)
            {
                PostOrder(root.leftChild);
                PostOrder(root.rightChild);
                Console.WriteLine(root.data);
            }
        }

    }

결과창