谈PHP的二叉树的表示

jmton

　　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++中的二叉树是一样的了。