C++で２分探索木のプログラムを作ってみる
こんにちは。もう少しC++でデータ構造のプログラムを書いていこうと思います。
今回は2分探索木です。
ちなみに２分で探索機は作れません。
2分探索木について
表題を付けたのですが、以前取り上げていたので、その投稿へのリンクを貼っておきます。
https://joho-ka.mints.ne.jp/binary-search-tree01
ここで取り上げた、挿入・削除・走査についてはC++で書いてみようと思います。
挿入・削除・走査のプログラム
さしあたり二分探索木３と同じアルゴリズムで二分探索木を作ります。
二分探索木になっていることを確認するための走査についても、プログラムを書いてみます。
ファイル名は 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
とりあえず動いているようです。しかし、 等幅フォントなら揃っているのですが 、フォント幅のせいで崩れるのが残念です。
今回はこれでおしまいにします。
それではまた。