Trong hướng dẫn này, chúng ta sẽ tìm nút lá bên trái sâu nhất trong cây nhị phân. Hãy xem cây nhị phân.
A B C D E F G
Hãy xem các bước để giải quyết vấn đề.
-
Viết cấu trúc Node với các con trỏ char, left và right.
-
Khởi tạo cây nhị phân với dữ liệu giả.
-
Viết hàm đệ quy để tìm nút trái sâu nhất trong hàm nhị phân. Cần ba nút gốc đối số, isLeftNode và con trỏ kết quả để lưu trữ nút sâu nhất.
-
Nếu nút hiện tại là nút bên trái và là nút lá, thì hãy cập nhật nút kết quả bằng nút hiện tại.
-
Gọi hàm đệ quy trên cây con bên trái.
-
Gọi hàm đệ quy trên cây con bên phải.
-
Nếu nút kết quả là null, thì không có nút nào đáp ứng các điều kiện của chúng tôi.
-
Nếu không, hãy in dữ liệu trong nút kết quả.
Ví dụ
Hãy xem mã.
#include <bits/stdc++.h>
using namespace std;
struct Node {
char data;
struct Node *left, *right;
};
Node *addNewNode(char data) {
Node *newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
void getDeepestLeftLeafNode(Node *root, bool isLeftNode, Node **resultPointer) {
if (root == NULL) {
return;
}
if (isLeftNode && !root->left && !root->right) {
*resultPointer = root;
return;
}
getDeepestLeftLeafNode(root->left, true, resultPointer);
getDeepestLeftLeafNode(root->right, false, resultPointer);
}
int main() {
Node* root = addNewNode('A');
root->left = addNewNode('B');
root->right = addNewNode('C');
root->left->left = addNewNode('D');
root->right->left = addNewNode('E');
root->right->right = addNewNode('F');
root->right->left->right = addNewNode('G');
Node *result = NULL;
getDeepestLeftLeafNode(root, false, &result);
if (result) {
cout << "The deepest left child is " << result->data << endl;
}
else {
cout << "There is no left leaf in the given tree" << endl;
}
return 0;
} Đầu ra
Nếu bạn thực hiện chương trình trên, bạn sẽ nhận được kết quả sau.
The deepest left child is D
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.