php二叉树数据库设计 php 二叉树

关于一个学习php的问题

你看看这个网址：

十多年的赛罕网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。成都营销网站建设的优势是能够根据用户设备显示端的尺寸不同，自动调整赛罕建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。创新互联从事“赛罕网站设计”,“赛罕网站推广”以来，每个客户项目都认真落实执行。

这是我同时blog

里面有关于php技术的各个层次的讨论

1、PHP编程能力

由于PHP的入门较为简单，所以暂时只有熟悉和精通两个级别。

1、熟悉PHP：精通PHP语法，掌握常用的函数，熟悉PHP5下的OOP应用，这个是基础，也没什么好说的。

2、精通PHP：对PHP运行机制的理解；对系统资源的调用交互理解；关健性能的优化能力。

2、MySQL能力

在开发上的应用基于几个能力体现：

1、了解：知道用PHP连接数据库；懂得写一些简单的SQL；建一些简单的索引；懂得用工具简单操作一下数据库（增删改库表结构数据等等）。

2、熟悉：懂得在开发应用上设计数据库，建立一些有效的索引，用explain分析SQL性能，压力测试等等。

3、很熟悉：深入了解数据库索引、存储引擎原理以及运行机制，能有效地构建高性能可扩展的数据库结构/架构，有效地优化数据库性能配置并加以调试，分析数据库运行状态。

4、精通：简单地说具备以上所有能力的同时，有多年高负载分布式环境下的优化管理经验。

据我观察以及交往经验，70%的PHPer处在了解阶段，25%处于熟悉阶段，4%很熟悉，精通的人基本就不是phper了。

70%这个群体最容易忽视MySQL，以为MySQL只是简单的存储媒介，没有优化意识，认为加个内存、CPU就能解决问题。

典型事件：join、order by、group by等语句性能一塌糊涂，数据库根本没有设计(仅限于拆成一个主表，N个附表等)，搞不清字段类型及作用，碰到大表的复杂查询就没辙。

20%这个群体的人只是MySQL运行机制理解不透彻，对影响MySQL性能的关健因素把握不明确，不熟练。

典型事件：熟读手册，但说不清索引原理，不知道二叉树、HASH等算法对于数据库的作用

4%的群体已经基本可以胜任DBA的职能。

3、OOP能力

1、了解：了解变量的作用域、类型，及其意义，了解继承机制等，懂得复用、封装概

念。

2、熟悉：熟练应用接口、抽象等技术混合开发程序，并理解其中含义，一般研究过JAVA。

3、很熟悉：有过OOP架构设计经验，熟悉设计模式、UML，熟悉PHP对象运行机制，内容管理等。

4、精通：应该是架构师级别了，不限于PHP。

经常我们会碰到一些自称熟悉OOP却连public、private、protected、static都解释不清的人，是肯定没有经历过正规的OOP项目。

4、大型网站经验

1、了解：熟悉PHP开发下的缓存应用（memcache、APC等）；接触过LVS、SQUID应用；

有一定的session处理方案；熟悉负载均衡；熟悉PHP数据连接池应用；了解PHP编程性能优化。

2、熟悉：掌握分布式缓存及缓存性能优化、熟悉存储系统、文件系统、数据库，开发可扩展平台。能结合负载均衡合理布置流量，对PHP运行性能进行监控与分析。

3、非常熟悉：具备系统分析师能力，已经超出phper环节…

4、精通：太深奥..

5、操作系统应用能力

操作系统的熟悉与精通需要需要广泛且扎实的基础理论，而对于开发者来说，熟悉基本的命令操作，对WEB相关服务的安装、配置、优化能力需要具备。

PHP版本二叉树按层 从上到下左到右完全二叉树

?php

/**  * 二叉树的定义  */

