이진트리(Binary Tree)

이진트리

이진트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조이다

노드의 자식중 왼쪽에 있는 것을 왼쪽 자식 노드,

오른쪽에 있는 것을 오른쪽 자식 노드라고 한다

각 노드는 자식을 가지지 않을 수 있다

출처: 위키백과 이진트리

아래는 위 이미지에 맞게 이진트리를 구현하는 코드이다

using System;
using System.Collections.Generic;
using System.Text;

namespace BinaryTree
{  
    class Tree
    {
        public int data;
        public Tree left;
        public Tree right;

        //생성자
        public Tree(int data)
        {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Text;

namespace BinaryTree
{
    class App
    {
        Tree tree;
        
        public App()
        {
            tree = new Tree(2);
            tree.left = new Tree(7);
            tree.right = new Tree(5);
            tree.left.left = new Tree(2);
            tree.left.right = new Tree(6);
            tree.right.right = new Tree(9);
            tree.left.right.left = new Tree(5);
            tree.left.right.right = new Tree(11);
            tree.right.right.left = new Tree(4);               
        }        
    }  
}

---

이진트리 순회

이진트리 순회 방법 중 전위, 중위, 후위 순회가 있다

 

전위순회(Preorder): 현재노드-왼쪽 자식노드-오른쪽 자식노드 순으로 순회한다

중위순회(Inorder):왼쪽 자식 노드-현재 노드-오른쪽 자식 노드 순으로 순회한다

후위순회(Postorder): 왼쪽 자식 노드- 오른쪽 자식 노드-현재 노드 순으로 순회한다

 

아래는 이진트리를 순회하는 세 가지 방법을 구현한 코드이다

        //전위
        public void Preorder(Tree tree)
        {
            if (tree != null)
            {
                Console.Write("{0} ",tree.data);
                Preorder(tree.left);
                Preorder(tree.right);
            }
        }
        //중위
        public void Inorder(Tree tree)
        {
            if (tree != null)
            {
                Inorder(tree.left);
                Console.Write("{0} ", tree.data);
                Inorder(tree.right);
            }
        }
        //후위
        public void Postorder(Tree tree)
        {
            if(tree != null)
            {
                Postorder(tree.left);
                Postorder(tree.right);
                Console.Write("{0} ", tree.data);
            }          
        }

위에서 구현한 트리를 순회한 결과