PHP实现二分搜索树，如何高效检索长尾？

本文共计2376个文字，预计阅读时间需要10分钟。

前言：本文介绍二叉树和二分搜索树，然后通过PHP代码定义二分搜索树的节点，使用递归思维操作向二分搜索树添加元素，并实现了递归判断二分搜索树上是否包含某个元素。

前言

这篇文章是介绍 二叉树 和 二分搜索树，然后通过 PHP 代码定义一下 二分搜索树 的节点，使用递归思想操作向二分搜索树添加元素，然后实现了递归判断二分搜索树上是否包含某个元素，最后分别实现了前序遍历、中序遍历、后序遍历 二分搜索树。

1.二叉树

1.1 二叉树图示

1.2 二叉树节点定义

//二叉树具有唯一根节点 class Node{ $e; //节点元素 $left; //左儿子 $right;//右儿子 }

Tips：二叉树每个节点最多有两个儿子，每个节点最多有一个父亲。

1.3 二叉树的特点

• 二叉树具有天然的递归结构，每个节点的左儿子或右儿子也是 二叉树。
• 二叉树不一定是满的，可能只有左儿子或又儿子。
• 一个节点或 NULL 也可以看做一个二叉树。
  

2.二分搜索树

2.1 二分搜索树特点

• 二分搜索树是二叉树。
• 每个节点的元素的值都要大于左儿子所有节点的值。
• 每个节点的元素的值都要小于右儿子所有节点的值。