二叉树生成：
1.传进来一个值，当前二叉树对象没用值，放置一个值，
传进一个值，当前二叉树对象有值
判断当前对象值和传进来的大小，如果传进来的值大，new 一个 self，放置到右边，然后调用 右边二叉树对象的 创建值的方法。 判断当前对象值和传进来的大小，如果传进来的值小，new 一个 self，放置到左边，然后调用 左边二叉树对象的 创建值的方法。
下面这个例子，不能中途添加数据，只能一次生成，不能旋转，只是一个简单的demo,供大家借鉴。
例子：
/**
* Btree 类
*/
class Btree
{
private $key = 0;
/** @var $left self */
private $left;
/** @var $right self */
private $right;
/**
* 构造函数
*/
public function __construct($arr = null)
{
$this -> _init($arr);
}
/**
* 将数组初始化成二叉树
*
* @param $key
*
* @return bool
*/
private function _init($key)
{
if (empty($key)) {
return false;
}
if ( !is_array($key) && empty($this -> key)) {
$this -> key = $key;
return true;
}
foreach ($key as $k) {
$this -> _create($k);
}
return true;
}
/**
* 生成二叉树核心方法
*
* @param $key
*
* @return bool
*/
private function _create($key)
{
if (empty($this -> key)) {
$this -> key = $key;
return true;
}
if ($this -> key > $key) {
if (empty($this -> left)) {
$this -> left = new self;
}
$this -> left -> _create($key);
} else {
if (empty($this -> right)) {
$this -> right = new self;
}
$this -> right -> _create($key);
}
return true;
}
/**
* 获取二叉树的升序排序
*
* @return array
*/
public function up()
{
// 获取当前对象的 key 并变成数组，以统一返回类型
$current = [$this -> key];
if (empty($this -> left) && empty($this -> right)) {
// 如果没有 左子树 和 右子树，直接返回当前值的数组即可
return $current;
}
if (empty($this -> left) && !empty($this -> right)) {
/**
* 如果没有左子树 并且有 右子树
* 当前值 肯定比 右子树 所有的值 要小
* 所以 把当前值放置在开始位置 连接数组后返回
*/
return array_merge($current, $this -> right -> up());
} else if (empty($this -> right) && !empty($this -> left)) {
/**
* 如果没有右子树 并且有 左子树
* 当前值 肯定比 左子树 所有的值 要大
* 所以 把当前值放置在结束位置 连接数组后返回
*/
return array_merge($this -> left -> up(), $current);
}
/**
* 当 既有左子树 又有 右子树时
* 当前值 肯定比 左子树所有数值 要大
* 当前值 肯定比 右子树所有数值 要小
* 所以 连接数组的时候 左子树的 在前 当前的在中间 右子树的在右
*/
return array_merge($this -> left -> up(), $current, $this -> right -> up());
}
/**
* 获取二叉树的降序排序
*
* @return array
*/
public function down()
{
$current = [$this -> key];
if (empty($this -> left) && empty($this -> right)) {
return $current;
}
if (empty($this -> left) && !empty($this -> right)) {
return array_merge($this -> right -> down(), $current);
} else if (empty($this -> right) && !empty($this -> left)) {
return array_merge($current, $this -> left -> down());
}
return array_merge($this -> right -> down(), $current, $this -> left -> down());
}
}
$arr = [5, 6, 4, 7, 2, 78, 12, 45, 23, 122, 786, 456, 237, 127, 1, 3];
$bt = new Btree($arr);
$up = $bt -> up();
$down = $bt -> down();
print_r($bt);
print_r($up);
print_r($down);输出结果：
Btree Object
(
[key:Btree:private] => 5
[left:Btree:private] => Btree Object
(
[key:Btree:private] => 4
[left:Btree:private] => Btree Object
(
[key:Btree:private] => 2
[left:Btree:private] => Btree Object
(
[key:Btree:private] => 1
[left:Btree:private] =>
[right:Btree:private] =>
)
[right:Btree:private] => Btree Object
(
[key:Btree:private] => 3
[left:Btree:private] =>
[right:Btree:private] =>
)
)
[right:Btree:private] =>
)
[right:Btree:private] => Btree Object
(
[key:Btree:private] => 6
[left:Btree:private] =>
[right:Btree:private] => Btree Object
(
[key:Btree:private] => 7
[left:Btree:private] =>
[right:Btree:private] => Btree Object
(
[key:Btree:private] => 78
[left:Btree:private] => Btree Object
(
[key:Btree:private] => 12
[left:Btree:private] =>
[right:Btree:private] => Btree Object
(
[key:Btree:private] => 45
[left:Btree:private] => Btree Object
(
[key:Btree:private] => 23
[left:Btree:private] =>
[right:Btree:private] =>
)
[right:Btree:private] =>
)
)
[right:Btree:private] => Btree Object
(
[key:Btree:private] => 122
[left:Btree:private] =>
[right:Btree:private] => Btree Object
(
[key:Btree:private] => 786
[left:Btree:private] => Btree Object
(
[key:Btree:private] => 456
[left:Btree:private] => Btree Object
(
[key:Btree:private] => 237
[left:Btree:private] => Btree Object
(
[key:Btree:private] => 127
[left:Btree:private] =>
[right:Btree:private] =>
)
[right:Btree:private] =>
)
[right:Btree:private] =>
)
[right:Btree:private] =>
)
)
)
)
)
)
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 6
[6] => 7
[7] => 12
[8] => 23
[9] => 45
[10] => 78
[11] => 122
[12] => 127
[13] => 237
[14] => 456
[15] => 786
)
Array
(
[0] => 786
[1] => 456
[2] => 237
[3] => 127
[4] => 122
[5] => 78
[6] => 45
[7] => 23
[8] => 12
[9] => 7
[10] => 6
[11] => 5
[12] => 4
[13] => 3
[14] => 2
[15] => 1
)可能会有问题，欢迎指正。
不要问我怎么写的博客。请直接告诉我你想说啥。
程序员吗 弯弯绕很烦人。
评论已关闭