C ++の1つのスタックを使用して、リーフノードを左から右にバイナリツリーで印刷します。

プログラムは、バイナリツリーのリーフノードを左から右に出力する必要がありますが、課題は1つのスタックのみを使用することです

push（）関数を使用してバイナリツリーのノードを挿入し、pop（）操作を使用してリーフノードを表示します。

リーフノードは、左右のポインタがNULLであるエンドノードです。これは、特定のノードが親ノードではないことを意味します。

例

Input : 12 21 32 41 59 33 70
Output : 41 59 33 70

スタックはLIFO構造であるデータ構造であり、トップポインターが最後に挿入された要素を指すため、リーフノードは最後にスタックに挿入され、他のノードの前にスタックからポップアウトまたは削除されます。スタック構造ごと。

以下のコードは、指定されたアルゴリズムのSTLを使用したC++の実装を示しています。

アルゴリズム

START
   Step 1 -> create node variable of type structure
      Declare int data
      Declare pointer of type node using *left, *right
   Step 2 -> create function for inserting node with parameter as val
      Declare node variable of node using malloc
      Set node->data = val
      Set node->left = node->right = NULL
      return node
   step 3 -> Declare Function void leaf(Node *ptr)
      create vector stack<Node*>stck
      Loop While 1
      IF ptr
         Stck.push(ptr)
         Ptr = ptr->left
      Else
         IF (stck.empty())
            Break
         Else
            IF (stck.top()->right == NULL)
               Set ptr = stck.top()
               Set stck.pop()
               IF ptr->left = NULL
                  Print ptr->data
            End
            Loop While ptr == stck.top()->right
               Set ptr = stck.top()
               Call stck.pop()
               IF stck.empty()
                  Break
               End
               IF !stck.empty()
                  Set ptr = tck.top()->right
               Else
                  Set ptr = NULL
               EndIF
            End
         End
      End
   Step 4-> In main()
      Call New passing value user want to insert as Node* root = New(12)
      Call leaf(root)
STOP

例

#include <bits/stdc++.h>
using namespace std;
// Structure of a node
struct Node {
   Node* left;
   Node* right;
   int data;
};
//Function to create a new node
Node* New(int val) {
   Node* node = new Node();
   node->left = node->right = NULL;
   node->data = val;
   return node;
}
// leaf node using stack
void leaf(Node* ptr) {
   // stack that will store nodes
   stack<Node*> stck;
   while (1) {
      if (ptr) {
         stck.push(ptr);
         ptr = ptr->left;
      } else {
         if (stck.empty())
            break;
         else {
            if (stck.top()->right == NULL) {
               ptr = stck.top();
               stck.pop();
               // Print the leaf node
               if (ptr->left == NULL)
                  printf("%d ", ptr->data);
            }
            while (ptr == stck.top()->right) {
               ptr = stck.top();
               stck.pop();
               if (stck.empty())
                  break;
            }
            if (!stck.empty())
               ptr = stck.top()->right;
            else
               ptr = NULL;
         }
      }
   }
}
int main() {
   printf("leaf nodes at end level are : ");
   Node* root = New(12);
   root->left = New(21);
   root->right = New(32);
   root->left->left = New(41);
   root->left->right = New(59);
   root->right->left = New(33);
   root->right->right = New(70);
   leaf(root);
   return 0;
}

出力

上記のプログラムを実行すると、次の出力が生成されます。

leaf nodes at end level are : 41 59 33 70