PHP二叉树的一些操作练习

很好的一个二叉树参考程序
服务器君一共花费了227.917 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

首先是创建一个树节点类,这个类有两个方法,compare()用于比较节点键值的大小,createNode()用于创建新节点。

// 树节点类
class binaryTreeNode
{
	// 比较节点键值的大小
	function compare($oldkey, $newkey){
		return $newkey - $oldkey;
	}
	// 建立一个新节点
	function createNode($key, $left, $right){
		return array('k'=>$key, 'l'=>$left, 'r'=>$right);
	}
}

然后再创建一个二叉树类。

// 二叉树类
class binaryTree
{
	var $id = 1;   			// 内部UID,自动加1
 	var $nodeCount = 0; 	// 该树节点数,每插入一个加1
 	var $root = null; 		// 树根的引用
 	var $tree = array(); 	// 树结构,中间存贮所有节点
  	var $_nodes = array(); 	// 存贮不同类型的节点,主要是为了引用该类的方法,便于继承,暂时没有用到
   	var $_node = null; 		// 当前节点类的引用
  	// 构造函数,初始化
  	function binaryTree($nodetype = 'binaryTreeNode'){
  		if(!class_exists($nodetype))
          	$nodetype = 'binaryTreeNode';
       	$this->_nodes[$nodetype] = new $nodetype();
      	$this->_node =& $this->_nodes[$nodetype];
	}
  	// 设定节点类型,暂时用处不大,主要为扩展
   	function setNodeType($nodetype = 'binaryTreeNode'){
      	if(!class_exists($nodetype))
          	$nodetype = 'binaryTreeNode';
		$this->_node =& $this->_nodes[$nodetype];
	}
 	// 插入一节点后修改所有相关节点的信息
	// $pnode 为当前根节点,后两个参数为新节点的参数
 	// 即在树中插入一个新节点后,找到此节点所插入的位置并修改其父节点的信息
    // 此函数本为递归,但因为是尾递归(rear-recursive),因此可以改成循环
   	function modifyTree(&$pnode, $key, $id){
    	$p =& $pnode;
      	while(true){
         	$b = $this->_node->compare($p['k'], $key);
            if($b<=0)
			{
           		if($p['l'] != 0)
				{
                	$p =& $this->tree[$p['l']];
               	}
				else
				{
                   	$p['l'] = $id;
                   	break;
               	}
           	}
			else
			{
               	if($p['r'] != 0)
				{
                	$p =& $this->tree[$p['r']];
             	}
				else
				{
                   	$p['r'] = $id;
                  	break;
            	}
			}
		}
	}
	// 重置树信息
	function reset()
	{
     	$this->tree = array();
      	$this->root = null;
      	$this->id = 1;
     	$this->nodeCount = 0;
    	$this->_node = null;
	}
	// 插入一个键为$key的节点,并自动为此节点生成一个唯一ID
	function insertNode($key)
	{
      	$node = $this->_node->createNode($key, 0, 0);
     	$this->tree[$this->id] = $node;
      	if($this->root == null)
		{
           	$this->root =& $this->tree[1];
     	}
		else
		{
           	$this->modifyTree($this->root, $key, $this->id);
      	}
     	$this->id ++;
      	$this->nodeCount ++;
	}
    // 先根遍历,打印树结构,用的递归
	// 此函数可修改用于任何用途
	function preorder(&$root, $level, $r = 'r')
	{
     	$p =& $root;
       	if($r == 'l') 
			$s = str_repeat("\t", 1);
     	else 
			$s = str_repeat("\t", $level);
   		echo $s.$p['k']."";
        if($p['r'] != 0)
		{
         	$p1 =& $this->tree[$p['r']];
          	$this->preorder($p1, $level + 1, 'l');
       	}
		else
		{
           	$s = str_repeat("\t", 1);
       		echo $s.'null'."\n";
     	}
        if($p['l'] != 0)
		{
          	$p1 =& $this->tree[$p['l']];
            $this->preorder($p1, $level + 1);
    	}
		else
		{
         	$s = str_repeat("\t", $level + 1);
          	echo $s.'null'."\n";
     	}
	}
}

