PHP クラス&オブジェクト -- PHP を解析してバイナリ ツリーを実装する_PHP チュートリアル

バイナリ ツリーとそのバリアントは、データ構造ファミリーの重要な部分です。リンク リストの一種であるバイナリ ツリーは、特定の順序で迅速に整理して取得する必要があるデータの処理に最適です。

コードをコピーします コードは次のとおりです:

// バイナリツリーを実装するクラスを定義します
class Binary_Tree_Node {
// データを保持する変数を定義します:
public $data;
// そして、左と右のオブジェクトを保持する変数:
public $left;
public $right;

// データを渡すことができるコンストラクター メソッド
public function __construct($d = NULL) {
$this->data = $d;
}

// 事前順序でツリーを左から右に走査し、配列を返します
// 事前順序とは、各ノードの値がその子よりも前にあることを意味します。
public function traversePreorder() {
// いくつかの変数を準備します。
$l = array();
$r = array();
// 適切にトラバースされた左右の子を読み取ります:
if ($this->left) { $l = $this->left->traversePreorder (); }
if ($this->right) { $r = $this->right->traversePreorder(); }

// 現在の値の左と右のマージされた配列を返します:
return array_merge(array($this->data), $l, $r);
}
// ポストオーダーで左から右にツリーをトラバースし、配列を返します
// ポストオーダーとは、各ノードの値がその子に従うことを意味します。
public function traversePostorder() {
// いくつかの変数を準備します。
$l = array();
$r = array();
// 適切にトラバースされた左右の子を読み取ります:
if ($this->left) { $l = $this->left->traversePostorder( ); }
if ($this->right) { $r = $this->right->traversePostorder(); }

// 現在の値の左と右のマージされた配列を返します:
return array_merge($l, $r, array($this->data));
}
// ツリーを左から右に順番に走査し、配列を返します。
// 順番とは、値が左の子、次に
// ノード値、次に右の子の順に並べられることを意味します。
public function traverseInorder() {
// いくつかの変数を準備します。
$l = array();
$r = array();
// 適切にトラバースされた左右の子を読み取ります:
if ($this-> left) { $l = $this->left->traverseInorder(); }
if ($this->right) { $r = $this->right->traverseInorder(); }

// 現在の値の左と右のマージされた配列を返します:
return array_merge($l, array($this->data), $r);
}
}
// 次のようなバイナリ ツリーを作成しましょう: 3
// / /
// h 9
// / /
// ツリーを作成します: 6 a
$tree = new Binary_Tree_Node(3);
$tree->left = 新しい Binary_Tree_Node('h');
$tree->right = 新しい Binary_Tree_Node(9);
$tree->right->left = 新しい Binary_Tree_Node(6);
$tree ->right->right = new Binary_Tree_Node('a');
// 次に、このツリーをすべての可能な順序で走査し、結果を表示します:
// 事前順序: 3、h、9、6、a
echo '

', implode(', ', $tree->traversePreorder()), '

';
// ポストオーダー: h, 9, 6, a, 3
echo '

', implode(', ', $tree->traversePostorder()), '

';
// 順番: h, 3, 6, 9, a
echo '

', implode(', ', $tree->traverseInorder()), '

';
?>

http://www.bkjia.com/PHPjc/327865.htmlwww.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/327865.html技術記事フォークおよびその変形は、データ構造の重要な構成部分です。