谈PHP的二叉树的表示
PHP已经发行到了5.2.10了，5.3.0rc4也已公布。6.0早就出了测试版。PHP是日趋完美。呵呵但是在C++/C中有个重要的概念就是链表。而链表中有个重要概念就是二叉树。实现二叉树关键是一个节点如何表示。
我们知道C++/C中可以使用以下代码表示一个二叉树的节点(使用模板):
template <class elemType>
struct nodeType
{
elemType info;
nodeType<elemType> *llink;
nodeType<elemType> *rlink;
}
如果只是C++语法可以使用类表示.
template <class elemType>
class nodeType
{
public:
elemType info;
nodeType<elemType> *llink;
nodeType<elemType> *rlink;
.........................
}
而PHP应该如何表示呢？PHP里是没有指针的，但有引用。而引用的效果其实与指针是差不多的。
当然PHP也没有struct，因此节点可以使用类来代替。
我们可以构造一个如下类:
class nodeType
{
var $key;
var $left, $right;
function nodeType($key, $left = null, $right = null)
{
$this->key = $key;
$this->left = &$left;
$this->right = &$right;
}
}
用更标准点的类表示。（注意：比较早的PHP就不支持了）
class nodeType
{
public $key;
public $left, $right;
public function nodeType($key, $left = null, $right = null)
{
$this->key = $key;
$this->left = &$left;
$this->right = &$right;
}
}
这里只是简单介绍二叉树的节点方法，就不具体实现二叉树了。相信对于有C++/C或java写过二叉树经验或参考C++/C或java二叉树代码应该实现起来很简单。
以上代码是否可以真的实现二叉树呢？我就简单的使用以下代码验证一下。
// 构建一个根，和左右子树
$leftNode = new nodeType(1);
$rightNode = new nodeType(10);
$rootNode = new nodeType(null, &$leftNode, &$rightNode); // 注意此处要传入引用
echo ++$rootNode->right->key;
echo '<br>';
echo $rightNode->key;
输出
11
11
// 在左子树再下添加一个节点
$leftLeftNode = new nodeType(12);
$rootNode->left->left = &$leftLeftNode; // 注意引用
echo $rootNode->left->key;
echo '<br>';
echo ++$rootNode->left->left->key;
echo '<br>';
echo $leftLeftNode->key;
输出
1
13
13
// 删除一个节点，直接赋值为null
$rootNode->left->left = null;
echo $rootNode->left->key;
echo '<br>';
echo $rootNode->left->left->key;
echo '<br>';
echo $leftLeftNode->key;
echo '<br>';
echo '*';
输出
1
*
由于PHP没有指针，不用担心所谓“野指针”，比较安全。其实在java也是使用这种方法实现链表的。
看以上结果，二叉树是有效的。具体实现一个二叉树还需要读者去实现了，这里就不讲了。可以参考C++书本里的二叉树实现。
网上还有一些其他的方法，但我觉得该方法比较好，基本上和C++中的二叉树是一样的了。
页:
[1]