さまざまなデータ構造をC++で書いてみる（３）

データ構造

こんにちは。

前回に引き続き，データ構造を扱っていきます。

今回は2分木です。

２分木をC++で書いてみる

今回もこれまでと同じように以前の記事へのリンクをはっておきます。

詳しい説明はリンク先を読んでください。

それでは２分木を作ってみます。

ヘッダファイルのファイル名は mytreenode.h にしてください。

#ifndef _MYTREENODE_H_
#define _MYTREENODE_H_
#endif
#include <string>
using namespace std; 
       
class MyTreeNode
{
public:
	MyTreeNode(string, MyTreeNode*, MyTreeNode*);
	string getElement();
	MyTreeNode* getLeft();
	MyTreeNode* getRight();
	void setLeft(MyTreeNode*);
	void setRight(MyTreeNode*);
	string preOrder(MyTreeNode*);
	string inOrder(MyTreeNode*);
	string postOrder(MyTreeNode*);
	string depthFirst(MyTreeNode*);
	string breadthFirst(MyTreeNode*);
private:
	string element;
	MyTreeNode* left;
	MyTreeNode* right;
};

次にクラス定義のファイルになります。

ファイル名は mytreenode.cpp にしておいてください。

#include "MyTreeNode.h"
#include <stack>
#include <queue>
#include <iostream>
       
MyTreeNode::MyTreeNode(string element, MyTreeNode* left, MyTreeNode* right)
{
	this->element = element;
	this->left = left;
	this->right = right;
}
       
string MyTreeNode::getElement()
{
	return this->element;
}
       
MyTreeNode* MyTreeNode::getLeft()
{
	return this->left;
}
       
MyTreeNode* MyTreeNode::getRight()
{
	return this->right;
}
       
void MyTreeNode::setLeft(MyTreeNode* left)
{
	this->left = left;
}
       
void MyTreeNode::setRight(MyTreeNode* right)
{
	this->right = right;
}
       
string MyTreeNode::preOrder(MyTreeNode* node)
{
	string result = node->getElement();
	if (node->getLeft() != nullptr) {
		result += " " + preOrder(node->getLeft());
	}
	if (node->getRight() != nullptr) {
		result += " " + preOrder(node->getRight());
	}
	return result;
}
       
string MyTreeNode::inOrder(MyTreeNode* node)
{
	string result = "";
	if (node->getLeft() != nullptr) {
		result += inOrder(node->getLeft());
	}
	result += " " + node->getElement();
	if (node->getRight() != nullptr) {
		result += inOrder(node->getRight());
	}
	return result;
}
       
string MyTreeNode::postOrder(MyTreeNode* node)
{
	string result = "";
	if (node->getLeft() != nullptr) {
		result += postOrder(node->getLeft());
	}
	if (node->getRight() != nullptr) {
		result += postOrder(node->getRight());
	}
	result += " " + node->getElement();
	return result;
}
       
string MyTreeNode::depthFirst(MyTreeNode* node)
{
	stack st;
	MyTreeNode* tmp;
    
	string result = "";
	st.push(node);
	while (!st.empty()) {
		tmp = st.top();
		st.pop();
		result += " " + tmp->getElement();
		if (tmp->getRight() != nullptr) {
			st.push(tmp->getRight());
		}
		if (tmp->getLeft() != nullptr) {
			st.push(tmp->getLeft());
		}
	}
	return result;
}
       
string MyTreeNode::breadthFirst(MyTreeNode* node)
{
	queue qu;
	MyTreeNode* tmp;
    
	string result = "";
	qu.push(node);
	while (!qu.empty()) {
		tmp = qu.front();
		qu.pop();
		result += " " + tmp->getElement();
		if (tmp->getLeft()!=nullptr) {
			qu.push(tmp->getLeft());
		}
		if (tmp->getRight() != nullptr) {
			qu.push(tmp->getRight());
		}
	}
	return result;
}

２分木を走査する

それでは，実際に２分木を作って走査します。

走査についての説明は上のリンクに書いてあります。

C++版のプログラムです。

#include<iostream>
#include"MyTreeNode.h"
using namespace std;
    
int main() {
	MyTreeNode* node1 = new MyTreeNode("i", nullptr, nullptr);
	MyTreeNode* node2 = new MyTreeNode("h", nullptr, nullptr);
	MyTreeNode* node3 = new MyTreeNode("g", node1, nullptr);
	MyTreeNode* node4 = new MyTreeNode("f", nullptr, nullptr);
	MyTreeNode* node5 = new MyTreeNode("e", nullptr, nullptr);
	MyTreeNode* node6 = new MyTreeNode("d", nullptr, node2);
	MyTreeNode* node7 = new MyTreeNode("c", node4, node3);
	MyTreeNode* node8 = new MyTreeNode("b", node6, node5);
	MyTreeNode* node9 = new MyTreeNode("a", node8, node7);
    
	cout << "PreOrder  : " << node9->preOrder(node9) << endl;
	cout << "InOrder   :" << node9->inOrder(node9) << endl;
	cout << "PostOrder :" << node9->postOrder(node9) << endl;
    
	cout << "DepthFirstSearch   :" << node9->depthFirst(node9) << endl;
	cout << "BreadthFirstSearch :" << node9->breadthFirst(node9) << endl;
}

実行結果です。

PreOrder  : a b d h e c f g i
InOrder   : d h b e a f c i g
PostOrder : h d e b f i g c a
DepthFirstSearch   : a b d h e c f g i
BreadthFirstSearch : a b c d e f g h i

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

Posted by 春日井 優