与えられた二分木のプレオーダー再帰トラバーサルを実行するC++プログラム
ツリートラバーサルは、グラフトラバーサルの一種です。これには、ツリー内の各ノードを1回だけチェックまたは印刷することが含まれます。二分探索木のプレオーダートラバーサルでは、ツリー内の各ノードに順番に(ルート、左、右)アクセスします。
二分木のプレオーダートラバーサルの例は次のとおりです。
二分木は次のように与えられます。
プレオーダートラバーサルは次のとおりです:6 4 1 5 8
プレオーダー再帰トラバーサルを実行するプログラムは次のとおりです。
例
#include<iostream> 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) { cout<<root->data<<" "; preorder(root->left); preorder(root->right); } } 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, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3); cout<<"Pre-Order traversal of the Binary Search Tree is: "; preorder(root); return 0; }
出力
Pre-Order traversal of the Binary Search Tree is: 4 2 1 3 5 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で出力します。これは再帰関数です。次のコードを使用して示されています。
void preorder(struct node *root) { if (root != NULL) { cout<<root-->data<<" "; preorder(root-->left); preorder(root-->right); } }
関数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, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3);
最後に、ツリーのルートノードを使用して関数preorder()が呼び出され、すべてのツリー値がpreorderで表示されます。これを以下に示します。
cout<<"Pre-Order traversal of the Binary Search Tree is: "; preorder(root);
-
与えられた二分木のポストオーダー再帰トラバーサルを実行するC++プログラム
ツリートラバーサルは、グラフトラバーサルの一種です。これには、ツリー内の各ノードを1回だけチェックまたは印刷することが含まれます。二分探索木のポストオーダートラバーサルでは、ツリー内の各ノードに順番に(左、右、ルート)アクセスします。 二分木のポストオーダートラバーサルの例は次のとおりです。 二分木は次のように与えられます。 注文後のトラバーサルは次のとおりです:1 5 4 8 6 注文後の再帰的走査を実行するプログラムは次のとおりです。 例 #include<iostream> using namespace std; struct node { &
-
与えられた二分木の順序の再帰的走査を実行するC++プログラム
ツリートラバーサルは、グラフトラバーサルの一種です。これには、ツリー内の各ノードを1回だけチェックまたは印刷することが含まれます。二分探索木の順序どおりの走査には、ツリー内の各ノードを順番に(左、根、右)訪問することが含まれます。 二分木のインオーダートラバーサルの例は次のとおりです。 二分木は次のように与えられます。 インオーダートラバーサルは次のとおりです:1 4 5 6 8 順序どおりの再帰的走査を実行するプログラムは次のとおりです。 例 #include<iostream> using namespace std; struct node {