C++で2分探索木のプログラムを作ってみる

データ構造

こんにちは。もう少しC++でデータ構造のプログラムを書いていこうと思います。

今回は2分探索木です。

ちなみに2分で探索機は作れません。

2分探索木について

表題を付けたのですが、以前取り上げていたので、その投稿へのリンクを貼っておきます。

ここで取り上げた、挿入・削除・走査についてはC++で書いてみようと思います。

挿入・削除・走査のプログラム

さしあたり二分探索木3と同じアルゴリズムで二分探索木を作ります。

二分探索木になっていることを確認するための走査についても、プログラムを書いてみます。

ファイル名は MyBinarySearchTree.h としておきます。

#pragma once
#include "MyTreeNode.h"
#include "MyStack.h"
#include "MyQueue.h"
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

template <typename T>
class MyBinarySearchTree
{
public:
    MyBinarySearchTree()
    {
        _root = nullptr;
    }

    MyTreeNode<T> *find(T element)
    {
        MyTreeNode<T> *node = _root;
        while (node != nullptr && node->getElement() != element)
        {
            if (element < node->getElement())
            {
                node = node->getLeft();
            }
            else
            {
                node = node->getRight();
            }
        }
        return node;
    }

    void insert(T element)
    {
        if (_root == nullptr)
        {
            MyTreeNode<T> *tmp = new MyTreeNode<T>(element, nullptr, nullptr);
            _root = tmp;
            return;
        }
        insert(_root, element);
    }

    bool del(T element)
    {
        if (find(element) == nullptr)
        {
            return false;
        }

        MyTreeNode<T> *parent = nullptr;
        MyTreeNode<T> *child = _root;

        while (child->getElement() != element)
        {
            if (element < child->getElement())
            {
                parent = child;
                child = child->getLeft();
            }
            else
            {
                parent = child;
                child = child->getRight();
            }
        }

        if (child->getLeft() == nullptr && child->getRight() == nullptr)
        {
            if (child == _root)
            {
                _root = nullptr;
                return true;
            }

            if (child == parent->getLeft())
            {
                parent->setLeft(nullptr);
            }
            else
            {
                parent->setRight(nullptr);
            }
            return true;
        }

        if (child->getLeft() == nullptr || child->getRight() == nullptr)
        {
            MyTreeNode<T> *node;
            if (child->getLeft() == nullptr)
            {
                node = child->getRight();
            }
            else
            {
                node = child->getLeft();
            }

            if (child == _root)
            {
                _root = node;
            }
            else if (child == parent->getLeft())
            {
                parent->setLeft(node);
            }
            else
            {
                parent->setRight(node);
            }
            return true;
        }

        if (child == _root)
        {
            _root = child->getLeft();
        }
        else if (parent->getLeft() == child)
        {
            parent->setLeft(child->getLeft());
        }
        else
        {
            parent->setRight(child->getLeft());
        }
        MyTreeNode<T> *node = child->getRight();
        child = child->getLeft();
        while (child->getRight() != nullptr)
        {
            child = child->getRight();
        }
        child->setRight(node);
        return true;
    }

    void printOrder(string tp)
    {
        cout << tp << "Order : " << MyBinarySearchTree<T>::order(_root, tp) << endl;
    }

    void printDepthFirst()
    {
        cout << "DepthFirstSearch : " << MyBinarySearchTree<T>::depth(_root) << endl;
    }

    void printBreadthFirst()
    {
        cout << "BreadthFirstSearch : " << MyBinarySearchTree<T>::breadth(_root) << endl;
    }

    void printTree()
    {
        cout << treeToString(0, "", _root) << endl;
    }

private:
    MyTreeNode<T> *_root;

    void insert(MyTreeNode<T> *node, T element)
    {
        if (element < node->getElement())
        {
            if (node->getLeft() == nullptr)
            {
                MyTreeNode<T> *tmp = new MyTreeNode<T>(element, nullptr, nullptr);
                node->setLeft(tmp);
                return;
            }
            else
            {
                insert(node->getLeft(), element);
                return;
            }
        }
        else
        {
            if (node->getRight() == nullptr)
            {
                MyTreeNode<T> *tmp = new MyTreeNode<T>(element, nullptr, nullptr);
                node->setRight(tmp);
                return;
            }
            else
            {
                insert(node->getRight(), element);
                return;
            }
        }
    }

    static string order(MyTreeNode<T> *node, string tp)
    {
        ostringstream ss;

        if (tp == "pre")
        {
            ss << " " << node->getElement();
        }
        if (node->getLeft() != nullptr)
        {
            ss << order(node->getLeft(), tp);
        }
        if (tp == "in")
        {
            ss << " " << node->getElement();
        }
        if (node->getRight() != nullptr)
        {
            ss << order(node->getRight(), tp);
        }
        if (tp == "post")
        {
            ss << " " << node->getElement();
        }
        return ss.str();
    }

