PHPで二分探索木やってみた

二分木構造で二分探索を行う。
多分こんな感じ。
削除が面倒臭いなぁ。
　

ソース

<?php
class BinaryNode
{
	public $data;
	public $left;
	public $right;

	public function __construct($data)
	{
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}


class BinaryTree
{
	private $_root;

	// コンストラクタ
	public function __construct()
	{
		$this->_root = null;
	}

	// 要素を追加
	public function add($data)
	{
		$node = new BinaryNode($data);

		$p =& $this->_root;
		while ($p) {
			// 同じデータが登録済み
			if ($p->data==$data) {
				return false;
			// 左へ進む
			} else if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}

		$p = $node;
		return true;
	}

	// 要素を削除
	public function delete($data)
	{
		$p =& $this->_root;
		while ($p) {
			// 発見
			if ($p->data==$data) {
				// 左右両方あり
				if ($p->left && $p->right) {
					$p2 =& $p->right;
					while ($p2->left) {
						$p2 =& $p2->left;
					}
					$p2->left = $p->left;
					$p = $p->right;
				// 左あり
				} else if ($p->left) {
					$p = $p->left;
				// 右あり
				} else if ($p->right) {
					$p = $p->right;
				} else {
					$p = null;
				}
				return true;
			}

			// 左へ進む
			if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}
		return false;
	}

	// 要素を検索
	public function search($data)
	{
		$p =& $this->_root;
		while ($p) {
			// 発見
			if ($p->data==$data) {
				return $p;
			// 左へ進む
			} else if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}
		return null;
	}

	// 要素を配列で取得
	public function traverse(BinaryNode $p=null)
	{
		if (!$p) {
			$p = $this->_root;
		}
		$result = array();
		if ($p) {
			if ($p->left) {
				$result = array_merge($result, $this->traverse($p->left));
			}
			$result[] = $p->data;
			if ($p->right) {
				$result = array_merge($result, $this->traverse($p->right));
			}
		}
		return $result;
	}
}

参考URL

アルゴリズムとデータ構造編　第１７章　二分探索木
http://www.geocities.jp/ky_webid/algorithm/017.html
　
データ構造：二分探索木［１］ ― 初期設定、追加、検索
http://tdweb.cssa.chs.nihon-u.ac.jp/ds/ds07.html
　
データ構造：二分探索木［２］ ― トラバーサル
http://tdweb.cssa.chs.nihon-u.ac.jp/ds/ds08.html
　
データ構造：二分探索木［３］ ― データ要素の削除
http://tdweb.cssa.chs.nihon-u.ac.jp/ds/ds09.html