비선형 데이터구조, 트리(Tree) #5 이진 트리의 삽입(Insert)

1. 개요

이진 트리의 삽입 기능을 구현합니다. 삽입 시 빈 공간에 삽입을 수행하는데 이 순서는 중위 순회(Inorder Traversal)를 따릅니다. 구현 언어는 자바입니다.

 

2. 중위 순회(Inorder Traversal)이란 무엇인가?

중위 순회란 왼쪽 서브 트리를 방문 후 루트 노드(Root Node)를 방문하고 마지막으로 오른쪽 서브 트리를 방문하는 순회입니다.

 

 

 

2. 이진 트리 삽입 과정

 

 

3. 이진 트리 삽입 구현

import java.util.LinkedList;
import java.util.Queue;

// 이진 트리 삽입 및 삭제 예제

public class BinaryTree
{
    public static class Node
    {
        int key;
        Node left, right;
     
        public Node(int key)
        {
            this.key = key;
            left = right = null;
        }
    }
    
    Node root;
    Node temp = root;
    
    // 비어있는 트리
    public BinaryTree()
    {
        root = null;
    }
    
    // 생성자
    public BinaryTree(int key)
    {
        root = new Node(key);
    }
    
    // 이진 트리의 중위 순회
    private void inorder(Node node)
    {
    	if(node==null)
    	{
    		return;
    	}
    	
    	inorder(node.left);
    	System.out.print(node.key+" ");
    	inorder(node.right);
    }
    
    // 이진 트리 중복순회 호출
    public void inorderTraversal()
    {
    	inorder(this.root);
    	System.out.println();
    }
    
    // 이진 트리에 key값을 노드로 생성하여 삽입
    public void insert(int key)
    {
    	if(root==null) 
    	{
    		root = new Node(key);
    		return;
    	}
    	
    	Queue<Node> q = new LinkedList<Node>();
    	q.add(root);
    	
    	// 이진트리의 빈공간을 찾을때까지 level order 순회 수행
    	while(!q.isEmpty()) {
    		temp = q.remove();
    		
    		
    		if(temp.left==null)
    		{
    			temp.left = new Node(key);
    			break;
    		}
    		else
    		{
    			q.add(temp.left);
    		}
    		
    		if(temp.right==null)
    		{
    			temp.right = new Node(key);
    			break;
    		}
    		else
    		{
    			q.add(temp.right);
    		}
    	}
    	
    }

}

import org.junit.jupiter.api.Test;
import Tree.BT.Implement.BinaryTree.Node;

class BinaryTreeTest {	
	@Test
	void insertTest() {
		BinaryTree bt = new BinaryTree();
		
		bt.insert(10);
		bt.insert(11);
		bt.insert(7);
		bt.insert(9);
		bt.insert(15);
		bt.insert(8);
		
		System.out.print("삽입이전 중위 순회 : ");
		bt.inorderTraversal();	// Expected Output : 9 11 15 10 8 7
		
		int key = 12;
		bt.insert(key);
		
		System.out.print("삽입이후 중위 순회 : ");
		bt.inorderTraversal();	// Expected Output : 9 11 15 10 8 7 12
	}

}

Output
삽입이전 중위 순회 : 9 11 15 10 8 7 
삽입이후 중위 순회 : 9 11 15 10 8 7 12

 

References

source code : https://github.com/yonghwankim-dev/DataStruct
https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/