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

与えられた二分木の順序のない非再帰的トラバーサルを実行するC++プログラム


二分木が順番にトラバースされる場合、最初に左側のサブツリーにアクセスし、次にルートにアクセスし、次に右側のサブツリーにアクセスします。 in_orderトラバーサルで昇順でキーを出力します。これは、再帰のない順序付きツリートラバーサル用のC++プログラムです。

アルゴリズム

Begin
   Declare a structure n.
      Declare d of the integer datatype.
      Declare a pointer l against structure n.
      Declare a pointer r against structure n.
      Declare a constructor of structure n.
         Pass an integer variable d to parameter.
         this->d = d
         l = r = NULL
   Declare inOrder(struct n *root) function.
      Declare a stack s.
      Declare a pointer current against structure n.
         Initialize n *current = root.
      while (current != NULL || s.empty() == false)
         while (current != NULL)
            s.push(current)
            current = current->l
         current = s.top()
         s.pop()
         print current->d.
         current = current->r.
   insert values in nodes of tree.
   Call inOrder(root) function to travern the tree.
End.

#include<bits/stdc++.h>
using namespace std;
struct n {
   int d;
   struct n* l;
   struct n* r;
   n (int d) {
      this->d = d;
      l = r = NULL;
   }
};
void inOrder(struct n *root) {
   stack<n *> s;
   n *current = root;
   while (current != NULL || s.empty() == false) {
      while (current != NULL) {
         s.push(current);
         current = current->l;
      }
      current = s.top();
      s.pop();
      cout << current->d << " ";
      current = current->r;
   }
}
int main() {
   struct n* root = new n(6);
   root->l = new n(4);
   root->r= new n(7);
   root->l->l = new n(8);
   root->l->r= new n(5);
   root->r->l = new n(9);
   root->r->r = new n(10);
   inOrder(root);
   return 0;
}

出力

8 4 5 6 9 7 10

  1. 与えられた二分木の順序の再帰的走査を実行するC++プログラム

    ツリートラバーサルは、グラフトラバーサルの一種です。これには、ツリー内の各ノードを1回だけチェックまたは印刷することが含まれます。二分探索木の順序どおりの走査には、ツリー内の各ノードを順番に(左、根、右)訪問することが含まれます。 二分木のインオーダートラバーサルの例は次のとおりです。 二分木は次のように与えられます。 インオーダートラバーサルは次のとおりです:1 4 5 6 8 順序どおりの再帰的走査を実行するプログラムは次のとおりです。 例 #include<iostream> using namespace std; struct node {  

  2. 与えられた二分木のプレオーダー再帰トラバーサルを実行するC++プログラム

    ツリートラバーサルは、グラフトラバーサルの一種です。これには、ツリー内の各ノードを1回だけチェックまたは印刷することが含まれます。二分探索木のプレオーダートラバーサルでは、ツリー内の各ノードに順番に(ルート、左、右)アクセスします。 二分木のプレオーダートラバーサルの例は次のとおりです。 二分木は次のように与えられます。 プレオーダートラバーサルは次のとおりです:6 4 1 5 8 プレオーダー再帰トラバーサルを実行するプログラムは次のとおりです。 例 #include<iostream> using namespace std; struct node { &nb