웹사이트 검색

트리 데이터 구조의 높이


이 자습서에서는 이진 트리에 대해 설명합니다. 우리는 재귀적으로 뿐만 아니라 반복적으로 트리 데이터 구조의 높이를 계산하는 방법을 볼 것입니다.

이진 트리

  • 재귀 방식
  • 반복적인 방식

트리 높이 - 재귀적으로

재귀는 하위 문제의 결과를 계산하고 상위 문제로 다시 반환하는 것을 포함합니다.

관련 단계:

  1. 트리의 높이를 재귀적으로 계산하려면 왼쪽 하위 트리와 오른쪽 하위 트리의 높이를 재귀적으로 찾아 1을 더해야 합니다(최상위 노드와 자식 사이의 높이).
  2. 이러한 각 하위 트리는 왼쪽 및 오른쪽 하위 트리를 가질 수 있으므로 하위 트리가 NULL이 될 때까지 재귀가 적용됩니다. 널 트리 노드의 높이는 -1입니다.
  3. 마지막으로 왼쪽 및 오른쪽 하위 트리의 높이를 비교하고 더 큰 것을 반환합니다.

package com.journaldev.tree.height;

public class BinaryTree {

	TreeNode root;

	public static class TreeNode {

		TreeNode left;
		TreeNode right;
		Object data;

		TreeNode(Object data) {
			this.data = data;
			left = right = null;
		}
	}
}

재귀를 사용하여 트리의 높이를 찾는 코드를 살펴보겠습니다.

package com.journaldev.tree.height;

import com.journaldev.tree.height.BinaryTree.TreeNode;

public class HeightOfTree {

	public static void main(String[] args) {

		BinaryTree binaryTree = new BinaryTree();

		/**
		 * Binary Tree in our example, height = 2
		 * 		1		(Root)
		 * 	  2	  3		(Level 1)
		 *  4    	 5		(Level 2)
		 */
		binaryTree.root = new TreeNode(1);
		binaryTree.root.left = new TreeNode(2);
		binaryTree.root.right = new TreeNode(3);
		binaryTree.root.left.left = new TreeNode(4);
		binaryTree.root.right.left = new TreeNode(5);

		int heightOfTree = height(binaryTree.root);
		System.out.printf("Height of tree is %d", heightOfTree);
	}
	
	public static int height(TreeNode root) {

		if (root == null)
			return -1;

		int leftHeight = height(root.left);
		int rightHeight = height(root.right);

		return Math.max(leftHeight, rightHeight) + 1;
	}
}

따라서 위의 코드에서 맨 아래 자식 노드에 도달하면 트리 높이에 1을 추가하고 그 결과를 이전 호출에 반환합니다. 출력: 트리의 높이는 2입니다. 이제 동일한 작업을 비재귀적으로 수행해 보겠습니다.

트리 높이 - 반복적으로

트리의 높이를 반복적으로 계산하려면 트리의 레벨 수를 계산하기만 하면 됩니다.

관련 단계

  1. 대기열을 만들고 여기에 트리의 루트를 추가합니다.
  2. 대기열에서 노드를 팝하고 하위 노드를 대기열에 추가하는 동안 대기열을 탐색합니다.
  3. 각 반복에서 최신 요소가 대기열에 추가되고 이 요소의 다음 수준 요소가 대기열에 추가됩니다.
  4. 대기열 크기가 0이 될 때까지 이 작업을 수행합니다. 이는 다음 레벨에 요소가 없음을 의미합니다.
  5. 이동한 모든 레벨에 대해 1을 추가합니다.

다음은 나무의 높이를 계산하는 반복 프로그램입니다.

public static int heightIteratively(TreeNode root) {

    if (root == null)
        return -1;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int height = -1;

    while (!queue.isEmpty()) {
        int size = queue.size();

        height++;

        while (size > 0) {
            TreeNode treeNode = queue.remove();

            if (treeNode.left != null)
                queue.add(treeNode.left);

            if (treeNode.right != null)
                queue.add(treeNode.right);
            
            size--;
        }
    }
    return height;
}

시간 복잡도는 O(n)입니다. 공간 복잡도는 O(1)입니다.

GitHub 리포지토리에서 전체 코드와 더 많은 DS 및 알고리즘 예제를 체크아웃할 수 있습니다.