サンプル・プログラム
ツリー構造


ファイルを格納するためのディレクトリ構造や、後述するXMLなどがツリー構造の代表例である。

PHPによるツリー
ツリーでは、リストで実装したメソッドに加え、下の階層(子ノード)を追加したり削除するメソッドが必要になる。


あらたに pahooTree のインスタンスを生成し、それを pahooList の append メソッドを使って追加してやればいい。
ただし、あとで子ノードを探索したり削除することを考えると、双方向リストと同じ考え方で、子ノードから親ノードへのリンク情報が必要だ。これは、ディレクトリで言うところの ".." と同じである。
そこで、クラス pahooTree のクラス変数として、子ノードを生成したら、$parentOBJ に親ノードのインスタンスそのものを、$parentPTR に親ノードのポインタ位置を記録しておくようにする。

クラス pahooTree では pahooList のメソッドに加え、次のメソッドを用意した。
メソッド | 機能 |
---|---|
appendChild() | ノードの末尾に子ノードを追加する。初期の子ノードは空である。 |
isparent() | 親ノードがあるかどうか判定する。 |
ischild() | 現在のポインタが子ノードを示すかどうか判定する。 |
appendChild() | 現在のポインタノードの末尾に子ノードを追加する。初期の子ノードは空である。 |
insertChild() | 現在のポインタ位置(ポインタが示す要素の前)に子ノードを1つ挿入する。初期の子ノードは空である。 |
deleteChild() | 現在のポインタが指す子ノードを1つ削除する。ノードでなければ何もしない。 |
moveChild() | 現在のポインタ位置に子ノードがあれば移動する。ノードでなければ何もしない。 |
moveParent() | 親ノードがあれば移動する。ポインタは子ノードを呼んでいる位置へ進める。 |
list() | ツリーの内容を成形して返す(リスト型)。 |
tree() | ツリーの内容を成形して返す(階層型)。 |
1187: */
1188: function __construct() {
1189: $this->error = FALSE;
1190: $this->errmsg = '';
1191: $this->plist = new pahooList();
1192: }
1193:
1194: /**
1195: * デストラクタ
1196: * @param なし
1197: * @return なし
1198: */
1199: function __destruct() {
1200: $this->plist = NULL;
1201: }
1202:
1203: /**
1204: * スタックに要素を1つ追加する
1205: * @param mixed $data 追加する要素
1206: * @return なし
1207: */
1208: function push($data) {
1209: $this->plist->append($data);
1210: $this->error = $this->plist->error;
1211: $this->errmsg = $this->plist->errmsg;
1212: return (! $this->error);
1213: }
1214:
1215: /**
1216: * スタックから要素を1つ取り出す
1217: * @param なし
1218: * @return mixed 取り出した要素/NULL 要素がない
1219: */
1220: function pop() {
1221: if ($this->len() == 0) {
1222: $this->error = TRUE;
1223: $this->errmsg = 'stack: No data';
1224: return NULL;
1225: } else {
1226: $this->plist->moveTail();
1227: $data = $this->plist->get();
1228: $this->plist->delete();
1229: return $this->error ? NULL : $data;
1230: }
1231: }
1232:
1233: /**
1234: * スタックに残っている要素数を数える
1235: * @param なし
1236: * @return int キューの要素数
1237: */
1238: function len() {
1239: return $this->plist->len();
1240: }
1241:
1242: /**
1243: * スタックの内容を成形して返す
1244: * @param なし
1245: * @return string リストの内容
1246: */
1247: function list2() {
1248: return $this->plist->list2();
1249: }
1250:
1251: // End of Class
1252: }
1253:
1254: // pahooTree クラス ==========================================================
1255: class pahooTree extends pahooList {
1256: public $parentOBJ; //親ノードのオブジェクト
1257: public $parentPTR; //親ノードのポインタ
1258:
1259: /**
1260: * コンストラクタ
1261: * @param pahooTree $paret 親ノード/NULL:自らが親ノード
1262: * @return なし
1263: */
1264: function __construct($obj=NULL, $pointer=self::ANCHOR) {
1265: parent::__construct();
1266: $this->parentOBJ = $obj;
1267: $this->parentPTR = $pointer;
1268: }
1269:
1270: /**
1271: * 親ノードがあるかどうかを判定する
1272: * @param なし
1273: * @return bool TRUE:親ノードがある/FALSE:親ノードがない
1274: */
1275: function isparent() {
1276: return ($this->parent == NULL) ? FALSE : TRUE;
1277: }
1278:
1279: /**
1280: * 現在のポインタが子ノードを示すかどうか判定する
1281: * @param なし
1282: * @return bool TRUE:子ノードを示す/FALSE:子ノードを示さない
1283: */
1284: function ischild() {
1285: return ($this->get() instanceof pahooTree);
1286: }
1287:
1288: /**
1289: * ツリーの末尾に子ノードを1つ追加する
1290: * @param なし
1291: * @return pahooTree 追加した子ノード
1292: */
1293: function appendChild() {
1294: $child = new pahooTree($this, $this->pointer);
1295: $pointer = $this->append($child);
1296: $child->parentPTR = $pointer;
1297:
1298: return $child;
1299: }
1300:
1301: /**
1302: * 現在のポインタ位置(ポインタが示す要素の前)に子ノードを1つ挿入する
1303: * @param なし
1304: * @return pahooTree 挿入した子ノード
1305: */
1306: function insertChild() {
1307: $child = new pahooTree($this, $this->pointer);
1308: $this->insert($child);
1309: return $child;
1310: }
1311:
1312: /**
1313: * 現在のポインタ位置(ポインタが示す要素の前)の子ノードを削除する
1314: * @param なし
1315: * @return int 削除した要素のインデックス/FALSE:子ノードではない
1316: */
1317: function deleteChild() {
1318: $res = FALSE;
1319: $child = $this->get();
1320: if ($child instanceof pahooTree) {
1321: $res = $this->delete();
1322: $child = NULL;
1323: }
1324: return $res;
1325: }
1326:
1327: /**
1328: * 現在のポインタ位置(ポインタが示す要素の前)に子ノードがあれば移動する
1329: * @param なし
1330: * @return pahooTree 子ノード/NULL:子ノードではない
1331: */
1332: function moveChild() {
1333: $res = NULL;
1334: $child = $this->get();
1335: if ($child instanceof pahooTree) {
1336: $child->moveRoot();
1337: $res = $child;
1338: }
1339: return $res;
サンプル・プログラム
11: //データ構造クラス
12: require_once('pahooDataStructure.php');
13:
14: /**
15: * 検索キーを含むノードを探す
16: * @param string $key 検索キー
17: * @param pahooTree $tree 探索対象ノード
18: * @return pahooTree 検索キーが存在するノード
19: */
20: function searchItem($key, $tree) {
21: $res = NULL;
22: $tree->moveRoot();
23: while (! $tree->istail()) {
24: $data = $tree->get();
25: if ($data instanceof pahooTree) {
26: $res = searchItem($key, $data);
27: if ($res != NULL) return $res;
28: $tree->moveNext();
29: } else if ($data == $key) {
30: return $tree;
31: } else {
32: $tree->moveNext();
33: }
34: }
35: return $res;
36: }
37:
38: // メイン・プログラム ======================================================
39: $tree = new pahooTree(); //ツリーを用意
40: $key = '3-B'; //検索キー
41:
42: $tree->append('1-A'); //第1階層に要素を追加
43: $tree->append('1-B');
44: $tree->append('1-C');
45: $child1 = $tree->appendChild(); //子ノード(第2階層)を追加
46: $child1->append('2-A'); //第2階層に要素を追加
47: $child1->append('2-B');
48: $child2 = $child1->appendChild(); //子ノード(第3階層)を追加
49: $child2->append('3-A'); //第3階層に要素を追加
50: $child2->append('3-B');
51: $child2->moveParent(); //親ノード(第2階層)に戻る
52: $child1->append('2-C');
53: $child1->moveParent();
54: $tree->append('1-D');
55:
56: $outstr = $tree->tree(); //現在のツリーを表示
57: printf("\nツリー\n%s\n", $outstr);
58:
59: $node = searchItem($key, $tree); //検索キーを含むノードを削除
60: if ($node != NULL) {
61: $parent = $node->moveParent();
62: $parent->deleteChild();
63: } else {
64: $outstr = 'No hit';
65: }
66: $outstr = $tree->tree(); //現在のツリーを表示
67: printf("\n削除後\n%s", $outstr);


実行結果は左図の通り。
PHPで XMLデータをツリーへ代入
ここでは、「PHPで天気予報を求める(その2)」で利用したWebAPIの出力XMLをツリーに読み込み、表示するPHPプログラムを作ってみることにする。
11: //データ構造クラス
12: require_once('pahooDataStructure.php');
13:
14: /**
15: * XMLの内容をツリーに代入(再帰呼び出し)
16: * @param SimpleXmlIterator $xml XMLデータ
17: * @param pahooTree $tree 探索対象ノード
18: * @return なし
19: */
20: function xml2tree($xml, $tree) {
21: $xml->rewind();
22: while ($xml->valid()) {
23: //子ノード
24: if ($xml->hasChildren()) {
25: $child = $tree->appendChild();
26: xml2tree($xml->getChildren(), $child);
27: //要素
28: } else {
29: $str = $xml->key() . ':' . (string)$xml->current();
30: $tree->append($str);
31: }
32: $xml->next();
33: }
34: }
35:
36: // メイン・プログラム ======================================================
37: //東京の天気 - livedoor天気情報
38: $url = 'http://weather.livedoor.com/forecast/rss/area/130010.xml';
39: $xml = new SimpleXmlIterator($url, 0, TRUE);
40: if ($xml == FALSE) {
41: print 'error: load -- ' . $url;
42: exit(1);
43: }
44:
45: //ツリーに代入
46: $tree = new pahooTree();
47: xml2tree($xml, $tree);
48:
49: //ツリーを表示
50: $outstr = $tree->tree();
51: printf("\n%s", $outstr);

XMLの読み込みには、PHP5で導入された SimpleXMLIterator クラスを利用する。
SimpleXMLIteratorクラス自体がツリー構造で成り立っているので、pahooTree への代入は、簡単なユーザー関数 xml2tree を書けば実装できる。子ノードが現れたら自身を呼び出す再帰関数となっている。

実行結果は下図の通り。

Pythonによるツリー
PHPの場合と異なり、ユーザークラス pahooList を継承しているわけではないので、リスト関係で必要なメソッドも追加している。
# pahooTree クラス ==========================================================
class pahooTree: #ツリー構造
"""
* コンストラクタ
* @param mixed item 格納する要素
* @param pahooTree paret 親ノード/None:自らが親ノード
* @param pahooTree left 親ノードの左ならTrue、右ならFalse
* @return なし
"""
def __init__(self, obj=None, pointer=None):
self.item = list() #要素を格納するリスト
self.pointer = 0 #ポインタ
self.parentOBJ = obj #親ノードのオブジェクト
self.parentPTR = pointer #親ノードのポインタ
self.error = False #エラーフラグ
self.errmsg = '' #エラーメッセージ
"""
* 現在のポインタが先頭を指すかどうかを判定する
* @param なし
* @return bool True:先頭である/False:先頭でない
"""
def isroot(self):
return True if (self.pointer == 0) else False
"""
* 現在のポインタが末尾を指すかどうかを判定する
* @param なし
* @return bool True:末尾である/False:末尾でない
"""
def istail(self):
return True if (self.pointer >= len(self.item)) else False
"""
* 現在のポインタが指す要素が存在するかどうかを判定する
* @param なし
* @return bool True:存在する/False:存在しない
"""
def exist(self):
i = self.pointer;
return True if ((i >= 0) and (self.item[i] != None)) else False
"""
* 現在のポインタが指す要素を1つ取り出す
* @param なし
* @return object 取り出した要素/NULL:要素がない
"""
def get(self):
i = self.pointer;
return self.item[i] if self.exist() else None
"""
* リストの先頭にポインタをセットする
* @param なし
* @return int 先頭のインデックス
"""
def moveRoot(self):
self.pointer = 0
return 0
"""
* リストの末尾にポインタをセットする
* @param なし
* @return int 末尾のインデックス
"""
def moveTail(self):
self.pointer = len(self.item) - 1
return self.pointer
"""
* 任意のインデックスをポインタにセットする
* @param int i インデックス
* @return int セットしたインデックス/None:対応する要素がない
"""
def setPointer(self, i):
if (self.item[i] == None):
res = None
else:
self.pointer = i
res = i
return res
"""
* 次の要素のインデックスを返し、ポインタを進める
* @param なし
* @return int 前の要素のインデックス/None:次はない
"""
def moveNext(self):
if (self.istail()): #リストの末尾
res = None
elif (not self.exist()): #要素がない
res = None
else:
self.pointer += 1
res = self.pointer
return res
"""
* リストの末尾に要素を1つ追加する
* @param mixed data 追加する要素
* @return int 追加したデータのインデックス
"""
def append(self, data):
self.item.append(data)
self.pointer = len(self.item) - 1
return self.pointer
"""
* 現在のポインタ位置(ポインタが示す要素の前)に要素を1つ挿入する
* @param mixed data 挿入する要素
* @return int 挿入した要素のインデックス
"""
def insert(self, data):
self.insert(self.pointer, data)
return self.pointer
"""
* 現在のポインタが指す要素を1つ削除する
* @param なし
* @return int 削除した要素のインデックス
"""
def delete(self):
i = self.pointer
if (self.item[i] != None):
self.item.pop(i)
else:
i = None
return i
"""
* 親ノードがあるかどうかを判定する
* @param なし
* @return bool TRUE:親ノードがある/FALSE:親ノードがない
"""
def isparent():
return False if (self.parent == None) else True
"""
* 現在のポインタが子ノードを示すかどうか判定する
* @param なし
* @return bool True:子ノードを示す/False:子ノードを示さない
"""
def ischild():
return True if (isinstance(self.get(), list)) else False
"""
* ツリーの末尾に子ノードを1つ追加する
* @param なし
* @return pahooTree 追加した子ノード
"""
def appendChild(self):
child = pahooTree(self, self.pointer)
pointer = self.append(child)
child.parentPTR = pointer
return child
"""
* 現在のポインタ位置(ポインタが示す要素の前)に子ノードを1つ挿入する
* @param なし
* @return pahooTree 挿入した子ノード
"""
def insertChild(self):
child = pahooTree(self, self.pointer)
self.insert(child)
return child
"""
* 現在のポインタ位置(ポインタが示す要素の前)の子ノードを削除する
* @param なし
* @return int 削除した要素のインデックス/False:子ノードではない
"""
def deleteChild(self):
res = False;
child = self.get()
if (isinstance(self.get(), pahooTree)):
res = self.delete()
child = None
return res
"""
* 現在のポインタ位置(ポインタが示す要素の前)に子ノードがあれば移動する
* @param なし
* @return pahooTree 子ノード/None:子ノードではない
"""
def moveChild(self):
res = None
child = self.get()
if (isinstance(self.get(), pahooTree)):
child.moveRoot()
res = child
return res
"""
* 親ノードがあれば移動する
* @param なし
* @return pahooTree 親ノード/NULL:親ノードがない
"""
def moveParent(self):
res = None
if (self.parentOBJ != None):
self.parentOBJ.pointer = self.parentPTR
res = self.parentOBJ
return res
"""
* ツリーの内容を成形して返す(リスト型)
* @param なし
* @return string ツリーの内容
"""
def list(self):
outstr = "[ "
self.moveRoot() #ツリーの先頭へ
while (not self.istail()): #ツリー末尾まで繰り返し
if (not self.isroot()):
outstr += ", "
data = self.get()
#子ノードの場合
if (isinstance(data, pahooTree)):
outstr += data.list()
else:
outstr += str(data)
self.moveNext() #次の要素へ
return outstr + ' ]'
"""
* ツリーの内容を成形して返す(階層型)
* @param int depth 階層の深さ
* @return string ツリーの内容
"""
def tree(self, depth=0):
if (depth == 0):
outstr = ''
else:
outstr = ' ' * depth
outstr += "|\n"
self.moveRoot() #ツリーの先頭へ
while (not self.istail()): #ツリー末尾まで繰り返し
data = self.get()
#子ノードの場合
if (isinstance(data, pahooTree)):
outstr += data.tree(depth + 1)
else:
outstr += ' ' * depth
outstr += '+ ' + str(data) + "\n"
サンプル・プログラム
import sys
#データ構造クラス
import pahooDataStructure
"""
* 検索キーを含むノードを探す
* @param string key 検索キー
* @param pahooTree tree 探索対象ノード
* @return pahooTree 検索キーが存在するノード
"""
def searchItem(key, tree):
res = None
tree.moveRoot()
while (not tree.istail()):
data = tree.get()
if (isinstance(tree.get(), pahooDataStructure.pahooTree)):
res = searchItem(key, data)
if (res != None):
return(res)
tree.moveNext()
elif (data == key):
return(tree)
else:
tree.moveNext()
return(res)
# メイン・プログラム ======================================================
tree = pahooDataStructure.pahooTree() #ツリーを用意
key = '3-B' #検索キー
tree.append('1-A') #第1階層に要素を追加
tree.append('1-B')
tree.append('1-C')
child1 = tree.appendChild() #子ノード(第2階層)を追加
child1.append('2-A') #第2階層に要素を追加
child1.append('2-B')
child2 = child1.appendChild() #子ノード(第3階層)を追加
child2.append('3-A') #第3階層に要素を追加
child2.append('3-B')
child2.moveParent() #親ノード(第2階層)に戻る
child1.append('2-C')
child1.moveParent()
tree.append('1-D')
outstr = tree.tree() #現在のツリーを表示
sys.stdout.write("\nツリー\n{}\n".format(outstr))
node = searchItem(key, tree) #検索キーを含むノードを削除
if (node != None):
parent = node.moveParent()
parent.deleteChild()
else:
outstr = 'No hit'
outstr = tree.tree() #現在のツリーを表示
sys.stdout.write("\n削除後\n{}\n".format(outstr))
Pythonで XMLデータをツリーへ代入
実行結果はPHPとほぼ同じだが、PythonではXMLを読み込むために xml.etree.ElementTree クラスを用いている。
import sys
import requests
import xml.etree.ElementTree
#データ構造クラス
import pahooDataStructure
"""
* XMLの内容をツリーに代入(再帰呼び出し)
* @param documentElement element XML要素
* @param pahooTree tree 探索対象ノード
* @return なし
"""
def xml2tree(element, tree):
#要素追加
ss = element.tag + ':' + str(element.text).replace("\n", '')
tree.append(ss)
#子ノード
cnt = 0
for sub in element:
if (cnt == 0):
child = tree.appendChild()
cnt += 1
xml2tree(sub, child)
# メイン・プログラム ======================================================
# 東京の天気 - livedoor天気情報
url = 'http://weather.livedoor.com/forecast/rss/area/130010.xml';
req = requests.get(url, stream=True)
req.raw.decode_content = True
#xml = minidom.parse(req.raw)
xml = xml.etree.ElementTree.fromstring(req.text)
if (xml == None):
sys.stdout.write("error: load -- {}".format(url))
sys.exit()
#ツリーに代入
tree = pahooDataStructure.pahooTree()
for sub in xml.iter(xml.tag):
xml2tree(sub, tree)
#ツリーを表示
outstr = tree.tree()
print(outstr)
PHPはツリーを備えていないが、ここではツリー構造を扱えるユーザー・クラス pahooTree を用意した。XMLデータをツリーに読み込むサンプル・プログラムを紹介する。