とりあえず自作の木になったかな
こんにちは。前回に引き続き、総称型を使っていきます。
なぜプログラムを書き換えたのか
以前は特定の型（stringなど）しか扱えなかった連結リストやスタックやキューだったものを、テンプレートを使って変数の型を変えても大丈夫であるように修正しました。
このようにするための方法として、総称型というものを用いました。
JavaやC#ではジェネリックスとも呼ばれています。
実は、地味にこだわったというか解決せざるを得なかったのは表示の部分です。
総称型なので、何を表示することになるかが前もってわからないのです。
そのため、それぞれのクラスを文字列に変換するとどのような表現になるかを to_string メソッドで決めています。
このような総称型を導入したことで、先に作ったプログラムのスタックやキューは文字列しか扱えなかったものを int や double も扱えるようにしました。
それだけでなく、それだけでなく、スタックやキューに 2分木のノードなどのオブジェクトも入れられるようになったのです。
実は、1月6日の記事が公開になった後に、2分木で深さ優先探索をするにはノードをスタックに入れられるようにしておく必要があるし、幅優先探索をするにはノードをキューに入れられるようにしておく必要があるし・・・と気が付きました。
しかし既に連結リストのプログラムは公開になっていたし・・・ということでプログラムを書き直しました。
ライブラリを使ってしまえばいいのですが、「車輪の再生産といわれようが自作しよう！」ということに、ほんのわずかだけこだわってみました。
2分木のプログラムを修正
それでは、今回は2分木のプログラムを掲載します。
ヘッダファイルのファイル名は mytreenode.h にしてください。
#pragma once
#include"MyStack.h"
#include"MyQueue.h"
#include<sstream>
template<typename T>
class MyTreeNode
{
public:
MyTreeNode(T element,MyTreeNode<T>* left,MyTreeNode<T>* right) {
this->_element = element;
this->_left = left;
this->_right = right;
}
T getElement() {
return this->_element;
}
MyTreeNode<T>* getLeft() {
return this->_left;
}
MyTreeNode<T>* getRight() {
return this->_right;
}
void setLeft(MyTreeNode<T>* left) {
this->_left = left;
}
void setRight(MyTreeNode<T>* right) {
this->_right = right;
}
static string order_string(string order, MyTreeNode<T>* node) {
ostringstream ss;
if (order == "pre") {
ss << node->getElement() << " ";
}
if (node->getLeft() != nullptr) {
ss << order_string(order, node->getLeft());
}
if (order == "in") {
ss << node->getElement() << " ";
}
if (node->getRight() != nullptr) {
ss << order_string(order, node->getRight());
}
if (order == "post") {
ss << node->getElement() << " ";
}
return ss.str();
}
static string depthFirst(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 breadthFirst(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->getLeft() != nullptr) {
qu->offer(tmp->getLeft());
}
if (tmp->getRight() != nullptr) {
qu->offer(tmp->getRight());
}
}
return ss.str();
}
private:
T _element;
MyTreeNode<T>* _left;
MyTreeNode<T>* _right;
};
このプログラムの変更点は総称型が使えるようになっただけではありません。
走査方法のメソッドを統合して減らしていたり、プライベートの変数やメソッドにはアンダースコアを付ける派になってみたり、地味な変更を加えています。
動作確認してみた
それでは、木構造を作ることができ、走査もできることを確認しておきましょう。
#include"MyTreeNode.h"
#include<iostream>
#include<string>
int main()
{
MyTreeNode<string>* node1 = new MyTreeNode<string>("i",nullptr,nullptr);
MyTreeNode<string>* node2 = new MyTreeNode<string>("h", nullptr, nullptr);
MyTreeNode<string>* node3 = new MyTreeNode<string>("g", node1, nullptr);
MyTreeNode<string>* node4 = new MyTreeNode<string>("f", nullptr, nullptr);
MyTreeNode<string>* node5 = new MyTreeNode<string>("e", nullptr, nullptr);
MyTreeNode<string>* node6 = new MyTreeNode<string>("d", nullptr, node2);
MyTreeNode<string>* node7 = new MyTreeNode<string>("c", node4, node3);
MyTreeNode<string>* node8 = new MyTreeNode<string>("b", node6, node5);
MyTreeNode<string>* node9 = new MyTreeNode<string>("a", node8, node7);
cout << "PreOrder : " << MyTreeNode<string>::order_string("pre", node9) << endl;
cout << "inOrder : " << MyTreeNode<string>::order_string("in", node9) << endl;
cout << "PostOrder : " << MyTreeNode<string>::order_string("post", node9) << endl;
cout << "DepthFirstSearch : " << MyTreeNode<string>::depthFirst(node9) << endl;
cout << "BreadthFirstSearch : " << MyTreeNode<string>::breadthFirst(node9) << endl;
}
実行結果は以前のプログラムと同じなので割愛します。
今回はこれでおしまいにします。それではまた。