class BinaryTree {

protected $key = NULL;      //  当前节点的值

protected $left = NULL;     //  左子树

protected $right = NULL;    //  右子树

/**      * 以指定的值构造二叉树，并指定左右子树      *

* @param mixed $key 节点的值.

* @param mixed $left 左子树节点.

* @param mixed $right 右子树节点.

*/

public function __construct( $key = NULL, $left = NULL, $right = NULL) {

$this-key = $key;

if ($key === NULL) {

$this-left = NULL;

$this-right = NULL;

}

elseif ($left === NULL) {

$this-left = new BinaryTree();

$this-right = new BinaryTree();

}

else {

$this-left = $left;

$this-right = $right;

}

}

/**

* 析构方法.

*/

public function __destruct() {

$this-key = NULL;

$this-left = NULL;

$this-right = NULL;

}

/**

* 清空二叉树.

**/

public function purge () {

$this-key = NULL;

$this-left = NULL;

$this-right = NULL;

}

/**

* 测试当前节点是否是叶节点.

*

* @return boolean 如果节点非空并且有两个空的子树时为真，否则为假.

*/

public function isLeaf() {

return !$this-isEmpty() 

$this-left-isEmpty() 

$this-right-isEmpty();

}

/**

* 测试节点是否为空

*

* @return boolean 如果节点为空返回真，否则为假.

*/

public function isEmpty() {

return $this-key === NULL;

}

/**

* Key getter.

*

* @return mixed 节点的值.

*/

public function getKey() {

if ($this-isEmpty()) {

return false;

}

return $this-key;

}

/**

* 给节点指定Key值,节点必须为空

*

* @param mixed $object 添加的Key值.

*/

public function attachKey($obj) {

if (!$this-isEmpty())

return false;

$this-key = $obj;

$this-left = new BinaryTree();

$this-right = new BinaryTree();

}

/**

* 删除key值，使得节点为空.

*/

public function detachKey() {

if (!$this-isLeaf())

return false;

$result = $this-key;

$this-key = NULL;

$this-left = NULL;

$this-right = NULL;

return $result;

}

/**

* 返回左子树

*

* @return object BinaryTree 当前节点的左子树.

*/

public function getLeft() {

if ($this-isEmpty())

return false;

return $this-left;

}

/**

* 给当前结点添加左子树

*

* @param object BinaryTree $t 给当前节点添加的子树.

*/

public function attachLeft(BinaryTree $t) {

if ($this-isEmpty() || !$this-left-isEmpty())

return false;

$this-left = $t;

}

/**

* 删除左子树

*

* @return object BinaryTree  返回删除的左子树.

*/

public function detachLeft() {

if ($this-isEmpty())

return false;

$result = $this-left;

$this-left = new BinaryTree();

return $result;

}

/**

* 返回当前节点的右子树

*

* @return object BinaryTree 当前节点的右子树.

*/

public function getRight() {

if ($this-isEmpty())

return false;

return $this-right;

}

/**

* 给当前节点添加右子树

*

* @param object BinaryTree $t 需要添加的右子树.

*/

public function attachRight(BinaryTree $t) {

if ($this-isEmpty() || !$this-right-isEmpty())

return false;

$this-right = $t;

}

/**

* 删除右子树，并返回此右子树

* @return object BinaryTree 删除的右子树.

*/

public function detachRight() {

if ($this-isEmpty ())

return false;

$result = $this-right;

$this-right = new BinaryTree();

return $result;

}

/**

* 先序遍历

*/

public function preorderTraversal() {

if ($this-isEmpty()) {

return ;

}

echo ' ', $this-getKey();

$this-getLeft()-preorderTraversal();

$this-getRight()-preorderTraversal();

}

/**

* 中序遍历

*/

public function inorderTraversal() {

if ($this-isEmpty()) {

return ;

}

$this-getLeft()-preorderTraversal();

echo ' ', $this-getKey();

$this-getRight()-preorderTraversal();

}

/**

* 后序遍历

*/

public function postorderTraversal() {

if ($this-isEmpty()) {

return ;

}

$this-getLeft()-preorderTraversal();

$this-getRight()-preorderTraversal();

echo ' ', $this-getKey();

}

}

/**

* 二叉排序树的PHP实现

*/

