钛节点

数据结构之二叉搜索树（三）

发表@2018-09-13 09:15:22

更新@2023-01-21 22:47:40

前面讲了一坨跟树有关的玩意，无论是理解搞定了，还是死记硬背搞定的，完事后都会如下图所示：

![](https://ti-node.com/static/upload/6405980790953345025)

为了表示二叉树是有一些卵用的，所以今天引入二叉搜索树，近义词是二叉查找树或者二叉排序树，是一种常见并常用的数据结构。二叉搜索树整体是有序的，比如从大到小又或者从小到大，正是因为有序，所以才会利于查找。举个例子：一坨数字15、10、18、7、12、16、19，让你快速从中找到16。作为蠢货，我的第一个想法就是循环，挨个对比，啥时候对上号了，那就算找到了，然后我运算6次，找到了16。

然而，一些稍微不傻的人会考虑从中间7开始对比，这个时候会有两种选择：从7往前，从7往后。从7往前的就比较悲催了，但是从7往后的，3次就能找到16。

最后，一些聪明人就开始基于“稍微不傻”的这些人的想法继续想：“要是选中间数的时候，能够知道要找数字在中间数前面或者后面就好了，一次可以锁定一个区域！”，于是搜索二叉树应运而生，如下图：

![](https://ti-node.com/static/upload/6405996854143614977)

如果我们要找19，19比15大，那一定是在15的右子树上，接着15的右子树的根节点就是18，19依然比18大，然后向18的右子树进发，bingo，找到了。

### 数据量越大，这种二叉搜索树越是能体现出自己的优势！

通过上面的俗话和示例似乎并不能准确描述二叉搜索树（二叉排序树、二叉查找树），有时候官方语言还是要套一套的：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值
- 任意节点的左、右子树也分别为二叉查找树
- 没有键值相等的节点

二叉搜索树首先是一颗二叉树，其次是带“搜索”优化功能，所以，我们将前几节中的代码直接复制粘贴然后魔改一把，你们感受一下：

```php
<?php
class Node{
  // 父节点
  private $parent = null;
  // 左子树
  private $left = null;
  // 右子树
  private $right = null;
  // 数据域
  private $data = null;
  public function __construct( $value ){
    $this->data = $value;
  }
  // 添加左子树
  public function setLeft( Node $node ){
    // 将当前class实例化后的结点作为父结点
    $node->parent = $this;
    $this->left = $node;
    return $node;
  }
  // 添加右子树
  public function setRight( Node $node ){
    // 将当前class实例化后的结点作为父结点
    $node->parent = $this;
    $this->right = $node;
    return $node;
  }
  // 前序遍历
  public function preOrder( $tree ){
    if( $tree instanceof Node ){
      // 先遍历根节点
      echo $tree->data.'  ';
      // 然后遍历左子树
      $this->preOrder( $tree->left );
      // 最后遍历右子树
      $this->preOrder( $tree->right );
    }
  }
  // 中序遍历
  public function midOrder( $tree ){
    if( $tree instanceof Node ){
      // 先遍历左子树
      $this->midOrder( $tree->left );
      // 再遍历根节点
      echo $tree->data.'  ';
      // 后遍历右子树
      $this->midOrder( $tree->right );
    }
  }
  // 后续遍历
  public function sufOrder( $tree ){
    if( $tree instanceof Node ){
      // 先遍历左子树
      $this->sufOrder( $tree->left );
      // 再遍历右子树
      $this->sufOrder( $tree->right );
      // 最后遍历根节点
      echo $tree->data.'  ';
    }
  }
}
```
上面代码就是上节课完整的代码，但是，很明显由于二叉搜索树的特征，setLeft和setRight两个方法算是报废了，最起码说，是不能直接调用的。迫于无奈，不得不分析一波儿了：拿新结点的数值和原有树的根节点开始比较，比根节点大，那么往右走；比根节点小，那么往左走。然后我们将根节点的左子树或者右子树依然当作一颗独立完整的树来看待，那么，然后继续用新结点与之进行上述步骤。。。是不是闻到了一股浓重的递归味儿？

```php
<?php
  // 接着上面的Node class补充进去
  public static function insert( $tree, $node ){
    // 新结点值比当前结点小，往左走
    if( $node->data < $tree->data ){
      if( $tree->left ){
        $tree = $tree->left;
        self::insert( $tree, $node );
      }   
      // 如果不存在左子树  
      else{
        $tree->setLeft( $node );
      }   
    }   
    // 新结点值比当前结点大，往右走
    else if( $node->data > $tree->data ){
      if( $tree->right ){
        $tree = $tree->right;
        self::insert( $tree, $node );
      }   
      // 如果不存在左子树  
      else{
        $tree->setRight( $node );
      }   
    }   
  }
```

开篇吹过了，搜索二叉树一大优势就是快速查找确定数值的结点，那么是时候出来溜溜了。其实查找本身也是也是根据搜索二叉树的特征进行查找的，整个过程和添加结点是颇为相似的。依然是从根节点开始，要么find的目标结点比根节点的小，要么find的目标结点比根结点的大，小了往左走，大了往右走。无论是往左走还是往右走，我们都可以把其子树当作独立的一个树，和要find的目标依然重复上述操作，最终当要find的目标既不大于根结点也不小于根节点，也就是意味着找到该结点了。同时，我们知道一颗搜索二叉树的最小值一定是最左下角那个结点，最大值一定是最右下角那个结点，所以这两个方法应该很容易写出来，你们感受一下：

```php
<?php
  public static function find( $tree, $value ){
    if( ! ( $tree instanceof Node ) ){
      return null;
    }   
    while( $tree ){
      if( $value < $tree->data ){
        $tree = $tree->left;
      }else if( $value > $tree->data ){
        $tree = $tree->right;
      } else {
        return $tree;
      }
    }
  }
  // 最小的 一定就是最左下角位置
  public static function findMin( $tree ){
    while( $tree->left ){
      $tree = $tree->left;
    }
    return $tree->data;
  }
  // 最大的 一定就是最右下角位置
  public static function findMax( $tree ){
    while( $tree->right ){
      $tree = $tree->right;
    }
    return $tree->data;
  }
```
码完代码，跑一个简单的小测试。这里值得注意的一点是，如果对一个搜索二叉树进行中序遍历，那么会得到一个有序数字队列。

```php
<?php
$tree = new Node( 20 );
Node::insert( $tree, new Node( 15 ) );
Node::insert( $tree, new Node( 30 ) );
Node::insert( $tree, new Node( 12 ) );
Node::insert( $tree, new Node( 18 ) );
Node::insert( $tree, new Node( 38 ) );
Node::insert( $tree, new Node( 23 ) );
// 12  15  18  20  23  30  38
$targetNode = Node::find( $tree, 12 );
$min = Node::findMin( $tree );
$max = Node::findMax( $tree );
//echo $min.PHP_EOL;
//echo $max.PHP_EOL;
//print_r( $max );

// 接着上面的运行代码，运行一下三种排序...
//echo $tree->preOrder( $tree ).PHP_EOL;
echo $tree->midOrder( $tree ).PHP_EOL;
//echo $tree->sufOrder( $tree ).PHP_EOL;
```