C++ ツリー ノード 書いて覚えるための初心者自己中記事

ノードが複数のノードを接続されているデータ構造をツリーと呼ぶ。

代表的なのはパソコンのフォルダやファイルがそれ。

このツリーは階層的にデータを扱える。

次のノードを子ノード（child node）

前のノードを親ノード（parent node）

親と子をつなぐ線（図にした場合のはなし？）をブランチ

という。

ツリーをどんどん親側にたどっていくと頂点に唯一のノードがある。

これをルート（root）という。

また逆に子ノードを持たないノードをリーフ（葉）または、終端ノード（end-node）という。

ルートからの距離を深さ（depth）という。距離？１depth ２depthって数えるのか？

以前勉強したリストは親、子、それぞれ一つずつ持っていた。

これもツリー。

リストでは単方向、双方向があったがツリーも子ノードしか持たないツリーもあれば親、子、両方もつツリーもある。

テキスト終盤だとさらっと前置き、ドバっとコードが増えてきたな。

また、一つずつ確認していこう。

template <typename TYPE>
class Tree {
public:
	struct Node {
		typedef list<Node*> Children;
		typedef typename Children::iterator Iterator;
		typedef typename Children::const_iterator CIterator;
 
		TYPE value;//ノードに関連づけられたあたい
		Children children;//子ノード
 
		Node(const TYPE& value) : value(value) {}
	};

private:
	Node* m_root;//ルートノード
};

ます、テンプレートクラスTreeがあって、

中には構造体Nodeがある。

typedef でlistクラステンプレートに構造体Nodeポインタを指定。Childrenと名付ける。

さらにtypedefでそのChildren のイテレータをIterator と名付ける。const_iteratorもCIteratorにする。

この時、typenameが付いているのは、上のlist<node*>と違い、型であるということを明示する必要がある為っぽい。

メンバ変数として、

TreeクラステンプレートのTYPE型のvalue と

list<Node*>のchildrenも用意。

さらに構造体の引数付きコンストラクタを作成。構造体オブジェクト作成時にvalueに値を入れる作戦だ。

また、クラステンプレートTreeのメンバ変数は

Nodeポインタのm_root 

ルートノードということだ。ダミーノードの立ち位置か？

ここは何とか・・。

次。

	typedef typename Node::Children Children;
	typedef typename Node::Iterator Iterator;
	typedef typename Node::CIterator CIterator;
 
public:
	explicit Tree(const TYPE& value) {
		m_root = new Node(value);//ルートノードを作成
	}

クラステンプレートTreeのコンストラクタとtypedef達。

typedefでは構造体Nodeの中でtypedefったのをクラステンプレートTreeでも使用できるようにしている。のか？

コンストラクタではexplicit で暗黙キャストをさせないようにしている。

クラステンプレートTreeのオブジェクト作成時に引数をとり、ルートノードのm_rootをnewで作成、値を入れている。

ルートノードが一番初めに作られるのね。

次、

	//ルートノード以外全削除
	void Clear() {
		Clear(m_root);
	}
 
private:
	void Clear(Node* node) {
		//子ノードをすべて破壊
		Children& children = node->children;
		for (Iterator it = children.begin(); it != children.end(); ++it) {
			Clear(*it);//これはどこのClearだ？？？
		}
		children.clear();//listクラステンプレートのclear
 
		//ルートノードだけはdeleteしない
		if (node != m_root) { delete node; }
	}

デストラクタの前にメンバ関数Clear。

Clearはオーバーロードしていて、引数付きのほうが本体っぽい。

引数に指定したノードの子ノードを削除するのかな？

listクラステンプレートのメンバ関数clearでリストの削除はしてるけど、その前にforで行っているイテレータを引数にしたClearはどなた？

イテレータを引数にとるClear関数なんて習ったっけ？

 あっ！！！

今日勉強した再帰関数じゃないですか？？そうですよね？？

 あぁ、スッキリした。

子ノードの子ノードとかいろいろ居るからこうするのが良いのか。

あれ、でも再帰関数で同じ階層のノードをforで回りつくしたらどうなるんだ？