class BST extends BinaryTree {

/**

* 构造空的二叉排序树

*/

public function __construct() {

parent::__construct(NULL, NULL, NULL);

}

/**

* 析构

*/

public function __destruct() {

parent::__destruct();

}

/**

* 测试二叉排序树中是否包含参数所指定的值

*

* @param mixed $obj 查找的值.

* @return boolean True 如果存在于二叉排序树中则返回真，否则为假期

*/

public function contains($obj) {

if ($this-isEmpty())

return false;

$diff = $this-compare($obj);

if ($diff == 0) {

return true;

}elseif ($diff  0)             return $this-getLeft()-contains($obj);

else

return $this-getRight()-contains($obj);

}

/**

* 查找二叉排序树中参数所指定的值的位置

*

* @param mixed $obj 查找的值.

* @return boolean True 如果存在则返回包含此值的对象，否则为NULL

*/

public function find($obj) {

if ($this-isEmpty())

return NULL;

$diff = $this-compare($obj);

if ($diff == 0)

return $this-getKey();

elseif ($diff  0)             return $this-getLeft()-find($obj);

else

return $this-getRight()-find($obj);

}

/**

* 返回二叉排序树中的最小值

* @return mixed 如果存在则返回最小值，否则返回NULL

*/

public function findMin() {

if ($this-isEmpty ())

return NULL;

elseif ($this-getLeft()-isEmpty())

return $this-getKey();

else

return $this-getLeft()-findMin();

}

/**

* 返回二叉排序树中的最大值

* @return mixed 如果存在则返回最大值，否则返回NULL

*/

public function findMax() {

if ($this-isEmpty ())

return NULL;

elseif ($this-getRight()-isEmpty())

return $this-getKey();

else

return $this-getRight()-findMax();

}

/**

* 给二叉排序树插入指定值

*

* @param mixed $obj 需要插入的值.

* 如果指定的值在树中存在，则返回错误

*/

public function insert($obj) {

if ($this-isEmpty()) {

$this-attachKey($obj);

} else {

$diff = $this-compare($obj);

if ($diff == 0)

die('argu error');

if ($diff  0)                 $this-getLeft()-insert($obj);

else

$this-getRight()-insert($obj);

}

$this-balance();

}

/**

* 从二叉排序树中删除指定的值

*

* @param mixed $obj 需要删除的值.

*/

public function delete($obj) {

if ($this-isEmpty ())

die();

$diff = $this-compare($obj);

if ($diff == 0) {

if (!$this-getLeft()-isEmpty()) {

$max = $this-getLeft()-findMax();

$this-key = $max;

$this-getLeft()-delete($max);

}

elseif (!$this-getRight()-isEmpty()) {

$min = $this-getRight()-findMin();

$this-key = $min;

$this-getRight()-delete($min);

} else

$this-detachKey();

} else if ($diff  0)                 $this-getLeft()-delete($obj);

else

$this-getRight()-delete($obj);

$this-balance();

}

public function compare($obj) {

return $obj - $this-getKey();

}

/**

* Attaches the specified object as the key of this node.

* The node must be initially empty.

*

* @param object IObject $obj The key to attach.

* @exception IllegalOperationException If this node is not empty.

*/

public function attachKey($obj) {

if (!$this-isEmpty())

return false;

$this-key = $obj;

$this-left = new BST();

$this-right = new BST();

}

/**

* Balances this node.

* Does nothing in this class.

*/

protected function balance () {}

/**

* Main program.

*

* @param array $args Command-line arguments.

* @return integer Zero on success; non-zero on failure.

*/

public static function main($args) {

printf("BinarySearchTree main program.\n");

$root = new BST();

foreach ($args as $row) {

$root-insert($row);

}

return $root;

}

}

$root = BST::main(array(50, 3, 10, 5, 100, 56, 78));

echo $root-findMax();

$root-delete(100);

echo $root-findMax();

用php调数据库做树状显示

数据库设计的时候，通常的做法是用父ID来解决树状结构，也有二叉树等等

id  pid category_name

然后，用递归就能实现，也有引用数组的方式

?php

/**

* 此方法由@Tonton 提供

* 

* @date 2012-12-12 

*/

function genTree5($items) { 

foreach ($items as $item) 

$items[$item['pid']]['son'][$item['id']] = $items[$item['id']]; 

return isset($items[0]['son']) ? $items[0]['son'] : array(); 

} 

/**

* 将数据格式化成树形结构

* @author Xuefen.Tong

* @param array $items

* @return array 

*/

function genTree9($items) {

$tree = array(); //格式化好的树

foreach ($items as $item)

if (isset($items[$item['pid']]))

$items[$item['pid']]['son'][] = $items[$item['id']];

else

$tree[] = $items[$item['id']];

return $tree;

}

$items = array(

1 = array('id' = 1, 'pid' = 0, 'name' = '江西省'),

2 = array('id' = 2, 'pid' = 0, 'name' = '黑龙江省'),

3 = array('id' = 3, 'pid' = 1, 'name' = '南昌市'),

4 = array('id' = 4, 'pid' = 2, 'name' = '哈尔滨市'),

5 = array('id' = 5, 'pid' = 2, 'name' = '鸡西市'),

6 = array('id' = 6, 'pid' = 4, 'name' = '香坊区'),

7 = array('id' = 7, 'pid' = 4, 'name' = '南岗区'),

8 = array('id' = 8, 'pid' = 6, 'name' = '和兴路'),

9 = array('id' = 9, 'pid' = 7, 'name' = '西大直街'),

10 = array('id' = 10, 'pid' = 8, 'name' = '东北林业大学'),

11 = array('id' = 11, 'pid' = 9, 'name' = '哈尔滨工业大学'),

12 = array('id' = 12, 'pid' = 8, 'name' = '哈尔滨师范大学'),

13 = array('id' = 13, 'pid' = 1, 'name' = '赣州市'),

14 = array('id' = 14, 'pid' = 13, 'name' = '赣县'),

15 = array('id' = 15, 'pid' = 13, 'name' = '于都县'),

16 = array('id' = 16, 'pid' = 14, 'name' = '茅店镇'),

17 = array('id' = 17, 'pid' = 14, 'name' = '大田乡'),

18 = array('id' = 18, 'pid' = 16, 'name' = '义源村'),

19 = array('id' = 19, 'pid' = 16, 'name' = '上坝村'),

);

echo "pre";

print_r(genTree5($items));

print_r(genTree9($items));

?