    static string depth(MyTreeNode<T> *node)
    {
        MyStack<MyTreeNode<T> *> *st = new MyStack<MyTreeNode<T> *>();
        MyTreeNode<T> *tmp;
        ostringstream ss;

        st->push(node);
        while (!st->empty())
        {
            tmp = st->pop();
            ss << " " << tmp->getElement();

            if (tmp->getRight() != nullptr)
            {
                st->push(tmp->getRight());
            }

            if (tmp->getLeft() != nullptr)
            {
                st->push(tmp->getLeft());
            }
        }
        return ss.str();
    }

    static string breadth(MyTreeNode<T> *node)
    {
        MyQueue<MyTreeNode<T> *> *qu = new MyQueue<MyTreeNode<T> *>();
        MyTreeNode<T> *tmp;
        ostringstream ss;

        qu->offer(node);
        while (!qu->isEmpty())
        {
            tmp = qu->poll();
            ss << " " << tmp->getElement();

            if (tmp->getRight() != nullptr)
            {
                qu->offer(tmp->getRight());
            }

            if (tmp->getLeft() != nullptr)
            {
                qu->offer(tmp->getLeft());
            }
        }
        return ss.str();
    }

    static string treeToString(int n, string direction, MyTreeNode<T> *node)
    {
        if (node == nullptr)
        {
            return "";
        }
        ostringstream ss;

        ss << setw(4) << left << node->getElement();

        if (node->getLeft() != nullptr && node->getRight() != nullptr)
        {
            ss << "┬";
        }
        else if (node->getRight() != nullptr)
        {
            ss << "─";
        }
        else if (node->getLeft() != nullptr)
        {
            ss << "┐";
        }

        if (node->getRight() != nullptr && node->getLeft() != nullptr)
        {
            ss << treeToString(n + 1, direction + "R", node->getRight());
        }
        else if (node->getRight() != nullptr)
        {
            ss << treeToString(n + 1, direction + "r", node->getRight());
        }

        if (node->getLeft() != nullptr)
        {
            ss << endl;
            for (int i = 0; i <= n; i++)
            {
                ss << "    ";
                if (i < n && direction.substr(i, 1) == "R")
                {
                    ss << "│";
                }
                else if (i < n)
                {
                    ss << "  ";
                }
            }
            ss << "└";
            ss << treeToString(n + 1, direction + "L", node->getLeft());
        }
        return ss.str();
    }
};

動作確認のプログラム

ここまでの動作確認をしてみます。

動作確認用のプログラムです。

#include "MyBinarySearchTree.h"
#include <iostream>
#include <string>
#include <random>
using namespace std;

int main()
{
    srand((unsigned)time(NULL));
    MyBinarySearchTree<int> *bst = new MyBinarySearchTree<int>();

    int count = 0;

    while (count < 20)
    {
        int r = rand() % 100 + 1;
        bst->insert(r);
        cout << "Insert " << r << endl;
        bst->printTree();
        cout << endl;
        count++;
    }

    bst->printOrder("pre");
    bst->printOrder("in");
    bst->printOrder("post");
    bst->printDepthFirst();
    bst->printBreadthFirst();
    bst->printTree();

    for (int i = 0; i < 5; i++)
    {
        int r = rand() % 100 + 1;
        if (bst->find(r) == nullptr)
        {
            cout << r << "はありません" << endl;
        }
        else
        {
            cout << r << "はあります" << endl;
        }
    }

    count = 0;
    while (count < 10)
    {
        int r = rand() % 100 + 1;
        if (bst->del(r))
        {
            cout << "Delete " << r << endl;
            bst->printOrder("in");
            bst->printTree();
            cout << endl;

            count++;
        }
    }
}

実行結果

上のプログラムの確認をしてみます。

Insert 58
58

Insert 52
58  ┐
    └52

Insert 92
58  ┬92
    └52

Insert 56
58  ┬92
    └52  ─56

Insert 63
58  ┬92  ┐
    │    └63
    └52  ─56

Insert 56
58  ┬92  ┐
    │    └63
    └52  ─56  ─56

Insert 51
58  ┬92  ┐
    │    └63
    └52  ┬56  ─56
          └51

Insert 31
58  ┬92  ┐
    │    └63
    └52  ┬56  ─56
          └51  ┐
                └31

Insert 34
58  ┬92  ┐
    │    └63
    └52  ┬56  ─56
          └51  ┐
                └31  ─34

Insert 47
58  ┬92  ┐
    │    └63
    └52  ┬56  ─56
          └51  ┐
                └31  ─34  ─47

Insert 54
58  ┬92  ┐
    │    └63
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ─34  ─47

Insert 5
58  ┬92  ┐
    │    └63
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ┬34  ─47
                      └5

Insert 26
58  ┬92  ┐
    │    └63
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ┬34  ─47
                      └5   ─26

Insert 34
58  ┬92  ┐
    │    └63
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ┬34  ─47  ┐
                      │          └34
                      └5   ─26

