ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือการเขียนโปรแกรมเพื่อค้นหาความลึกหรือความสูงสูงสุดของต้นไม้ที่กำหนด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ความสูงของต้นไม้คือ 3.
ในการหาความสูงสูงสุดของต้นไม้ เราจะตรวจสอบความสูงของต้นไม้ย่อยด้านซ้ายและขวาของต้นไม้ และเพิ่มหนึ่งเข้าไปที่ค่าสูงสุดของทั้งสอง นี่เป็นกระบวนการแบบเรียกซ้ำซึ่งจะดำเนินต่อไปโดยพบโหนดสุดท้ายในทรี และจะมีการเพิ่มโหนดหนึ่งๆ ไปเรื่อย ๆ เพื่อค้นหาความสูงของทรีย่อย
ตัวอย่างข้างต้นแก้ไขโดยใช้วิธีนี้
การหาความสูงของต้นไม้ เช่น height(3) =max(height(5),height(7)) + 1
สำหรับสิ่งนี้ เราจะคำนวณความสูงของโหนดด้วยค่า 5 และ 7
height(5) =max(height(1),height(9)) + 1 and
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
