二分木の二重順走査（ダブルオーダー走査）を実装するC++プログラム

本記事では、二分探索木（BST）における二重順走査（Double Order Traversal）を実装するC++プログラムを紹介します。

二重順走査とは、各部分木の根ノードを2回訪問する走査手法です。通常の行きがけ順・通りがけ順・帰りがけ順とは異なり、左部分木を辿る前後で根を再度出力する点が特徴です。

アルゴリズム

プログラムは以下の手順で動作します。

Begin
    クラス BST は以下の関数を持つ:
      insert() = 木に要素を挿入する:
        根ノードを設定する。
        ノードの値が根より大きければ右の子として、
        そうでなければ左の子として挿入する。
      doubleOrder() = 二重順走査を実行する:
        root == null の場合
          「木は空です」と表示する。
        それ以外の場合、以下を実行する:
          (部分)木の根を訪問する。
          左部分木を訪問する。
          再び(部分)木の根を訪問する。
          右部分木を訪問する。
End

サンプルコード

# include <iostream>
# include <cstdlib>
using namespace std;

struct nod // ノードの宣言 {
    int info;
    struct nod *l;
    struct nod *r;
}*r;

class BST {
    public:// 関数の宣言
    void insert(nod *, nod *);
    void doubleOrder(nod *);
    void show(nod *, int);
    BST() {
        r = NULL;
    }
};

void BST::insert(nod *tree, nod *newnode) {
    if (r == NULL) {
        r = new nod;
        r->info = newnode->info;
        r->l = NULL;
        r->r = NULL;
        cout<<"Root Node is Added"<<endl;
        return;
    }
    if (tree->info == newnode->info) {
        cout<<"Element already in the tree"<<endl;
        return;
    }
    if (tree->info >newnode->info) {
        if (tree->l != NULL) {
            insert(tree->l, newnode);
        } else {
            tree->l= newnode;
            (tree->l)->l = NULL;
            (tree->l)->r= NULL;
            cout<<"Node Added To Left"<<endl;
            return;
        }
    } else {
        if (tree->r != NULL) {
            insert(tree->r, newnode);
        } else {
            tree->r = newnode;
            (tree->r)->l= NULL;
            (tree->r)->r = NULL;
            cout<<"Node Added To Right"<<endl;
            return;
        }
    }
}

void BST::doubleOrder(nod *ptr) {
    if (r == NULL) {
        cout << "Tree is empty" << endl;
        return;
    }
    if (ptr != NULL) {
        cout << ptr->info << " ";
        doubleOrder(ptr->l);
        cout << ptr->info << " ";
        doubleOrder(ptr->r);
    }
}

void BST::show(nod *ptr, int level)// 木を表示する {
    int i;
    if (ptr != NULL) {
        show(ptr->r, level + 1);
        cout << endl;
        if (ptr == r)
            cout << "Root->: ";
        else {
            for (i = 0; i < level; i++)
                cout << " ";
        }
        cout << ptr->info;
        show(ptr->l, level + 1);
    }
}

int main() {
    int c, n;
    BST bst;
    nod *t;
    while (1)// switch文によるメニュー処理 {
        cout << "1.Insert Element " << endl;
        cout << "2.Double-Order Traversal" << endl;
        cout << "3.Show" << endl;
        cout << "4.Quit" << endl;
        cout << "Enter your choice : ";
        cin >>c;
        switch (c)// switch文による分岐処理 {
            case 1:
                t = new nod;
                cout << "Enter the number to be inserted : ";
                cin >>t->info;
                bst.insert(r, t);
                break;
            case 2:
                cout << "Double-Order Traversal of BST:" << endl;
                bst.doubleOrder(r);
                cout << endl;
                break;
            case 3:
                cout << "Print BST:" << endl;
                bst.show(r, 1);
                cout << endl;
                break;
            case 4:
                exit(1);
            default:
                cout << "Wrong choice" << endl;
        }
    }
}

実行結果

以下は、値 7, 6, 4, 2, 10 をこの順に挿入し、木の表示と二重順走査を実行した際の出力例です。

1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted :
7
Root Node is Added
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 6
Node Added To Left
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 4
Node Added To Left
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 2
Node Added To Left
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Right
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 3
Print BST:
10
Root->: 7
6
4
2
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 2
Double-Order Traversal of BST:
7 6 4 2 2 4 6 7 10 10
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 4

解説のポイント

• insert()：BSTの性質に従い、挿入する値が現在のノードより小さければ左部分木へ、大きければ右部分木へ再帰的に進みます。重複する値は登録されません。
• doubleOrder()：根を出力 → 左部分木を走査 → 再び根を出力 → 右部分木を走査、という順序で再帰的に処理します。そのため出力例では 7 6 4 2 2 4 6 7 10 10 のように、各ノードの値が2回ずつ現れます。
• show()：木の構造をインデント付きで視覚的に表示する補助関数です。

このように二重順走査は、木構造の前後関係を強調したい場合や、特定のアルゴリズムの学習・デバッグ時に役立つ走査方法です。