Insert 2
58  ┬92  ┐
    │    └63
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ┬34  ─47  ┐
                      │          └34
                      └5   ┬26
                            └2

Insert 42
58  ┬92  ┐
    │    └63
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ┬34  ─47  ┐
                      │          └34  ─42
                      └5   ┬26
                            └2

Insert 99
58  ┬92  ┬99
    │    └63
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ┬34  ─47  ┐
                      │          └34  ─42
                      └5   ┬26
                            └2

Insert 71
58  ┬92  ┬99
    │    └63  ─71
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ┬34  ─47  ┐
                      │          └34  ─42
                      └5   ┬26
                            └2

Insert 92
58  ┬92  ┬99  ┐
    │    │    └92
    │    └63  ─71
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ┬34  ─47  ┐
                      │          └34  ─42
                      └5   ┬26
                            └2

Insert 4
58  ┬92  ┬99  ┐
    │    │    └92
    │    └63  ─71
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ┬34  ─47  ┐
                      │          └34  ─42
                      └5   ┬26
                            └2   ─4

preOrder :  58 52 51 31 5 2 4 26 34 47 34 42 56 54 56 92 63 71 99 92
inOrder :  2 4 5 26 31 34 34 42 47 51 52 54 56 56 58 63 71 92 92 99
postOrder :  4 2 26 5 42 34 47 34 31 51 54 56 56 52 71 63 92 99 92 58
DepthFirstSearch :  58 52 51 31 5 2 4 26 34 47 34 42 56 54 56 92 63 71 99 92
BreadthFirstSearch :  58 92 52 99 63 56 51 92 71 56 54 31 34 5 47 26 2 34 4 42
58  ┬92  ┬99  ┐
    │    │    └92
    │    └63  ─71
    └52  ┬56  ┬56
          │    └54
          └51  ┐
                └31  ┬34  ─47  ┐
                      │          └34  ─42
                      └5   ┬26
                            └2   ─4
71はあります
51はあります
56はあります
31はあります
39はありません
Delete 54
inOrder :  2 4 5 26 31 34 34 42 47 51 52 56 56 58 63 71 92 92 99
58  ┬92  ┬99  ┐
    │    │    └92
    │    └63  ─71
    └52  ┬56  ─56
          └51  ┐
                └31  ┬34  ─47  ┐
                      │          └34  ─42
                      └5   ┬26
                            └2   ─4

Delete 99
inOrder :  2 4 5 26 31 34 34 42 47 51 52 56 56 58 63 71 92 92
58  ┬92  ┬92
    │    └63  ─71
    └52  ┬56  ─56
          └51  ┐
                └31  ┬34  ─47  ┐
                      │          └34  ─42
                      └5   ┬26
                            └2   ─4

Delete 31
inOrder :  2 4 5 26 34 34 42 47 51 52 56 56 58 63 71 92 92
58  ┬92  ┬92  
    │    └63  ─71
    └52  ┬56  ─56
          └51  ┐
                └5   ┬26  ─34  ─47  ┐
                      │                └34  ─42
                      └2   ─4

Delete 47
inOrder :  2 4 5 26 34 34 42 51 52 56 56 58 63 71 92 92
58  ┬92  ┬92
    │    └63  ─71
    └52  ┬56  ─56
          └51  ┐
                └5   ┬26  ─34  ─34  ─42
                      └2   ─4

Delete 42
inOrder :  2 4 5 26 34 34 51 52 56 56 58 63 71 92 92
58  ┬92  ┬92
    │    └63  ─71
    └52  ┬56  ─56
          └51  ┐
                └5   ┬26  ─34  ─34
                      └2   ─4

Delete 4
inOrder :  2 5 26 34 34 51 52 56 56 58 63 71 92 92
58  ┬92  ┬92  
    │    └63  ─71
    └52  ┬56  ─56
          └51  ┐
                └5   ┬26  ─34  ─34
                      └2

Delete 63
inOrder :  2 5 26 34 34 51 52 56 56 58 71 92 92
58  ┬92  ┬92
    │    └71
    └52  ┬56  ─56
          └51  ┐
                └5   ┬26  ─34  ─34
                      └2

Delete 71
inOrder :  2 5 26 34 34 51 52 56 56 58 92 92
58  ┬92  ─92
    └52  ┬56  ─56
          └51  ┐
                └5   ┬26  ─34  ─34
                      └2

Delete 2
inOrder :  5 26 34 34 51 52 56 56 58 92 92
58  ┬92  ─92
    └52  ┬56  ─56
          └51  ┐
                └5   ─26  ─34  ─34

Delete 26
inOrder :  5 34 34 51 52 56 56 58 92 92
58  ┬92  ─92
    └52  ┬56  ─56
          └51  ┐
                └5   ─34  ─34

とりあえず動いているようです。しかし、 等幅フォントなら揃っているのですが 、フォント幅のせいで崩れるのが残念です。

今回はこれでおしまいにします。

それではまた。

Posted by 春日井 優