测试用代码:

// 此函数主要是为了兼容性
function make_seed() {
	list($usec, $sec) = explode(' ', microtime());
	return (float) $sec + ((float) $usec * 100000);
}
// 生成随机序列键值
function generateRandamSequence($min = 1, $max = 100){
	srand(make_seed());
 	$n = $min;
  	$a = array();
   	while($n <= $max)
	{
      	$randval = rand($min, $max);
      	if($a[$randval - $min] == '')
		{
           	$a[$randval - $min] = $n;
           	$n++;
    	}
	}
   	reset($a);
  	ksort($a);
	reset($a);
  	return $a;
}
$min = 1;
$max = 100;
// 将随机序列键值存入一数组内
$a = generateRandamSequence($min, $max);
print_r($a);   // 打印数组
$tree = new binaryTree; // 建立一棵树
// 将节点按键值顺序插入到树中,同时调整树的结构
for($i=0;$i<$max-$min+1;$i++)
	$tree->insertNode($a[$i]);
print_r($tree); // 打印树对象的内容
echo serialize($tree); // 打印树序列化之后的内容
echo "<hr>;\n<pre>;";
$t =& $tree->root; // 指定树根,为以下传入引用参数用
$tree->preorder($t, 0); // 先根遍历,打印树型结构
// 打印完毕可发现,键值比根键值小的所有节点均在根的左边,反之则在右边,每个节点都是如此
// 但此树不是平衡树(AVL树),因此查询效率还是比较低,特别是如果是连成一直线,则效率达到最低,不能利用树的对数特性了
echo "</pre>;"; // 打印完毕

完整版本:

<?php
// 树节点类
class binaryTreeNode
{
	// 比较节点键值的大小
	function compare($oldkey, $newkey){
		return $newkey - $oldkey;
	}
	// 建立一个新节点
	function createNode($key, $left, $right){
		return array('k'=>$key, 'l'=>$left, 'r'=>$right);
	}
}
// 二叉树类
class binaryTree
{
	var $id = 1;   			// 内部UID,自动加1
 	var $nodeCount = 0; 	// 该树节点数,每插入一个加1
 	var $root = null; 		// 树根的引用
 	var $tree = array(); 	// 树结构,中间存贮所有节点
  	var $_nodes = array(); 	// 存贮不同类型的节点,主要是为了引用该类的方法,便于继承,暂时没有用到
   	var $_node = null; 		// 当前节点类的引用
  	// 构造函数,初始化
  	function binaryTree($nodetype = 'binaryTreeNode'){
  		if(!class_exists($nodetype))
          	$nodetype = 'binaryTreeNode';
       	$this->_nodes[$nodetype] = new $nodetype();
      	$this->_node =& $this->_nodes[$nodetype];
	}
  	// 设定节点类型,暂时用处不大,主要为扩展
   	function setNodeType($nodetype = 'binaryTreeNode'){
      	if(!class_exists($nodetype))
          	$nodetype = 'binaryTreeNode';
		$this->_node =& $this->_nodes[$nodetype];
	}
 	// 插入一节点后修改所有相关节点的信息
	// $pnode 为当前根节点,后两个参数为新节点的参数
 	// 即在树中插入一个新节点后,找到此节点所插入的位置并修改其父节点的信息
    // 此函数本为递归,但因为是尾递归(rear-recursive),因此可以改成循环
   	function modifyTree(&$pnode, $key, $id){
    	$p =& $pnode;
      	while(true){
         	$b = $this->_node->compare($p['k'], $key);
            if($b<=0)
			{
           		if($p['l'] != 0)
				{
                	$p =& $this->tree[$p['l']];
               	}
				else
				{
                   	$p['l'] = $id;
                   	break;
               	}
           	}
			else
			{
               	if($p['r'] != 0)
				{
                	$p =& $this->tree[$p['r']];
             	}
				else
				{
                   	$p['r'] = $id;
                  	break;
            	}
			}
		}
	}
	// 重置树信息
	function reset()
	{
     	$this->tree = array();
      	$this->root = null;
      	$this->id = 1;
     	$this->nodeCount = 0;
    	$this->_node = null;
	}
	// 插入一个键为$key的节点,并自动为此节点生成一个唯一ID
	function insertNode($key)
	{
      	$node = $this->_node->createNode($key, 0, 0);
     	$this->tree[$this->id] = $node;
      	if($this->root == null)
		{
           	$this->root =& $this->tree[1];
     	}
		else
		{
           	$this->modifyTree($this->root, $key, $this->id);
      	}
     	$this->id ++;
      	$this->nodeCount ++;
	}
    // 先根遍历,打印树结构,用的递归
	// 此函数可修改用于任何用途
	function preorder(&$root, $level, $r = 'r')
	{
     	$p =& $root;
       	if($r == 'l') 
			$s = str_repeat("\t", 1);
     	else 
			$s = str_repeat("\t", $level);
   		echo $s.$p['k']."";
        if($p['r'] != 0)
		{
         	$p1 =& $this->tree[$p['r']];
          	$this->preorder($p1, $level + 1, 'l');
       	}
		else
		{
           	$s = str_repeat("\t", 1);
       		echo $s.'null'."\n";
     	}
        if($p['l'] != 0)
		{
          	$p1 =& $this->tree[$p['l']];
            $this->preorder($p1, $level + 1);
    	}
		else
		{
         	$s = str_repeat("\t", $level + 1);
          	echo $s.'null'."\n";
     	}
	}
}
//---------------------------------------------------
// the following is the test
// 此函数主要是为了兼容性
function make_seed() {
	list($usec, $sec) = explode(' ', microtime());
	return (float) $sec + ((float) $usec * 100000);
}
// 生成随机序列键值
function generateRandamSequence($min = 1, $max = 100){
	srand(make_seed());
 	$n = $min;
  	$a = array();
   	while($n <= $max)
	{
      	$randval = rand($min, $max);
      	if($a[$randval - $min] == '')
		{
           	$a[$randval - $min] = $n;
           	$n++;
    	}
	}
   	reset($a);
  	ksort($a);
	reset($a);
  	return $a;
}
$min = 1;
$max = 100;
// 将随机序列键值存入一数组内
$a = generateRandamSequence($min, $max);
print_r($a);   // 打印数组
$tree = new binaryTree; // 建立一棵树
// 将节点按键值顺序插入到树中,同时调整树的结构
for($i=0;$i<$max-$min+1;$i++)
	$tree->insertNode($a[$i]);
print_r($tree); // 打印树对象的内容
echo serialize($tree); // 打印树序列化之后的内容
echo "<hr>;\n<pre>;";
$t =& $tree->root; // 指定树根,为以下传入引用参数用
$tree->preorder($t, 0); // 先根遍历,打印树型结构
// 打印完毕可发现,键值比根键值小的所有节点均在根的左边,反之则在右边,每个节点都是如此
// 但此树不是平衡树(AVL树),因此查询效率还是比较低,特别是如果是连成一直线,则效率达到最低,不能利用树的对数特性了
echo "</pre>;"; // 打印完毕
?>

本文地址:http://www.nowamagic.net/librarys/veda/detail/353,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/353

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《PHP经典实例(第2版)》 斯克拉(David Sklar) (作者), 切贝特伯格(Adam Tracbtenberg) (作者), 李松峰 (译者), 秦绪文 (译者), 李丽 (译者)

PHP经典实例(第2版)能够为您节省宝贵的Web开发时间。有了这些针对真实问题的解决方案放在手边,大多数编程难题都会迎刃而解。《PHP经典实例(第2版)》将PHP的特性与经典实例丛书的独特形式组合到一起,足以帮您成功地构建跨浏览器的Web应用程序。在这个修订版中,您可以更加方便地找到各种编程问题的解决方案,《PHP经典实例(第2版)》中内容涵盖了:表单处理;Session管理;数据库交互;使用Web服务。

更多计算机宝库...