Tìm nút sâu nhất trong cây nhị phân trong C ++

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à tìm nút sâu nhất trong cây nhị phân .

Cây nhị phân là một cấu trúc dữ liệu đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu. Cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con.

Nút sâu nhất trong cây nhị phân là nút ở độ cao tối đa có thể có trong cây.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào:

Đầu ra:8

Phương pháp tiếp cận giải pháp

Có thể có nhiều cách để giải quyết vấn đề này, vì bạn cần phải tìm chiều cao và đi qua cây đến nút cuối cùng ở độ cao và trả lại nó. Tất cả các giải pháp sẽ chỉ nằm trên nguyên tắc này. Ở đây, chúng tôi đã thảo luận về một số giải pháp đầy hứa hẹn và được tối ưu hóa.

Một giải pháp đơn giản cho vấn đề là sử dụng trình duyệt inorder của cây và duy trì một dấu mức, nếu mức hiện tại lớn hơn maxLevel. Chúng tôi sẽ khởi tạo nút dưới dạng DeepNode. Sau khi tất cả các nút của cây được duyệt qua, chúng ta sẽ trả về Nút sâu nhất. Đối với đường truyền của cây, chúng ta sẽ sử dụng đệ quy.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#include <iostream>
using namespace std;
struct Node{
   int data;
   struct Node *left, *right;
};
Node *newNode(int data){
   Node *temp = new Node;
   temp->data = data; 
   temp->left = temp->right = NULL;
   return temp;
}
void findDeepestNodeRec(Node *root, int currentLevel, int &maxLevel, int &deepestNode){
   if (root != NULL){
      findDeepestNodeRec(root->left, ++currentLevel, maxLevel, deepestNode);
      if (currentLevel > maxLevel){
         deepestNode = root->data;
         maxLevel = currentLevel;
      }
      findDeepestNodeRec(root->right, currentLevel, maxLevel, deepestNode);
   }
}
int findDeepestNodeBT(Node *root){
   int deepestNode = 0;
   int maxLevel = 0;
   findDeepestNodeRec(root, 0, maxLevel, deepestNode);
   return deepestNode;
}
int main(){
   Node* root = newNode(3);
   root->left = newNode(5);
   root->right = newNode(4);
   root->left->left = newNode(1);
   root->left->right = newNode(9);
   root->right->left = newNode(6);
   root->right->left->right = newNode(8);
   cout<<"The deepest node of the given binary tree is "<<findDeepestNodeBT(root);
   return 0;
}

Đầu ra

The deepest node of the given binary tree is 8

Một cách tiếp cận khác để giải quyết vấn đề là bằng cách tìm chiều cao của cây đã cho. Và sau đó trả về nút ở mức bằng chiều cao của cây.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#include <bits/stdc++.h>
using namespace std;
struct Node{
   int data; struct Node *left, *right;
};
Node *newNode(int data){
   Node *temp = new Node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
int calcHeight(Node* root){
   if(!root) return 0;
   int leftHt = calcHeight(root->left) + 1;
   int rightHt = calcHeight(root->right) + 1;
   return max(leftHt, rightHt);
}
void findDeepestNodeBT(Node* root, int levels){
   if(!root) return;
   if(levels == 1)
   cout << root->data;
   else if(levels > 1){
      findDeepestNodeBT(root->left, levels - 1);
      findDeepestNodeBT(root->right, levels - 1);
   }
}
int main(){
   Node* root = newNode(3);
   root->left = newNode(5);
   root->right = newNode(4);
   root->left->left = newNode(1);
   root->left->right = newNode(9);
   root->right->left = newNode(6);
   root->right->left->right = newNode(8);
   int maxHeight = calcHeight(root);
   cout<<"The deepest node of the binary tree is "; 
   findDeepestNodeBT(root, maxHeight);
   return 0;
}

Đầu ra

The deepest node of the binary tree is 8