这篇文章是介绍 二叉树 和 二分搜寻树，而后通过 PHP 代码定义一下 二分搜寻树 的节点，应用递归思维操作向二分搜寻树增加元素，而后实现了递归判断二分搜寻树上是否蕴含某个元素，最初别离实现了前序遍历、中序遍历、后序遍历 二分搜寻树。
1.二叉树
1.1 二叉树图示
1.2 二叉树节点定义
//二叉树具备惟一根节点class Node{ $e; //节点元素 $left; //左儿子 $right;//右儿子}Tips：二叉树每个节点最多有两个儿子，每个节点最多有一个父亲。
1.3 二叉树的特点
- 二叉树具备人造的递归结构，每个节点的左儿子或右儿子也是
二叉树。 - 二叉树不肯定是满的，可能只有左儿子或又儿子。
- 一个节点或 NULL 也能够看做一个二叉树。
2.二分搜寻树
2.1 二分搜寻树特点
- 二分搜寻树是二叉树。
- 每个节点的元素的值都要大于左儿子所有节点的值。
- 每个节点的元素的值都要小于右儿子所有节点的值。
- 每个子树也是二分搜寻树。
- 二分搜寻树查问速度快。
- 存储的元素必须要有比拟性。
2.2 二分搜寻树图示
2.3 PHP 代码定义节点
class Node{ public $e; public $left = null; public $right = null; /** * 构造函数 初始化节点数据 * Node constructor. * @param $e */ public function __construct($e) { $this->e = $e; }}2.4 向二分搜寻树增加元素
上面展现的的应用递归思维向二分搜寻树增加元素，其中 add($e) 办法示意想二分搜寻树增加元素 $e，recursionAdd(Node $root, $e) 是一个递归函数，示意应用递归向二分搜寻树增加元素：
/** * 向二分搜寻树增加元素 * @param $e */ public function add($e) { $this->root = $this->recursionAdd($this->root, $e); } /** * 递归向二分搜寻树增加元素 * @param Node $root * @param $e */ public function recursionAdd(Node $root, $e) { if ($root == null) { //若节点为空则增加元素 并且返回以后节点信息 $this->size++; $root = new Node($e); } elseif ($e < $root->e) { //若元素小于以后节点元素 则向左节点递归增加元素 $root->left = $this->recursionAdd($root->left, $e); } elseif ($e > $root->e) { //若元素大于以后节点元素 则向右节点递归增加元素 $root->right = $this->recursionAdd($root->right, $e); } //若元素等于以后节点元素 则什么都不做 }Tips：这里的二分搜寻树不蕴含反复元素，如果想要蕴含反复元素，能够定义每个左儿子所有元素小于等于父亲节点，或者每个节点右儿子所有节点元素大于等于父亲节点。
2.5 查问二分搜寻树是否蕴含某个元素
上面展现的的应用递归思维查问二分搜寻树元素是否蕴含某个元素，其中 contains($e) 办法示意查问二分搜寻树是否蕴含元素 $e，recursionContains(Node $root, $e) 是一个递归函数，示意应用递归查问二分搜寻树元素：
/** * 判断二分搜寻树是否蕴含某个元素 * @param $e * @return bool */ public function contains($e): bool { return $this->recursionContains($this->root, $e); } /** * 递归判断二分搜寻树是否蕴含某元素 * @param $root * @param $e * @return bool */ private function recursionContains(Node $root, $e): bool { if ($root == null) { //若以后节点为空 则示意不存在元素 $e return false; } elseif ($e == $root->e) { //若 $e 等于以后节点元素，则示意树蕴含元素 $e return true; } elseif ($e < $root->e) { //若 $e 小于以后节点元素，则去左儿子树递归查问是否蕴含节点 return $this->recursionContains($root->left, $e); } else { //若 $e 大于以后节点元素，则去右儿子树递归查问是否蕴含节点 return $this->recursionContains($root->right, $e); } }Tips：递归的时候会比拟元素和节点的值，递归的时候判断元素大小相当于 “指路”，最终指向到的地位就是判断是否蕴含元素是否存在的根据。
2.6 二分搜寻树前序遍历
前序遍历操作就是把所有节点都拜访一次，前序遍历 是先拜访节点，再递归遍历左儿子树，而后再递归遍历右儿子树：
/** * 前序遍历 */ public function preTraversal() { $this->recursionPreTraversal($this->root, 0); } /** * 前序遍历的递归 */ public function recursionPreTraversal($root, $sign_num) { echo $this->getSign($sign_num);//打印深度 if ($root == null) { echo "null<br>"; return; } echo $root->e . "<br>"; //打印以后节点元素 $this->recursionPreTraversal($root->left, $sign_num + 1); $this->recursionPreTraversal($root->right, $sign_num + 1); }上面是打印后果:
<?phprequire 'BinarySearchTree.php';$binarySearchTree = new BinarySearchTree();$binarySearchTree->add(45);$binarySearchTree->add(30);$binarySearchTree->add(55);$binarySearchTree->add(25);$binarySearchTree->add(35);$binarySearchTree->add(50);$binarySearchTree->add(65);$binarySearchTree->add(15);$binarySearchTree->add(27);$binarySearchTree->add(31);$binarySearchTree->add(48);$binarySearchTree->add(60);$binarySearchTree->add(68);//上面是预期想要的后果/** * 45 * / * 30 55 * / / * 25 35 50 65 * / / / / * 15 27 31 48 60 68 * */$binarySearchTree->preTraversal();/**打印输出45-----30----------25---------------15--------------------null--------------------null---------------27--------------------null--------------------null----------35---------------31--------------------null--------------------null---------------null-----55----------50---------------48--------------------null--------------------null---------------null----------65---------------60--------------------null--------------------null---------------68--------------------null--------------------null */Tips：能够看到打印输出后果和预期统一。
2.7 二分搜寻树中序遍历
遍历操作就是把所有节点都拜访一次，后序遍历 是先递归遍历右儿子树，再拜访节点，而后再递归遍历右儿子树，最初的程序输入后果是有序的：
/** * 中序遍历 */ public function midTraversal() { $this->recursionMidTraversal($this->root, 0); } /** * 中序遍历的递归 */ public function recursionMidTraversal($root, $sign_num) { if ($root == null) { echo $this->getSign($sign_num);//打印深度 echo "null<br>"; return; } $this->recursionMidTraversal($root->left, $sign_num + 1); echo $this->getSign($sign_num);//打印深度 echo $root->e . "<br>"; $this->recursionMidTraversal($root->right, $sign_num + 1); }上面是打印后果:
<?phprequire 'BinarySearchTree.php';$binarySearchTree = new BinarySearchTree();$binarySearchTree->add(45);$binarySearchTree->add(30);$binarySearchTree->add(55);$binarySearchTree->add(25);$binarySearchTree->add(35);$binarySearchTree->add(50);$binarySearchTree->add(65);$binarySearchTree->add(15);$binarySearchTree->add(27);$binarySearchTree->add(31);$binarySearchTree->add(48);$binarySearchTree->add(60);$binarySearchTree->add(68);//上面是预期想要的后果/** * 45 * / * 30 55 * / / * 25 35 50 65 * / / / / * 15 27 31 48 60 68 * */$binarySearchTree->midTraversal();/**打印输出--------------------null---------------15--------------------null----------25--------------------null---------------27--------------------null-----30--------------------null---------------31--------------------null----------35---------------null45--------------------null---------------48--------------------null----------50---------------null-----55--------------------null---------------60--------------------null----------65--------------------null---------------68--------------------null */Tips：能够看到打印输出后果和预期统一，然而此时的遍历程序变了，最初的程序输入后果是有序的。2.8 二分搜寻树后序遍历
遍历操作就是把所有节点都拜访一次，后序遍历 是先递归遍历左儿子树，而后再递归遍历右儿子树，再拜访节点：
/** * 后序遍历 */ public function rearTraversal() { $this->recursionRearTraversal($this->root, 0); } /** * 后序遍历的递归 */ public function recursionRearTraversal($root, $sign_num) { if ($root == null) { echo $this->getSign($sign_num);//打印深度 echo "null<br>"; return; } $this->recursionRearTraversal($root->left, $sign_num + 1); $this->recursionRearTraversal($root->right, $sign_num + 1); echo $this->getSign($sign_num);//打印深度 echo $root->e . "<br>"; }上面是打印后果:
<?phprequire 'BinarySearchTree.php';$binarySearchTree = new BinarySearchTree();$binarySearchTree->add(45);$binarySearchTree->add(30);$binarySearchTree->add(55);$binarySearchTree->add(25);$binarySearchTree->add(35);$binarySearchTree->add(50);$binarySearchTree->add(65);$binarySearchTree->add(15);$binarySearchTree->add(27);$binarySearchTree->add(31);$binarySearchTree->add(48);$binarySearchTree->add(60);$binarySearchTree->add(68);//上面是预期想要的后果/** * 45 * / * 30 55 * / / * 25 35 50 65 * / / / / * 15 27 31 48 60 68 * */$binarySearchTree->rearTraversal();/**打印输出--------------------null--------------------null---------------15--------------------null--------------------null---------------27----------25--------------------null--------------------null---------------31---------------null----------35-----30--------------------null--------------------null---------------48---------------null----------50--------------------null--------------------null---------------60--------------------null--------------------null---------------68----------65-----5545 */代码仓库 ：https://gitee.com/love-for-po...
扫码关注爱因诗贤