algorithm
バイナリツリーのトラバーサル
サーチ…
前書き
ある特定の順序でバイナリツリーのノードを訪れることをトラバーサルと呼びます。
バイナリツリーのプリオーダー、インオーダー、ポストオーダートラバーサル
バイナリツリーを考えてみましょう:
先行トラバーサル(ルート)は、ノードを横断してからノードのサブツリーを左へ移動し、次にノードの右のサブツリーを左に移動します。
したがって、上の木の先行走査は次のようになります:
1 2 4 5 3 6 7
順序通りのトラバース(ルート)は、ノードの左のサブツリーを横切り、次にノードの右のサブツリーを横切っている。
したがって、上のツリーの順序通りのトラバーサルは次のようになります。
4 2 5 1 6 3 7
ポストオーダーのトラバーサル(ルート)は、ノードの左のサブツリーをたどり、次に右のサブツリー、次にノードをトラバースします。
したがって、上記ツリーのポストオーダートラバーサルは次のようになります。
4 5 2 6 7 3 1
レベルオーダートラバーサル - 実装
たとえば、指定されたツリーが:
レベルオーダーのトラバーサルは
1 2 3 4 5 6 7
ノードデータをレベル単位で印刷します。
コード:
#include<iostream>
#include<queue>
#include<malloc.h>
using namespace std;
struct node{
int data;
node *left;
node *right;
};
void levelOrder(struct node *root){
if(root == NULL) return;
queue<node *> Q;
Q.push(root);
while(!Q.empty()){
struct node* curr = Q.front();
cout<< curr->data <<" ";
if(curr->left != NULL) Q.push(curr-> left);
if(curr->right != NULL) Q.push(curr-> right);
Q.pop();
}
}
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main(){
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
printf("Level Order traversal of binary tree is \n");
levelOrder(root);
return 0;
}
上記の目的を達成するために、キューデータ構造が使用される。
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow