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

ツリートラバーサルは、グラフトラバーサルの一種です。これには、ツリー内の各ノードを1回だけチェックまたは印刷することが含まれます。二分探索木のプレオーダートラバーサルでは、ツリー内の各ノードに順番に（ルート、左、右）アクセスします。

二分木のプレオーダートラバーサルの例は次のとおりです。

二分木は次のように与えられます。

プレオーダートラバーサルは次のとおりです：5 3 2 4 8 9

事前注文の非再帰的トラバーサルを実行するプログラムは次のとおりです。

例

#include<iostream>
#include <stack>
using namespace std;
struct node {
   int data;
   struct node *left;
   struct node *right;
};
struct node *createNode(int val) {
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp→data = val;
   temp→left = temp→right = NULL;
   return temp;
}
void preorder(struct node *root) {
   if (root == NULL)
   return;
   stack<node *> nodeStack;
   nodeStack.push(root);
   while (nodeStack.empty() == false) {
      struct node *temp_node = nodeStack.top();
      cout<< temp_node->data <<" ";
      nodeStack.pop();
      if (temp_node→right)
      nodeStack.push(temp_node->right);
      if (temp_node→left)
      nodeStack.push(temp_node->left);
   }
}
struct node* insertNode(struct node* node, int val) {
   if (node == NULL) return createNode(val);
   if (val < node→data)
   node→left = insertNode(node→left, val);
   else if (val > node→data)
   node→right = insertNode(node→right, val);
   return node;
}
int main() {
   struct node *root = NULL;
   root = insertNode(root, 5);
   insertNode(root, 8);
   insertNode(root, 3);
   insertNode(root, 2);
   insertNode(root, 6);
   insertNode(root, 9);
   insertNode(root, 4);
   cout<<"Pre-Order traversal of the Binary Search Tree is: ";
   preorder(root);
}

出力

Pre-Order traversal of the Binary Search Tree is: 5 3 2 4 8 6 9

上記のプログラムでは、構造ノードがツリーのノードを作成します。この構造体は、構造体ノードタイプのポインターを含むため、自己参照構造体です。この構造を以下に示します。

struct node {
   int data;
   struct node *left;
   struct node *right;
};

関数createNode（）は、ノードtempを作成し、mallocを使用してそれにメモリを割り当てます。データ値valはtempのデータに格納されます。 NULLは、tempの左右のポインタに格納されます。これは、次のコードスニペットによって示されます。

struct node *createNode(int val) {
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp→data = val;
   temp→left = temp→right = NULL;
   return temp;
}

関数preorder（）は、スタックを使用してツリーの要素をpreorderで出力します。まず、ルートノードがスタックに挿入されます。スタックが空でなくなるまで実行されるwhileループが開始されます。最初にスタックのトップノード要素のデータが表示され、次にノードがポップされます。次に、上記のノードの左右のノードがスタックにプッシュされます。

この関数は、次のコードスニペットを使用して示されています。

void preorder(struct node *root) {
   if (root == NULL)
   return;
   stack<node *> nodeStack;
   nodeStack.push(root);
   while (nodeStack.empty() == false) {
      struct node *temp_node = nodeStack.top();
      cout<< temp_node->data <<" ";
      nodeStack.pop();
      if (temp_node→right)
      nodeStack.push(temp_node→right);
      if (temp_node→left)
      nodeStack.push(temp_node→left);
   }
}

関数insertNode（）は、必要な値をバイナリツリーの正しい位置に挿入します。ノードがNULLの場合、createNodeが呼び出されます。それ以外の場合、ノードの正しい位置はツリー内にあります。これは、次のコードスニペットで確認できます。

struct node* insertNode(struct node* node, int val) {
   if (node == NULL) return createNode(val);
   if (val < node→data)
   node→left = insertNode(node→left, val);
   else if (val > node→data)
   node->right = insertNode(node→right, val);
   return node;
}

main（）関数では、ルートノードは最初にNULLとして定義されます。次に、必要な値を持つすべてのノードが二分探索木に挿入されます。これを以下に示します。

struct node *root = NULL;
root = insertNode(root, 5);
insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 2);
insertNode(root, 6);
insertNode(root, 9);
insertNode(root, 4);

最後に、ツリーのルートノードを使用して関数preorder（）が呼び出され、すべてのツリー値がpreorderで表示されます。これを以下に示します。

cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);