C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

バイナリツリーのすべてのリーフノードをC++で右から左に印刷します

この問題では、二分木が与えられ、二分木のすべてのリーフノードを右から左に印刷する必要があります。

問題を理解するために例を見てみましょう

入力 −

バイナリツリーのすべてのリーフノードをC++で右から左に印刷します

出力 − 7 4 1

この問題を解決するには、二分木をトラバースする必要があります。このトラバーサルは2つの方法で実行できます-

プレオーダートラバーサル −このトラバーサルは再帰を使用します。ここでは、トラバース、ルート、左、右のサブツリーを作成します。リーフノードに遭遇した場合はそれを印刷します。それ以外の場合は、ノードの子をチェックし、それらを探索してリーフノードを見つけます。

例

ソリューションの実装を示すプログラム-

#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;
}
出力 
Leaf nodes of the tree from right to left are −
18 2 98 8

ポストオーダートラバーサル −リーフノードを見つけるためのこのトラバーサルは、反復を使用します。スタックを使用してデータを格納し、ポストオーダー方式でツリーをトラバースし（最初に右のサブツリー、次に左のサブツリー、次にルート）、リーフノードを出力します。

例

ソリューションの実装を示すプログラム-

#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;
}

出力

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

  1. C++プログラミングのバイナリツリー内のすべてのノードの印刷レベル。

    二分木が与えられた場合、タスクは、1からnまでのノードに格納されているすべてのキーに関連付けられたレベルを出力することです 上記のツリーでは、ノードは- 10 at level 1 3 and 211 at level 2 140, 162, 100 and 146 at level 3 キーが与えられると、プログラムはその特定のキーのレベルを出力する必要があります。 例 Input: 10 3 211 140 162 100 146 Output:    level of 10 is 1    Level of 3 is 2   &

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

    プログラムは、バイナリツリーのリーフノードを左から右に出力する必要がありますが、課題は1つのスタックのみを使用することです push（）関数を使用してバイナリツリーのノードを挿入し、pop（）操作を使用してリーフノードを表示します。 リーフノードは、左右のポインタがNULLであるエンドノードです。これは、特定のノードが親ノードではないことを意味します。 例 Input : 12 21 32 41 59 33 70 Output : 41 59 33 70 スタックはLIFO構造であるデータ構造であり、トップポインターが最後に挿入された要素を指すため、リーフノードは最後にスタックに挿