サンプル・プログラム
ツリー構造
ファイルを格納するためのディレクトリ構造や、後述するXMLなどがツリー構造の代表例である。
PHPによるツリー
ツリーでは、リストで実装したメソッドに加え、下の階層（子ノード）を追加したり削除するメソッドが必要になる。
あらたに pahooTree のインスタンスを生成し、それを pahooList の append メソッドを使って追加してやればいい。
ただし、あとで子ノードを探索したり削除することを考えると、双方向リストと同じ考え方で、子ノードから親ノードへのリンク情報が必要だ。これは、ディレクトリで言うところの ".." と同じである。
そこで、クラス pahooTree のクラス変数として、子ノードを生成したら、$parentOBJ に親ノードのインスタンスそのものを、$parentPTR に親ノードのポインタ位置を記録しておくようにする。
クラス pahooTree では pahooList のメソッドに加え、次のメソッドを用意した。
| メソッド | 機能 |
|---|---|
| appendChild() | ノードの末尾に子ノードを追加する。初期の子ノードは空である。 |
| isparent() | 親ノードがあるかどうか判定する。 |
| ischild() | 現在のポインタが子ノードを示すかどうか判定する。 |
| appendChild() | 現在のポインタノードの末尾に子ノードを追加する。初期の子ノードは空である。 |
| insertChild() | 現在のポインタ位置（ポインタが示す要素の前）に子ノードを1つ挿入する。初期の子ノードは空である。 |
| deleteChild() | 現在のポインタが指す子ノードを1つ削除する。ノードでなければ何もしない。 |
| moveChild() | 現在のポインタ位置に子ノードがあれば移動する。ノードでなければ何もしない。 |
| moveParent() | 親ノードがあれば移動する。ポインタは子ノードを呼んでいる位置へ進める。 |
| list() | ツリーの内容を成形して返す（リスト型）。 |
| tree() | ツリーの内容を成形して返す（階層型）。 |
1187: // pahooTreeクラス ==========================================================
1188: class pahooTree extends pahooList {
1189: public $parentOBJ; //親ノードのオブジェクト
1190: public $parentPTR; //親ノードのポインタ
1191:
1192: /**
1193: * コンストラクタ
1194: * @param pahooTree $paret 親ノード／NULL：自らが親ノード
1195: * @returnなし
1196: */
1197: function __construct($obj=NULL, $pointer=self::ANCHOR) {
1198: parent::__construct();
1199: $this->parentOBJ = $obj;
1200: $this->parentPTR = $pointer;
1201: }
1202:
1203: /**
1204: * 親ノードがあるかどうかを判定する
1205: * @paramなし
1206: * @return bool TRUE：親ノードがある／FALSE：親ノードがない
1207: */
1208: function isparent() {
1209: return ($this->parent == NULL) ? FALSE : TRUE;
1210: }
1211:
1212: /**
1213: * 現在のポインタが子ノードを示すかどうか判定する
1214: * @paramなし
1215: * @return bool TRUE：子ノードを示す／FALSE：子ノードを示さない
1216: */
1217: function ischild() {
1218: return ($this->get() instanceof pahooTree);
1219: }
1220:
1221: /**
1222: * ツリーの末尾に子ノードを1つ追加する
1223: * @paramなし
1224: * @return pahooTree 追加した子ノード
1225: */
1226: function appendChild() {
1227: $child = new pahooTree($this, $this->pointer);
1228: $pointer = $this->append($child);
1229: $child->parentPTR = $pointer;
1230:
1231: return $child;
1232: }
1233:
1234: /**
1235: * 現在のポインタ位置（ポインタが示す要素の前）に子ノードを1つ挿入する
1236: * @paramなし
1237: * @return pahooTree挿入した子ノード
1238: */
1239: function insertChild() {
1240: $child = new pahooTree($this, $this->pointer);
1241: $this->insert($child);
1242: return $child;
1243: }
1244:
1245: /**
1246: * 現在のポインタ位置（ポインタが示す要素の前）の子ノードを削除する
1247: * @paramなし
1248: * @return int削除した要素のインデックス／FALSE：子ノードではない
1249: */
1250: function deleteChild() {
1251: $res = FALSE;
1252: $child = $this->get();
1253: if ($child instanceof pahooTree) {
1254: $res = $this->delete();
1255: $child = NULL;
1256: }
1257: return $res;
1258: }
1259:
1260: /**
1261: * 現在のポインタ位置（ポインタが示す要素の前）に子ノードがあれば移動する
1262: * @paramなし
1263: * @return pahooTree子ノード／NULL：子ノードではない
1264: */
1265: function moveChild() {
1266: $res = NULL;
1267: $child = $this->get();
1268: if ($child instanceof pahooTree) {
1269: $child->moveRoot();
1270: $res = $child;
1271: }
1272: return $res;
1273: }
1274:
1275: /**
1276: * 親ノードがあれば移動する
1277: * @paramなし
1278: * @return pahooTree 親ノード／NULL:親ノードがない
1279: */
1280: function moveParent() {
1281: $res = NULL;
1282: if ($this->parentOBJ != NULL) {
1283: $this->parentOBJ->pointer = $this->parentPTR;
1284: $res = $this->parentOBJ;
1285: }
1286: return $res;
1287: }
1288:
1289: /**
1290: * ツリーの内容を成形して返す（リスト型）
1291: * @paramなし
1292: * @return stringツリーの内容
1293: */
1294: function list() {
1295: $outstr = '[ ';
1296: $this->moveRoot(); //ツリーの先頭へ
1297: while (! $this->istail()) { //ツリー末尾まで繰り返し
1298: if (! $this->isroot()) $outstr .= ', ';
1299: $data = $this->get();
1300: //子ノードの場合
1301: if ($data instanceof pahooTree) {
1302: $outstr .= $data->list();
1303: } else {
1304: $outstr .= print_r($data, TRUE);
1305: }
1306: $this->moveNext(); //次の要素へ
1307: }
1308: return $outstr .' ]';
1309: }
1310:
1311: /**
1312: * ツリーの内容を成形して返す（階層型）
1313: * @param int $depth 階層の深さ
1314: * @return stringツリーの内容
1315: */
1316: function tree($depth=0) {
1317: if ($depth == 0) {
1318: $outstr = '';
1319: } else {
1320: $outstr = str_repeat(' ', $depth);
1321: $outstr .= "|\n";
1322: }
1323: $this->moveRoot(); //ツリーの先頭へ
1324: while (! $this->istail()) { //ツリー末尾まで繰り返し
1325: $data = $this->get();
1326: //子ノードの場合
1327: if ($data instanceof pahooTree) {
1328: $outstr .= $data->tree($depth + 1);
1329: } else {
1330: $outstr .= str_repeat(' ', $depth);
1331: $outstr .= '+ ' . print_r($data, TRUE) . "\n";
1332: }
1333: $this->moveNext(); //次の要素へ
1334: }
1335: return $outstr;
1336: }
1337:
1338: // End of Class
1339: }
サンプル・プログラム
0011: //データ構造クラス
0012: require_once('pahooDataStructure.php');
0013:
0014: /**
0015: * 検索キーを含むノードを探す
0016: * @param string $key検索キー
0017: * @param pahooTree $tree探索対象ノード
0018: * @return pahooTree検索キーが存在するノード
0019: */
0020: function searchItem($key, $tree) {
0021: $res = NULL;
0022: $tree->moveRoot();
0023: while (! $tree->istail()) {
0024: $data = $tree->get();
0025: if ($data instanceof pahooTree) {
0026: $res = searchItem($key, $data);
0027: if ($res != NULL) return $res;
0028: $tree->moveNext();
0029: } else if ($data == $key) {
0030: return $tree;
0031: } else {
0032: $tree->moveNext();
0033: }
0034: }
0035: return $res;
0036: }
0037:
0038: // メイン・プログラム ======================================================
0039: $tree = new pahooTree(); //ツリーを用意
0040: $key = '3-B'; //検索キー
0041:
0042: $tree->append('1-A'); //第1階層に要素を追加
0043: $tree->append('1-B');
0044: $tree->append('1-C');
0045: $child1 = $tree->appendChild(); //子ノード(第2階層)を追加
0046: $child1->append('2-A'); //第2階層に要素を追加
0047: $child1->append('2-B');
0048: $child2 = $child1->appendChild(); //子ノード(第3階層)を追加
0049: $child2->append('3-A'); //第3階層に要素を追加
0050: $child2->append('3-B');
0051: $child2->moveParent(); //親ノード(第2階層)に戻る
0052: $child1->append('2-C');
0053: $child1->moveParent();
0054: $tree->append('1-D');
0055:
0056: $outstr = $tree->tree(); //現在のツリーを表示
0057: printf("\nツリー\n%s\n", $outstr);
0058:
0059: $node = searchItem($key, $tree); //検索キーを含むノードを削除
0060: if ($node != NULL) {
0061: $parent = $node->moveParent();
0062: $parent->deleteChild();
0063: } else {
0064: $outstr = 'No hit';
0065: }
0066: $outstr = $tree->tree(); //現在のツリーを表示
0067: printf("\n削除後\n%s", $outstr);
実行結果は左図の通り。
PHPで XMLデータをツリーへ代入
ここでは、「PHPで天気予報を求める（その2）」で利用したWebAPIの出力XMLをツリーに読み込み、表示するPHPプログラムを作ってみることにする。
0011: //データ構造クラス
0012: require_once('pahooDataStructure.php');
0013:
0014: /**
0015: * XMLの内容をツリーに代入（再帰呼び出し）
0016: * @param SimpleXmlIterator $xml XMLデータ
0017: * @param pahooTree $tree探索対象ノード
0018: * @returnなし
0019: */
0020: function xml2tree($xml, $tree) {
0021: $xml->rewind();
0022: while ($xml->valid()) {
0023: //子ノード
0024: if ($xml->hasChildren()) {
0025: $child = $tree->appendChild();
0026: xml2tree($xml->getChildren(), $child);
0027: //要素
0028: } else {
0029: $str = $xml->key() . ':' . (string)$xml->current();
0030: $tree->append($str);
0031: }
0032: $xml->next();
0033: }
0034: }
0035:
0036: // メイン・プログラム ======================================================
0037: //東京の天気 - livedoor天気情報
0038: $url = 'https://weather.livedoor.com/forecast/rss/area/130010.xml';
0039: $xml = new SimpleXmlIterator($url, 0, TRUE);
0040: if ($xml == FALSE) {
0041: print 'error: load -- ' . $url;
0042: exit(1);
0043: }
0044:
0045: //ツリーに代入
0046: $tree = new pahooTree();
0047: xml2tree($xml, $tree);
0048:
0049: //ツリーを表示
0050: $outstr = $tree->tree();
0051: printf("\n%s", $outstr);
XMLの読み込みには、PHP5で導入された SimpleXMLIterator クラスを利用する。
SimpleXMLIteratorクラス自体がツリー構造で成り立っているので、pahooTree への代入は、簡単なユーザー関数 xml2tree を書けば実装できる。子ノードが現れたら自身を呼び出す再帰関数となっている。
実行結果は下図の通り。
Pythonによるツリー
PHPの場合と異なり、ユーザークラス pahooList を継承しているわけではないので、リスト関係で必要なメソッドも追加している。
0011:
0012: # pahooTreeクラス ==========================================================
0013: class pahooTree: #ツリー構造
0014: """
0015: * コンストラクタ
0016: * @param mixed item 格納する要素
0017: * @param pahooTree paret 親ノード／None：自らが親ノード
0018: * @param pahooTree left 親ノードの左ならTrue、右ならFalse
0019: * @returnなし
0020: """
0021: def __init__(self, obj=None, pointer=None):
0022: self.item = list() #要素を格納するリスト
0023: self.pointer = 0 #ポインタ
0024: self.parentOBJ = obj #親ノードのオブジェクト
0025: self.parentPTR = pointer #親ノードのポインタ
0026: self.error = False #エラーフラグ
0027: self.errmsg = '' #エラーメッセージ
0028:
0029: """
0030: * 現在のポインタが先頭を指すかどうかを判定する
0031: * @paramなし
0032: * @return bool True：先頭である／False：先頭でない
0033: """
0034: def isroot(self):
0035: return True if (self.pointer == 0) else False
0036:
0037: """
0038: * 現在のポインタが末尾を指すかどうかを判定する
0039: * @paramなし
0040: * @return bool True：末尾である／False：末尾でない
0041: """
0042: def istail(self):
0043: return True if (self.pointer >= len(self.item)) else False
0044:
0045: """
0046: * 現在のポインタが指す要素が存在するかどうかを判定する
0047: * @paramなし
0048: * @return bool True：存在する／False：存在しない
0049: """
0050: def exist(self):
0051: i = self.pointer;
0052: return True if ((i >= 0) and (self.item[i] != None)) else False
0053:
0054: """
0055: * 現在のポインタが指す要素を1つ取り出す
0056: * @paramなし
0057: * @return object取り出した要素／NULL：要素がない
0058: """
0059: def get(self):
0060: i = self.pointer;
0061: return self.item[i] if self.exist() else None
0062:
0063: """
0064: * リストの先頭にポインタをセットする
0065: * @paramなし
0066: * @return int先頭のインデックス
0067: """
0068: def moveRoot(self):
0069: self.pointer = 0
0070: return 0
0071:
0072: """
0073: * リストの末尾にポインタをセットする
0074: * @paramなし
0075: * @return int末尾のインデックス
0076: """
0077: def moveTail(self):
0078: self.pointer = len(self.item) - 1
0079: return self.pointer
0080:
0081: """
0082: * 任意のインデックスをポインタにセットする
0083: * @param int i インデックス
0084: * @return intセットしたインデックス／None：対応する要素がない
0085: """
0086: def setPointer(self, i):
0087: if (self.item[i] == None):
0088: res = None
0089: else:
0090: self.pointer = i
0091: res = i
0092: return res
0093:
0094: """
0095: * 次の要素のインデックスを返し、ポインタを進める
0096: * @paramなし
0097: * @return int前の要素のインデックス／None：次はない
0098: """
0099: def moveNext(self):
0100: if (self.istail()): #リストの末尾
0101: res = None
0102: elif (not self.exist()): #要素がない
0103: res = None
0104: else:
0105: self.pointer += 1
0106: res = self.pointer
0107: return res
0108:
0109: """
0110: * リストの末尾に要素を1つ追加する
0111: * @param mixed data 追加する要素
0112: * @return int 追加したデータのインデックス
0113: """
0114: def append(self, data):
0115: self.item.append(data)
0116: self.pointer = len(self.item) - 1
0117: return self.pointer
0118:
0119: """
0120: * 現在のポインタ位置（ポインタが示す要素の前）に要素を1つ挿入する
0121: * @param mixed data挿入する要素
0122: * @return int挿入した要素のインデックス
0123: """
0124: def insert(self, data):
0125: self.insert(self.pointer, data)
0126: return self.pointer
0127:
0128: """
0129: * 現在のポインタが指す要素を1つ削除する
0130: * @paramなし
0131: * @return int削除した要素のインデックス
0132: """
0133: def delete(self):
0134: i = self.pointer
0135: if (self.item[i] != None):
0136: self.item.pop(i)
0137: else:
0138: i = None
0139: return i
0140:
0141: """
0142: * 親ノードがあるかどうかを判定する
0143: * @paramなし
0144: * @return bool TRUE：親ノードがある／FALSE：親ノードがない
0145: """
0146: def isparent():
0147: return False if (self.parent == None) else True
0148:
0149: """
0150: * 現在のポインタが子ノードを示すかどうか判定する
0151: * @paramなし
0152: * @return bool True：子ノードを示す／False：子ノードを示さない
0153: """
0154: def ischild():
0155: return True if (isinstance(self.get(), list)) else False
0156:
0157: """
0158: * ツリーの末尾に子ノードを1つ追加する
0159: * @paramなし
0160: * @return pahooTree 追加した子ノード
0161: """
0162: def appendChild(self):
0163: child = pahooTree(self, self.pointer)
0164: pointer = self.append(child)
0165: child.parentPTR = pointer
0166: return child
0167:
0168: """
0169: * 現在のポインタ位置（ポインタが示す要素の前）に子ノードを1つ挿入する
0170: * @paramなし
0171: * @return pahooTree挿入した子ノード
0172: """
0173: def insertChild(self):
0174: child = pahooTree(self, self.pointer)
0175: self.insert(child)
0176: return child
0177:
0178: """
0179: * 現在のポインタ位置（ポインタが示す要素の前）の子ノードを削除する
0180: * @paramなし
0181: * @return int削除した要素のインデックス／False：子ノードではない
0182: """
0183: def deleteChild(self):
0184: res = False;
0185: child = self.get()
0186: if (isinstance(self.get(), pahooTree)):
0187: res = self.delete()
0188: child = None
0189: return res
0190:
0191: """
0192: * 現在のポインタ位置（ポインタが示す要素の前）に子ノードがあれば移動する
0193: * @paramなし
0194: * @return pahooTree子ノード／None：子ノードではない
0195: """
0196: def moveChild(self):
0197: res = None
0198: child = self.get()
0199: if (isinstance(self.get(), pahooTree)):
0200: child.moveRoot()
0201: res = child
0202: return res
0203:
0204: """
0205: * 親ノードがあれば移動する
0206: * @paramなし
0207: * @return pahooTree 親ノード／NULL:親ノードがない
0208: """
0209: def moveParent(self):
0210: res = None
0211: if (self.parentOBJ != None):
0212: self.parentOBJ.pointer = self.parentPTR
0213: res = self.parentOBJ
0214: return res
0215:
0216: """
0217: * ツリーの内容を成形して返す（リスト型）
0218: * @paramなし
0219: * @return stringツリーの内容
0220: """
0221: def list(self):
0222: outstr = "[ "
0223: self.moveRoot() #ツリーの先頭へ
0224: while (not self.istail()): #ツリー末尾まで繰り返し
0225: if (not self.isroot()):
0226: outstr += ", "
0227: data = self.get()
0228: #子ノードの場合
0229: if (isinstance(data, pahooTree)):
0230: outstr += data.list()
0231: else:
0232: outstr += str(data)
0233: self.moveNext() #次の要素へ
0234: return outstr + ' ]'
0235:
0236: """
0237: * ツリーの内容を成形して返す（階層型）
0238: * @param int depth 階層の深さ
0239: * @return stringツリーの内容
0240: """
0241: def tree(self, depth=0):
0242: if (depth == 0):
0243: outstr = ''
0244: else:
0245: outstr = ' ' * depth
0246: outstr += "|\n"
0247: self.moveRoot() #ツリーの先頭へ
0248: while (not self.istail()): #ツリー末尾まで繰り返し
0249: data = self.get()
0250: #子ノードの場合
0251: if (isinstance(data, pahooTree)):
0252: outstr += data.tree(depth + 1)
0253: else:
0254: outstr += ' ' * depth
0255: outstr += '+ ' + str(data) + "\n"
サンプル・プログラム
0010: import sys
0011:
0012: #データ構造クラス
0013: import pahooDataStructure
0014:
0015: """
0016: * 検索キーを含むノードを探す
0017: * @param string key検索キー
0018: * @param pahooTree tree探索対象ノード
0019: * @return pahooTree検索キーが存在するノード
0020: """
0021: def searchItem(key, tree):
0022: res = None
0023: tree.moveRoot()
0024: while (not tree.istail()):
0025: data = tree.get()
0026: if (isinstance(tree.get(), pahooDataStructure.pahooTree)):
0027: res = searchItem(key, data)
0028: if (res != None):
0029: return(res)
0030: tree.moveNext()
0031: elif (data == key):
0032: return(tree)
0033: else:
0034: tree.moveNext()
0035:
0036: return(res)
0037:
0038: # メイン・プログラム ======================================================
0039: tree = pahooDataStructure.pahooTree() #ツリーを用意
0040: key = '3-B' #検索キー
0041:
0042: tree.append('1-A') #第1階層に要素を追加
0043: tree.append('1-B')
0044: tree.append('1-C')
0045: child1 = tree.appendChild() #子ノード(第2階層)を追加
0046: child1.append('2-A') #第2階層に要素を追加
0047: child1.append('2-B')
0048: child2 = child1.appendChild() #子ノード(第3階層)を追加
0049: child2.append('3-A') #第3階層に要素を追加
0050: child2.append('3-B')
0051: child2.moveParent() #親ノード(第2階層)に戻る
0052: child1.append('2-C')
0053: child1.moveParent()
0054: tree.append('1-D')
0055:
0056: outstr = tree.tree() #現在のツリーを表示
0057: sys.stdout.write("\nツリー\n{}\n".format(outstr))
0058:
0059: node = searchItem(key, tree) #検索キーを含むノードを削除
0060: if (node != None):
0061: parent = node.moveParent()
0062: parent.deleteChild()
0063: else:
0064: outstr = 'No hit'
0065: outstr = tree.tree() #現在のツリーを表示
0066: sys.stdout.write("\n削除後\n{}\n".format(outstr))
Pythonで XMLデータをツリーへ代入
実行結果はPHPとほぼ同じだが、PythonではXMLを読み込むために xml.etree.ElementTree クラスを用いている。
0010: import sys
0011: import requests
0012: import xml.etree.ElementTree
0013:
0014: #データ構造クラス
0015: import pahooDataStructure
0016:
0017: """
0018: * XMLの内容をツリーに代入（再帰呼び出し）
0019: * @param documentElement element XML要素
0020: * @param pahooTree tree探索対象ノード
0021: * @returnなし
0022: """
0023: def xml2tree(element, tree):
0024: #要素追加
0025: ss = element.tag + ':' + str(element.text).replace("\n", '')
0026: tree.append(ss)
0027: #子ノード
0028: cnt = 0
0029: for sub in element:
0030: if (cnt == 0):
0031: child = tree.appendChild()
0032: cnt += 1
0033: xml2tree(sub, child)
0034:
0035: # メイン・プログラム ======================================================
0036: # 東京の天気 - livedoor天気情報
0037: url = 'https://weather.livedoor.com/forecast/rss/area/130010.xml';
0038: req = requests.get(url, stream=True)
0039: req.raw.decode_content = True
0040: #xml = minidom.parse(req.raw)
0041:
0042: xml = xml.etree.ElementTree.fromstring(req.text)
0043: if (xml == None):
0044: sys.stdout.write("error: load -- {}".format(url))
0045: sys.exit()
0046:
0047: #ツリーに代入
0048: tree = pahooDataStructure.pahooTree()
0049: for sub in xml.iter(xml.tag):
0050: xml2tree(sub, tree)
0051:
0052: #ツリーを表示
0053: outstr = tree.tree()
0054: print(outstr)
PHPはツリーを備えていないが、ここではツリー構造を扱えるユーザー・クラス pahooTree を用意した。XMLデータをツリーに読み込むサンプル・プログラムを紹介する。