Trong bài toán này, chúng ta được đưa ra một cây nhị phân. Nhiệm vụ của chúng tôi là viết một chương trình để tìm chiều sâu hoặc chiều cao tối đa của cây đã cho.
Hãy lấy một ví dụ để hiểu vấn đề,
Chiều cao của cây là 3.
Để tìm chiều cao tối đa của cây, chúng tôi sẽ kiểm tra chiều cao của cây con bên trái và bên phải của nó và thêm một cây vào mức tối đa của cả hai. Đây là một quá trình đệ quy sẽ tiếp tục vì nút cuối cùng của cây được tìm thấy và một nút được thêm dần dần để tìm chiều cao của các cây con.
Ví dụ trên được giải quyết bằng phương pháp này.
Tìm chiều cao của cây tức là chiều cao (3) =max (chiều cao (5), chiều cao (7)) + 1.
Đối với điều này, chúng tôi sẽ tính toán chiều cao của các nút có giá trị 5 và 7.
height (5) =max (height (1), height (9)) + 1 và
height (7) =1, nó không có cây con nào có thể được tạo thành.
Tương tự, height (1) =height (9) =1
height (5) =max (1,1) +1 =2
height (3) =max (height (5), height (7)) + 1 =max (2.1) + 1 =3.
Vì vậy, chiều cao trở thành 3.
Chương trình minh họa giải pháp,
Ví dụ
#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;
} Đầu ra
The height of the given binary tree is 3