In tất cả các nút lá của cây nhị phân từ phải sang trái trong C ++

Trong bài toán này, chúng ta được đưa ra một cây nhị phân và chúng ta phải in tất cả các nút lá của cây nhị phân từ phải sang trái.

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

Đầu vào -

Đầu ra - 7 4 1

Để giải quyết vấn đề này, chúng ta sẽ phải duyệt cây nhị phân. Việc truyền tải này có thể được thực hiện theo hai cách -

Đặt hàng trước truyền tải - Truyền tải này sử dụng đệ quy. Ở đây, chúng ta sẽ đi ngang, root rồi đến cây con bên trái và bên phải. Nếu chúng ta gặp một nút lá thì chúng ta sẽ in nó, nếu không, chúng ta kiểm tra các nút con của nút và khám phá chúng để tìm nút lá.

Ví dụ

Chương trình thể hiện việc triển khai giải pháp của chúng tôi -

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
Node* insertNode(int data) {
   Node* temp = new Node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
void findLeafNode(Node* root) {
   if (!root)
      return;
   if (!root->left && !root->right) {
      cout<<root->data<<"\t";
      return;
   }
   if (root->right)
      findLeafNode(root->right);
   if (root->left)
      findLeafNode(root->left);
}
int main() {
   Node* root = insertNode(21);
   root->left = insertNode(5);
   root->right = insertNode(11);
   root->left->left = insertNode(8);
   root->left->right = insertNode(98);
   root->right->left = insertNode(2);
   root->right->right = insertNode(8);
   cout<<"Leaf nodes of the tree from right to left are:\n";
   findLeafNode(root);
   return 0;
}

Đầu ra

Leaf nodes of the tree from right to left are −
18 2 98 8

Truyền tải đơn hàng sau - Việc truy tìm nút lá này sẽ sử dụng phép lặp. Chúng tôi sẽ sử dụng một ngăn xếp để lưu trữ dữ liệu và duyệt cây theo cách sắp xếp thứ tự (đầu tiên là cây con bên phải sau đó đến cây con bên trái và sau đó là gốc) và in các nút lá.

Ví dụ

Chương trình thể hiện việc triển khai giải pháp của chúng tôi -

#include<bits/stdc++.h>
using namespace std;
struct Node {
   Node* left;
   Node* right;
   int data;
};
Node* insertNode(int key) {
   Node* node = new Node();
   node->left = node->right = NULL;
   node->data = key;
   return node;
}
void findLeafNode(Node* tree) {
   stack<Node*> treeStack;
   while (1) {
      if (tree) {
         treeStack.push(tree);
         tree = tree->right;
      } else {
         if (treeStack.empty())
            break;
         else {
            if (treeStack.top()->left == NULL) {
               tree = treeStack.top();
               treeStack.pop();
               if (tree->right == NULL)
                  cout<<tree->data<<"\t";
            }
            while (tree == treeStack.top()->left) {
               tree = treeStack.top();
               treeStack.pop();
               if (treeStack.empty())
                  break;
            }
            if (!treeStack.empty())
               tree = treeStack.top()->left;
            else
               tree = NULL;
         }  
      }
   }
}
int main(){
   Node* root = insertNode(21);
   root->left = insertNode(5);
   root->right = insertNode(11);
   root->left->left = insertNode(8);
   root->left->right = insertNode(98);
   root->right->left = insertNode(2);
   root->right->right = insertNode(18);
   cout<<"Leaf nodes of the tree from right to left are:\n";
   findLeafNode(root);
   return 0;
}

Đầu ra

Leaf nodes of the tree from right to left are −
18 2 98 8