共计 836 个字符,预计需要花费 3 分钟才能阅读完成。
这篇文章是介绍 二叉树
和 二分搜寻树
,而后通过 PHP
代码定义一下 二分搜寻树(Binary Search Tree)
的节点。
1. 二叉树
1.1 二叉树图示
1.2 二叉树节点定义
// 二叉树具备惟一根节点
class Node{
$e; // 节点元素
$left; // 左儿子
$right;// 右儿子
}
Tips:二叉树每个节点最多有两个儿子,每个节点最多有一个父亲。
1.3 二叉树的特点
- 二叉树具备人造的递归结构,每个节点的左儿子或右儿子也是
二叉树
。 - 二叉树不肯定是满的,可能只有左儿子或又儿子。
- 一个节点或 NULL 也能够看做一个二叉树。
2. 二分搜寻树
2.1 二分搜寻树特点
- 二分搜寻树是二叉树。
- 每个节点的元素的值都要大于左儿子所有节点的值。
- 每个节点的元素的值都要小于右儿子所有节点的值。
- 每个子树也是二分搜寻树。
- 二分搜寻树查问速度快。
- 存储的元素必须要有比拟性。
2.2 二分搜寻树图示
2.3 PHP 代码定义节点
<?php
class BinarySearchTree
{
private $root;
private $size;
/**
* 构造函数 初始化二分搜寻树
* BinarySearchTree constructor.
*/
public function __construct() {
$this->root = null;
$this->size;
}
/**
* 获取以后搜寻树元素个数
* @return mixed
*/
public function getSize() {return $this->size;}
/**
* 判断以后二分搜寻树是否为空
* @return bool
*/
public function isEmpty(): bool {return $this->size == 0;}
}
class Node
{
public $e;
public $left = null;
public $right = null;
/**
* 构造函数 初始化节点数据
* Node constructor.
* @param $e
*/
public function __construct($e) {$this->e = $e;}
}
正文完