最終的に終端ノードに行ったときって、node->children がNULLになるのか？

 いや、まて、そもそも今回のノードでは子ノードがリストだった。

ルートノードに子ノードを一つ付けたら、その子ノードもリストの子ノードを持てるわけでしょ？

　　       　　　[               ルートノード                   ]

           [子ノード]        |         [子ノード]           |       [子ノード] 

 [子ノード] [子ノード] | [子ノード] [子ノード] |  [子ノード] [子ノード] 

 この状態で、仮にClear関数でルートノードを引数にしてたとしたら、

一段下の子ノードリストのイテレータが用意されて、

forで子ノードを回るときに再帰関数で三段目の子ノードに行って、

三段目の子ノードがforで回るときに再帰関数が呼ばれて、

そこではもう子ノードが無いからそれはヌルポインタって事？

エラーにはならないのか？

ならないのか。

その場合はforが成立しないからリストメンバ関数のclearなわけか？

強引な感じがするけど、そう思おう。

でリストを削除したら、ノード自体も削除。

う～ん。なんかもやもやする。

つぎ、

virtual ~Tree() {
	Clear();
	delete m_root;//Clearはルートノードを破棄しないので、ここで破棄します
}

 デストラクタ。

さっきのClearメンバ関数だけだとルートノードは消えないから別でdeleteする。

次。

//ルートノードを取得
Node* GetRoot() { return m_root; }
const Node* GetRoot()const { return m_root; }

 これはそのまま。

つぎ、

//nodeの子ノードにvalueを持ったノードを作成
static Node* Append(Node* node, const TYPE& value) {
	Node* child = new Node(value);
	node->children.push_back(child);
	return child;
}

 引数でしていたノードに子ノードを作る。作る際に同じく指定した値を引数として使う。node->children はlist<Node*> だからクラステンプレートlistのメンバ関数push_backが使用できる。

作った子ノードを返り値にしている。

ところでこの関数だけstatic なのはなんでだろう。

うーん。なんかmain関数内でAppend関数を直接呼び出してるっぽい。

それが理由なのかな？

ツリー構造のクラステンプレートTree はここまで。

つぎは、そのクラスを使うコード。

typedef Tree<string> NameTree;
typedef NameTree::Node Node;
typedef NameTree::Children Children;
typedef NameTree::CIterator CIteraotr;

 まず、typedef 

stringクラスを型に指定した NameTree

NameTree のNode  Node

NameTreeのChildren Children

NameTreeのCIterator CIterator

ChildrenとCIterator はTreeクラスでtypedefされたのをこっちでも使えるようにって事かな。

void Show(const Node* node, int depth = 0) {
	cout << setw(depth * 2) << " " << node->value << endl;
 
	const Children& children = node->children;
	for (CIteraotr it = children.begin(); it != children.end(); ++it) {
		Show(*it, depth + 1);
	}
}

 Show関数。

 ノードを受け取る、ルートノードを使うんだろうな。

cout のところで使われている関数 setw は出力幅を指定するマニピュレータなのか。

階層を表現するためだな。

で、さっきClear関数でさんざん悩んだのと同じ再帰関数だわ。

引数depthで階層を増やしている。

これでマニピュレータsetwも活躍。

NameTree tree("hoge");
 
Node* hoge = tree.GetRoot();
 
Node* foo = NameTree::Append(hoge, "foo");
Node* bar = NameTree::Append(hoge, "bar");
NameTree::Append(hoge, "readme.txt");
NameTree::Append(foo, "foo.h");
NameTree::Append(foo, "foo.cpp");
NameTree::Append(bar, "bar.h");
NameTree::Append(bar, "bar.cpp");
 
Show(hoge);
//output
 hoge
  foo
   foo.h
   foo.cpp
  bar
   bar.h
   bar.cpp
  readme.txt

main関数内。

さっきのtypedefでNameTree は Tree<string> だったな。

Node* hoge にルートノードをお取り寄せ。

そうかこのNodeはtypedefされたNodeなのか。ポインタ行けるんだ。

Appendで子ノード作ってNode*にお取り寄せ。

最後にShow。

ツリーはまだ続きそう。

とりあえずここまで。