이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 주어진 나무의 최대 깊이 또는 높이를 찾는 프로그램을 작성하는 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
나무의 높이는 3입니다.
트리의 최대 높이를 찾기 위해 왼쪽 및 오른쪽 하위 트리의 높이를 확인하고 둘의 최대값에 1을 더합니다. 이것은 트리의 마지막 노드가 발견되고 하나가 하위 트리의 높이를 찾기 위해 점진적으로 추가되는 것을 계속하는 재귀 프로세스입니다.
이 방법을 사용하여 위의 예를 해결했습니다.
트리의 높이 찾기, 즉 height(3) =max(height(5),height(7)) + 1.
이를 위해 값이 5와 7인 노드의 높이를 계산합니다.
높이(5) =최대(높이(1), 높이(9)) + 1 및
height(7) =1, 구성할 수 있는 하위 트리가 없습니다.
마찬가지로 높이(1) =높이(9) =1
높이(5) =최대(1,1) +1 =2
높이(3) =최대(높이(5), 높이(7)) + 1 =최대(2,1) + 1 =3.
따라서 높이는 3이 됩니다.
솔루션을 설명하는 프로그램,
예시
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
int height(node* node) {
if (node == NULL)
return 0;
else {
int lDepth = height(node->left);
int rDepth = height(node->right);
if (lDepth > rDepth)
return(lDepth + 1);
else return(rDepth + 1);
}
}
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main() {
node *root = insertNode(4);
root->left = insertNode(5);
root->right = insertNode(0);
root->left->left = insertNode(1);
root->left->right = insertNode(9);
cout<<"The height of the given binary tree is "<<height(root);
return 0;
} 출력
The height of the given binary tree is 3