ツリー構造

階層構造をもったデータ集合に
ファイルを格納するためのディレクトリのような階層構造をしているデータ集合に対しては、ツリーを用いる。
PHPはツリーを備えていないが、ここではツリー構造を扱えるユーザー・クラス pahooTree を用意した。XMLデータをツリーに読み込むサンプル・プログラムを紹介する。

サンプル・プログラム

ツリー構造

ツリー
ツリーは上図のように、階層があるデータ構造で、木(tree)を上下反転させたように見えることからこの名で呼んでいる。

ファイルを格納するためのディレクトリ構造や、後述するXMLなどがツリー構造の代表例である。
ツリーとリスト
ツリーリストを拡張することで表現可能だ。リストにぶら下がるデータ実体に、ツリーそのものを入れてしまえばよい。これを表したのが上図である。
以前に作ったPHPリスト・クラス pahooList は、データ実体としてオブジェクトを代入できるから、これを継承してPHPツリー・クラス pahooTree を作成することにする。

PHPによるツリー

クラスは外部ファイル "pahooDataStructure.php" に分離している。
ツリーでは、リストで実装したメソッドに加え、下の階層(子ノード)を追加したり削除するメソッドが必要になる。
PHPによる appendChild のイメージ
appendChild - PHPによるツリー
あるノードの最後に子ノードを追加するメソッドを appendChild とすると、それは上図のような構造になる。

あらたに pahooTree のインスタンスを生成し、それを pahooListappend メソッドを使って追加してやればいい。
ただし、あとで子ノードを探索したり削除することを考えると、双方向リストと同じ考え方で、子ノードから親ノードへのリンク情報が必要だ。これは、ディレクトリで言うところの ".." と同じである。
そこで、クラス 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によるツリー
PHPプログラム "dt03-41-01.php" は、ツリーへの要素追加、子ノードの追加、要素の探索と子ノードの削除を行うサンプル・プログラムである。

実行結果は左図の通り。

PHPで XMLデータをツリーへ代入

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);

PHPプログラム "dt03-41-02.php" は、ネット上のXMLファイルをツリーへ代入し、その内容を表示するサンプル・プログラムである。

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

実行結果は下図の通り。
XMLをツリーへ代入

Pythonによるツリー

Pythonでツリー構造を扱うためのクラスが pahooTree である。PHPのツリー・クラスを移植した。クラスは外部ファイル "pahooDataStructure.py" に分離している。PHPと同じメソッドを用意した。
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"

サンプル・プログラム

PHPのサンプル・プログラム "dt03-41-01.php" をPythonへ移植したものが "dt03-41-11.py" である。実行結果はPHPと同じになる。
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プログラム "dt03-41-02.php" Pythonへ移植したものが "dt03-41-12.py" である。
実行結果は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)
(この項おわり)
header