数据结构二叉树php 数据结构二叉树的遍历算法

数据结构算法在php编程中的作用？

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

成都创新互联是一家专业提供泸水企业网站建设,专注与网站建设、成都网站制作、HTML5建站、小程序制作等业务。10年已为泸水众多企业、政府机构等服务。创新互联专业网站建设公司优惠进行中。

使用php实现的基本的数据结构和算法，什么二叉树、二叉搜索树、AVL树、B树、链表和常见排序、搜索算法等等，而且全部是使用面向对象来实现的，确是是很强。

php程序员有必要学习数据结构与算法吗？

没必要去学什么排序、查找的算法，没别要去学什么链表、堆栈、队列等数据结构的细节。

提升主要是快速开发，接到项目可以一晚上交货的就是高手。

不过工资与上面的都无关，工资主要决定于你和领导的关系。

如何根据制定的数据使用PHP生成一个二叉树

假如你所说的二叉树是指这种的话

那么你的数据结构一定要满足一个条件，则每一条数据必须记录好父级的标识

?php

$data = array(

array(

'id' = 1,

'pid' = 0,

'name' = ""新建脑图,

),

array(

'id' = 2,

'pid' = 1,

'name' = "分支主题",

),

array(

'id' = 3,

'pid' = 1,

'name' = "分支主题",

),

);

?

上述二位数组中的 id为2，3的子数组的父级（pid）id均是1，则他们的父级就是id为1的数组

?php

foreach($data as $key=$value){

if( $value['pid'] == '0'){

$parent[] = $value;

unset($data[$key]);

} 

}

foreach($parent as $key=$value){

foreach($data as $k=$v){

if( $v['pid'] == $value['id'] ){

$parent[$key]['_child'][] = $v;

unset($data[$k]);

} 

}

}

?

通过以上循环过后，对应二叉树关系的数组就可以做出来了

当然上述代码只能进行到二级二叉树，如果想做出无限级二叉树的数组，则必须使用到递归函数了

PS：上述代码是网页里手打的，没经过测试，但思路肯定是没问题的哈

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();