PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】

本文实例讲述了php实现绘制二叉树图形显示功能。分享给大家供大家参考，具体如下：

前言：

最近老师布置了一个作业：理解并实现平衡二叉树和红黑树，本来老师是说用c#写的，但是我学的c#基本都还给老师了，怎么办？那就用现在最熟悉的语言php来写吧！

有一个问题来了，书上在讲解树的时候基本上会给出形象的树形图。但是当我们自己试着实现某种树，在调试、输出的时候确只能以字符的形式顺序地输出。这给调试等方面带来了很大的不便。然后在各种百度之后，我发现利用php实现二叉树的图形显示的资源几乎是零！好吧，那我就自己个儿实现一个！

效果显示：

如果我是直接在这一步摆代码的话，估计大家会比较烦闷，那我就直接上结果吧，后面在补代码，先激发激发大家的阅读兴趣：

1、搜索二叉树：

2、平衡二叉树：

3、红黑树：

上代码：

我们给图片创建一个类吧，显得稍微的小高级：

image.php 文件：

<?php
/**
 * author:lsgozj
 * description: 绘制二叉树图像
 */
class image
{
  //树相关设置
  //每层之间的间隔高度
  private $level_high = 100;
  //最底层叶子结点之间的宽度
  private $leaf_width = 50;
  //结点圆的半径
  private $rad = 20;
  //根节点离边框顶端距离
  private $leave = 20;
  //树（保存树对象的引用）
  private $tree;
  //树的层数
  private $level;
  //完全二叉树中最底层叶子结点数量（计算图像宽度时用到，论如何实现图片大小自适应）
  private $maxcount;
  //图像相关设置
  //画布宽度
  private $width;
  //画布高度
  private $height;
  //画布背景颜色（rgb）
  private $bg = array(
    220, 220, 220
  );
  //节点颜色（搜索二叉树和平衡二叉树时用）
  private $nodecolor = array(
    255, 192, 203
  );
  //图像句柄
  private $image;
  /**
   * 构造函数，类属性初始化
   * @param $tree 传递一个树的对象
   * @return null
   */
  public function __construct($tree)
  {
    $this->tree = $tree;
    $this->level = $this->getlevel();
    $this->maxcount = $this->getmaxcount($this->level);
    $this->width = ($this->rad * 2 * $this->maxcount) + $this->maxcount * $this->leaf_width;
    $this->height = $this->level * ($this->rad * 2) + $this->level_high * ($this->level - 1) + $this->leave;
    //1.创建画布
    $this->image = imagecreatetruecolor($this->width, $this->height); //新建一个真彩色图像，默认背景是黑色
    //填充背景色
    $bgcolor = imagecolorallocate($this->image, $this->bg[0], $this->bg[1], $this->bg[2]);
    imagefill($this->image, 0, 0, $bgcolor);
  }
  /**
   * 返回传进来的树对象对应的完全二叉树中最底层叶子结点数量
   * @param $level 树的层数
   * @return 结点数量
   */
  function getmaxcount($level)
  {
    return pow(2, $level - 1);
  }
  /**
   * 获取树对象的层数
   * @param null
   * @return 树的层数
   */
  function getlevel()
  {
    return $this->tree->depth();
  }
  /**
   * 显示二叉树图像
   * @param null
   * @return null
   */
  public function show()
  {
    $this->draw($this->tree->root, 1, 0, 0);
    header("content-type:image/png");
    imagepng($this->image);
    imagedestroy($this->image);
  }
  /**
   * （递归）画出二叉树的树状结构
   * @param $root，根节点（树或子树） $i，该根节点所处的层 $p_x，父节点的x坐标 $p_y,父节点的y坐标
   * @return null
   */
  private function draw($root, $i, $p_x, $p_y)
  {
    if ($i <= $this->level) {
      //当前节点的y坐标
      $root_y = $i * $this->rad + ($i - 1) * $this->level_high;
      //当前节点的x坐标
      if (!is_null($parent = $root->parent)) {
        if ($root == $parent->left) {
          $root_x = $p_x - $this->width / (pow(2, $i));
        } else {
          $root_x = $p_x + $this->width / (pow(2, $i));
        }
      } else {
        //根节点
        $root_x = (1 / 2) * $this->width;
        $root_y += $this->leave;
      }
      //画结点（确定所画节点的类型（平衡、红黑、排序）和方法）
      $method = 'draw' . get_class($this->tree) . 'node';
      $this->$method($root_x, $root_y, $root);
      //将当前节点和父节点连线（黑色线）
      $black = imagecolorallocate($this->image, 0, 0, 0);
      if (!is_null($parent = $root->parent)) {
        imageline($this->image, $p_x, $p_y, $root_x, $root_y, $black);
      }
      //画左子节点
      if (!is_null($root->left)) {
        $this->draw($root->left, $i + 1, $root_x, $root_y);
      }
      //画右子节点
      if (!is_null($root->right)) {
        $this->draw($root->right, $i + 1, $root_x, $root_y);
      }
    }
  }
  /**
   * 画搜索二叉树结点
   * @param $x，当前节点的x坐标 $y，当前节点的y坐标 $node，当前节点的引用
   * @return null
   */
  private function drawbstnode($x, $y, $node)
  {
    //节点圆的线颜色
    $black = imagecolorallocate($this->image, 0, 0, 0);
    $nodecolor = imagecolorallocate($this->image, $this->nodecolor[0], $this->nodecolor[1], $this->nodecolor[2]);
    //画节点圆
    imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
    //节点圆颜色填充
    imagefill($this->image, $x, $y, $nodecolor);
    //节点对应的数字
    imagestring($this->image, 4, $x, $y, $node->key, $black);
  }
  /**
   * 画平衡二叉树结点
   * @param $x，当前节点的x坐标 $y，当前节点的y坐标 $node，当前节点的引用
   * @return null
   */
  private function drawavlnode($x, $y, $node)
  {
    $black = imagecolorallocate($this->image, 0, 0, 0);
    $nodecolor = imagecolorallocate($this->image, $this->nodecolor[0], $this->nodecolor[1], $this->nodecolor[2]);
    imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
    imagefill($this->image, $x, $y, $nodecolor);
    imagestring($this->image, 4, $x, $y, $node->key . '(' . $node->bf . ')', $black);
  }
  /**
   * 画红黑树结点
   * @param $x，当前节点的x坐标 $y，当前节点的y坐标 $node，当前节点的引用
   * @return null
   */
  private function drawrbtnode($x, $y, $node)
  {
    $black = imagecolorallocate($this->image, 0, 0, 0);
    $gray = imagecolorallocate($this->image, 180, 180, 180);
    $pink = imagecolorallocate($this->image, 255, 192, 203);
    imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
    if ($node->isred == true) {
      imagefill($this->image, $x, $y, $pink);
    } else {
      imagefill($this->image, $x, $y, $gray);
    }
    imagestring($this->image, 4, $x, $y, $node->key, $black);
  }
}

好，现在我们来看看在客户端如何调用：

client.php

class client
{
  public static function main()
  {
    try {
      //实现文件的自动加载
      function autoload($class)
      {
        include strtolower($class) . '.php';
      }
      spl_autoload_register('autoload');
      $arr = array(62, 88, 58, 47, 35, 73, 51, 99, 37, 93);
//      $tree = new bst();  //搜索二叉树
      $tree = new avl();  //平衡二叉树
//      $tree = new rbt();  //红黑树
      $tree->init($arr);   //树的初始化
//      $tree->delete(62);
//      $tree->insert(100);
//      $tree->midorder();  //树的中序遍历（这也是调试的一个手段，看看数字是否从小到大排序）
      $image = new image($tree);
      $image->show();  //显示图像
    } catch (exception $e) {
      echo $e->getmessage();
    }
  }
}
client::main();

这里用到的那三个树的类如下：

二叉搜索树bst.php：

<?php
 /**
 * author:zhongjin
 * description: 二叉查找树
 */
//结点
class node
{
  public $key;
  public $parent;
  public $left;
  public $right;
  public function __construct($key)
  {
    $this->key = $key;
    $this->parent = null;
    $this->left = null;
    $this->right = null;
  }
}
//二叉搜索树
class bst
{
  public $root;
  /**
   * 初始化树结构
   * @param $arr 初始化树结构的数组
   * @return null
   */
  public function init($arr)
  {
    $this->root = new node($arr[0]);
    for ($i = 1; $i < count($arr); $i++) {
      $this->insert($arr[$i]);
    }
  }
  /**
   * （对内）中序遍历
   * @param $root （树或子树的）根节点
   * @return null
   */
  private function mid_order($root)
  {
    if ($root != null) {
      $this->mid_order($root->left);
      echo $root->key . " ";
      $this->mid_order($root->right);
    }
  }
  /**
   * （对外）中序遍历
   * @param null
   * @return null
   */
  public function midorder()
  {
    $this->mid_order($this->root);
  }
  /**
   * 查找树中是否存在$key对应的节点
   * @param $key 待搜索数字
   * @return $key对应的节点
   */
  function search($key)
  {
    $current = $this->root;
    while ($current != null) {
      if ($current->key == $key) {
        return $current;
      } elseif ($current->key > $key) {
        $current = $current->left;
      } else {
        $current = $current->right;
      }
    }
    return $current;
  }
  /**
   * 查找树中的最小关键字
   * @param $root 根节点
   * @return 最小关键字对应的节点
   */
  function search_min($root)
  {
    $current = $root;
    while ($current->left != null) {
      $current = $current->left;
    }
    return $current;
  }
  /**
   * 查找树中的最大关键字
   * @param $root 根节点
   * @return 最大关键字对应的节点
   */
  function search_max($root)
  {
    $current = $root;
    while ($current->right != null) {
      $current = $current->right;
    }
    return $current;
  }
  /**
   * 查找某个$key在中序遍历时的直接前驱节点
   * @param $x 待查找前驱节点的节点引用
   * @return 前驱节点引用
   */
  function predecessor($x)
  {
    //左子节点存在，直接返回左子节点的最右子节点
    if ($x->left != null) {
      return $this->search_max($x->left);
    }
    //否则查找其父节点，直到当前结点位于父节点的右边
    $p = $x->parent;
    //如果x是p的左孩子，说明p是x的后继，我们需要找的是p是x的前驱
    while ($p != null && $x == $p->left) {
      $x = $p;
      $p = $p->parent;
    }
    return $p;
  }
  /**
   * 查找某个$key在中序遍历时的直接后继节点
   * @param $x 待查找后继节点的节点引用
   * @return 后继节点引用
   */
  function successor($x)
  {
    if ($x->right != null) {
      return $this->search_min($x->right);
    }
    $p = $x->parent;
    while ($p != null && $x == $p->right) {
      $x = $p;
      $p = $p->parent;
    }
    return $p;
  }
  /**
   * 将$key插入树中
   * @param $key 待插入树的数字
   * @return null
   */
  function insert($key)
  {
    if (!is_null($this->search($key))) {
      throw new exception('结点' . $key . '已存在，不可插入！');
    }
    $root = $this->root;
    $inode = new node($key);
    $current = $root;
    $prenode = null;
    //为$inode找到合适的插入位置
    while ($current != null) {
      $prenode = $current;
      if ($current->key > $inode->key) {
        $current = $current->left;
      } else {
        $current = $current->right;
      }
    }
    $inode->parent = $prenode;
    //如果$prenode == null， 则证明树是空树
    if ($prenode == null) {
      $this->root = $inode;
    } else {
      if ($inode->key < $prenode->key) {
        $prenode->left = $inode;
      } else {
        $prenode->right = $inode;
      }
    }
    //return $root;
  }
  /**
   * 在树中删除$key对应的节点
   * @param $key 待删除节点的数字
   * @return null
   */
  function delete($key)
  {
    if (is_null($this->search($key))) {
      throw new exception('结点' . $key . "不存在，删除失败！");
    }
    $root = $this->root;
    $dnode = $this->search($key);
    if ($dnode->left == null || $dnode->right == null) { #如果待删除结点无子节点或只有一个子节点，则c = dnode
      $c = $dnode;
    } else { #如果待删除结点有两个子节点，c置为dnode的直接后继，以待最后将待删除结点的值换为其后继的值
      $c = $this->successor($dnode);
    }
    //无论前面情况如何，到最后c只剩下一边子结点
    if ($c->left != null) {
      $s = $c->left;
    } else {
      $s = $c->right;
    }
    if ($s != null) { #将c的子节点的父母结点置为c的父母结点，此处c只可能有1个子节点，因为如果c有两个子节点，则c不可能是dnode的直接后继
      $s->parent = $c->parent;
    }
    if ($c->parent == null) { #如果c的父母为空，说明c=dnode是根节点，删除根节点后直接将根节点置为根节点的子节点，此处dnode是根节点，且拥有两个子节点，则c是dnode的后继结点，c的父母就不会为空，就不会进入这个if
      $this->root = $s;
    } else if ($c == $c->parent->left) { #如果c是其父节点的左右子节点，则将c父母的左右子节点置为c的左右子节点
      $c->parent->left = $s;
    } else {
      $c->parent->right = $s;
    }
    #如果c!=dnode，说明c是dnode的后继结点，交换c和dnode的key值
    if ($c != $dnode) {
      $dnode->key = $c->key;
    }
    #返回根节点
//    return $root;
  }
  /**
   * （对内）获取树的深度
   * @param $root 根节点
   * @return 树的深度
   */
  private function getdepth($root)
  {
    if ($root == null) {
      return 0;
    }
    $dl = $this->getdepth($root->left);
    $dr = $this->getdepth($root->right);
    return ($dl > $dr ? $dl : $dr) + 1;
  }
  /**
   * （对外）获取树的深度
   * @param null
   * @return null
   */
  public function depth()
  {
    return $this->getdepth($this->root);
  }
}
?>

平衡二叉树avl.php：

<?php
 /**
 * author:zhongjin
 * description: 平衡二叉树
 */
//结点
class node
{
  public $key;
  public $parent;
  public $left;
  public $right;
  public $bf; //平衡因子
  public function __construct($key)
  {
    $this->key = $key;
    $this->parent = null;
    $this->left = null;
    $this->right = null;
    $this->bf = 0;
  }
}
//平衡二叉树
class avl
{
  public $root;
  const lh = +1; //左高
  const eh = 0;  //等高
  const rh = -1; //右高
  /**
   * 初始化树结构
   * @param $arr 初始化树结构的数组
   * @return null
   */
  public function init($arr)
  {
    $this->root = new node($arr[0]);
    for ($i = 1; $i < count($arr); $i++) {
      $this->insert($arr[$i]);
    }
  }
  /**
   * （对内）中序遍历
   * @param $root （树或子树的）根节点
   * @return null
   */
  private function mid_order($root)
  {
    if ($root != null) {
      $this->mid_order($root->left);
      echo $root->key . "-" . $root->bf . " ";
      $this->mid_order($root->right);
    }
  }
  /**
   * （对外）中序遍历
   * @param null
   * @return null
   */
  public function midorder()
  {
    $this->mid_order($this->root);
  }
  /**
   * 将以$root为根节点的最小不平衡二叉树做右旋处理
   * @param $root（树或子树）根节点
   * @return null
   */
  private function r_rotate($root)
  {
    $l = $root->left;
    if (!is_null($root->parent)) {
      $p = $root->parent;
      if ($root == $p->left) {
        $p->left = $l;
      } else {
        $p->right = $l;
      }
      $l->parent = $p;
    } else {
      $l->parent = null;
    }
    $root->parent = $l;
    $root->left = $l->right;
    $l->right = $root;
    //这句必须啊！
    if ($l->parent == null) {
      $this->root = $l;
    }
  }
  /**
   * 将以$root为根节点的最小不平衡二叉树做左旋处理
   * @param $root（树或子树）根节点
   * @return null
   */
  private function l_rotate($root)
  {
    $r = $root->right;
    if (!is_null($root->parent)) {
      $p = $root->parent;
      if ($root == $p->left) {
        $p->left = $r;
      } else {
        $p->right = $r;
      }
      $r->parent = $p;
    } else {
      $r->parent = null;
    }
    $root->parent = $r;
    $root->right = $r->left;
    $r->left = $root;
    //这句必须啊！
    if ($r->parent == null) {
      $this->root = $r;
    }
  }
  /**
   * 对以$root所指结点为根节点的二叉树作左平衡处理
   * @param $root（树或子树）根节点
   * @return null
   */
  public function leftbalance($root)
  {
    $l = $root->left;
    $l_bf = $l->bf;
    switch ($l_bf) {
      //检查root的左子树的平衡度，并作相应的平衡处理
      case self::lh:  //新结点插入在root的左孩子的左子树上，要做单右旋处理
        $root->bf = $l->bf = self::eh;
        $this->r_rotate($root);
        break;
      case self::rh:  //新节点插入在root的左孩子的右子树上，要做双旋处理
        $l_r = $l->right;  //root左孩子的右子树根
        $l_r_bf = $l_r->bf;
        //修改root及其左孩子的平衡因子
        switch ($l_r_bf) {
          case self::lh:
            $root->bf = self::rh;
            $l->bf = self::eh;
            break;
          case self::eh:
            $root->bf = $l->bf = self::eh;
            break;
          case self::rh:
            $root->bf = self::eh;
            $l->bf = self::lh;
            break;
        }
        $l_r->bf = self::eh;
        //对root的左子树作左平衡处理
        $this->l_rotate($l);
        //对root作右平衡处理
        $this->r_rotate($root);
    }
  }
  /**
   * 对以$root所指结点为根节点的二叉树作右平衡处理
   * @param $root（树或子树）根节点
   * @return null
   */
  public function rightbalance($root)
  {
    $r = $root->right;
    $r_bf = $r->bf;
    switch ($r_bf) {
      //检查root的右子树的平衡度，并作相应的平衡处理
      case self::rh:  //新结点插入在root的右孩子的右子树上，要做单左旋处理
        $root->bf = $r->bf = self::eh;
        $this->l_rotate($root);
        break;
      case self::lh:  //新节点插入在root的右孩子的左子树上，要做双旋处理
        $r_l = $r->left;  //root右孩子的左子树根
        $r_l_bf = $r_l->bf;
        //修改root及其右孩子的平衡因子
        switch ($r_l_bf) {
          case self::rh:
            $root->bf = self::lh;
            $r->bf = self::eh;
            break;
          case self::eh:
            $root->bf = $r->bf = self::eh;
            break;
          case self::lh:
            $root->bf = self::eh;
            $r->bf = self::rh;
            break;
        }
        $r_l->bf = self::eh;
        //对root的右子树作右平衡处理
        $this->r_rotate($r);
        //对root作左平衡处理
        $this->l_rotate($root);
    }
  }
  /**
   * 查找树中是否存在$key对应的节点
   * @param $key 待搜索数字
   * @return $key对应的节点
   */
  public function search($key)
  {
    $current = $this->root;
    while ($current != null) {
      if ($current->key == $key) {
        return $current;
      } elseif ($current->key > $key) {
        $current = $current->left;
      } else {
        $current = $current->right;
      }
    }
    return $current;
  }
  /**
   * 查找树中的最小关键字
   * @param $root 根节点
   * @return 最小关键字对应的节点
   */
  function search_min($root)
  {
    $current = $root;
    while ($current->left != null) {
      $current = $current->left;
    }
    return $current;
  }
  /**
   * 查找树中的最大关键字
   * @param $root 根节点
   * @return 最大关键字对应的节点
   */
  function search_max($root)
  {
    $current = $root;
    while ($current->right != null) {
      $current = $current->right;
    }
    return $current;
  }
  /**
   * 查找某个$key在中序遍历时的直接前驱节点
   * @param $x 待查找前驱节点的节点引用
   * @return 前驱节点引用
   */
  private function predecessor($x)
  {
    //左子节点存在，直接返回左子节点的最右子节点
    if ($x->left != null) {
      return $this->search_max($x->left);
    }
    //否则查找其父节点，直到当前结点位于父节点的右边
    $p = $x->parent;
    //如果x是p的左孩子，说明p是x的后继，我们需要找的是p是x的前驱
    while ($p != null && $x == $p->left) {
      $x = $p;
      $p = $p->parent;
    }
    return $p;
  }
  /**
   * 查找某个$key在中序遍历时的直接后继节点
   * @param $x 待查找后继节点的节点引用
   * @return 后继节点引用
   */
  private function successor($x)
  {
    if ($x->left != null) {
      return $this->search_min($x->right);
    }
    $p = $x->parent;
    while ($p != null && $x == $p->right) {
      $x = $p;
      $p = $p->parent;
    }
    return $p;
  }
  /**
   * （对内）插入结点，如果结点不存在则插入，失去平衡要做平衡处理
   * @param $root 根节点 $key 待插入树的数字
   * @return null
   */
  private function insert_node(&$root, $key)
  {
    //找到了插入的位置，插入新节点
    if (is_null($root)) {
      $root = new node($key);
      //插入结点成功
      return true;
    } else {
      //在树中已经存在和$key相等的结点
      if ($key == $root->key) {
        //插入节点失败
        return false;
      } //在root的左子树中继续搜索
      elseif ($key < $root->key) {
        //插入左子树失败
        if (!($this->insert_node($root->left, $key))) {
          //树未长高
          return false;
        }
        //成功插入,修改平衡因子
        if (is_null($root->left->parent)) {
          $root->left->parent = $root;
        }
        switch ($root->bf) {
          //原来左右子树等高，现在左子树增高而树增高
          case self::eh:
            $root->bf = self::lh;
            //树长高
            return true;
            break;
          //原来左子树比右子树高，需要做左平衡处理
          case self::lh:
            $this->leftbalance($root);
            //平衡后，树并未长高
            return false;
            break;
          //原来右子树比左子树高，现在左右子树等高
          case self::rh:
            $root->bf = self::eh;
            //树并未长高
            return false;
            break;
        }
      } //在root的右子树中继续搜索
      else {
        //插入右子树失败
        if (!$this->insert_node($root->right, $key)) {
          //树未长高
          return false;
        }
        //成功插入,修改平衡因子
        if (is_null($root->right->parent)) {
          $root->right->parent = $root;
        }
        switch ($root->bf) {
          //原来左右子树等高，现在右子树增高而树增高
          case self::eh:
            $root->bf = self::rh;
            //树长高
            return true;
            break;
          //原来左子树比右子树高，现在左右子树等高
          case self::lh:
            $root->bf = self::eh;
            return false;
            break;
          //原来右子树比左子树高，要做右平衡处理
          case self::rh:
            $this->rightbalance($root);
            //树并未长高
            return false;
            break;
        }
      }
    }
  }
  /**
   * （对外）将$key插入树中
   * @param $key 待插入树的数字
   * @return null
   */
  public function insert($key)
  {
    $this->insert_node($this->root, $key);
  }
  /**
   * 获取待删除的节点（删除的最终节点）
   * @param $key 待删除的数字
   * @return 最终被删除的节点
   */
  private function get_del_node($key)
  {
    $dnode = $this->search($key);
    if ($dnode == null) {
      throw new exception("结点不存在！");
      return;
    }
    if ($dnode->left == null || $dnode->right == null) { #如果待删除结点无子节点或只有一个子节点，则c = dnode
      $c = $dnode;
    } else { #如果待删除结点有两个子节点，c置为dnode的直接后继，以待最后将待删除结点的值换为其后继的值
      $c = $this->successor($dnode);
    }
    $dnode->key = $c->key;
    return $c;
  }
  /**
   * （对内）删除指定节点，处理该结点往上结点的平衡因子
   * @param $node 最终该被删除的节点
   * @return null
   */
  private function del_node($node)
  {
    if ($node == $this->root) {
      $this->root = null;
      return;
    }
    $current = $node;
    //现在的node只有两种情况，要么只有一个子节点，要么没有子节点
    $p = $current->parent;
    //删除一个结点，第一个父节点的平衡都肯定会发生变化
    $lower = true;
    while ($lower == true && !is_null($p)) {
      //待删除结点是左节点
      if ($current == $p->left) {
        if($current == $node){
          if (!is_null($current->left)) {
            $p->left = $current->left;
          } else {
            $p->left = $current->left;
          }
        }
        $p_bf = $p->bf;
        switch ($p_bf) {
          case self::lh:
            $p->bf = self::eh;
            $lower = true;
            $current = $p;
            $p = $current->parent;
            break;
          case self::eh:
            $p->bf = self::rh;
            $lower = false;
            break;
          case self::rh:
            $this->rightbalance($p);
            $lower = true;
            $current = $p->parent;
            $p = $current->parent;
            break;
        }
      } //右结点
      else {
        if($current == $node){
          if (!is_null($current->left)) {
            $p->right = $current->left;
          } else {
            $p->right = $current->left;
          }
        }
        $p_bf = $p->bf;
        switch ($p_bf) {
          case self::lh:
            $this->leftbalance($p);
            $lower = true;
            $current = $p->parent;
            $p = $current->parent;
            break;
          case self::eh:
            $p->bf = self::lh;
            $lower = false;
            break;
          case self::rh:
            $p->bf = self::lh;
            $lower = true;
            $current = $p;
            $p = $current->parent;
            break;
        }
      }
    }
  }
  /**
   * （对外）删除指定节点
   * @param $key 删除节点的key值
   * @return null
   */
  public function delete($key)
  {
    $del_node = $this->get_del_node($key);
    $this->del_node($del_node);
  }
  /**
   * （对内）获取树的深度
   * @param $root 根节点
   * @return 树的深度
   */
  private function getdepth($root)
  {
    if ($root == null) {
      return 0;
    }
    $dl = $this->getdepth($root->left);
    $dr = $this->getdepth($root->right);
    return ($dl > $dr ? $dl : $dr) + 1;
  }
  /**
   * （对外）获取树的深度
   * @param null
   * @return null
   */
  public function depth()
  {
    return $this->getdepth($this->root);
  }
}
?>

红黑树rbt.php：

<?php
 /**
 * author:zhongjin
 * description: 红黑树
 */
//结点
class node
{
  public $key;
  public $parent;
  public $left;
  public $right;
  public $isred; //分辨红节点或黑节点
  public function __construct($key, $isred = true)
  {
    $this->key = $key;
    $this->parent = null;
    $this->left = null;
    $this->right = null;
    //插入结点默认是红色
    $this->isred = $isred;
  }
}
//红黑树
class rbt
{
  public $root;
  /**
   * 初始化树结构
   * @param $arr 初始化树结构的数组
   * @return null
   */
  public function init($arr)
  {
    //根节点必须是黑色
    $this->root = new node($arr[0], false);
    for ($i = 1; $i < count($arr); $i++) {
      $this->insert($arr[$i]);
    }
  }
  /**
   * （对内）中序遍历
   * @param $root （树或子树的）根节点
   * @return null
   */
  private function mid_order($root)
  {
    if ($root != null) {
      $this->mid_order($root->left);
      echo $root->key . "-" . ($root->isred ? 'r' : 'b') . ' ';
      $this->mid_order($root->right);
    }
  }
  /**
   * （对外）中序遍历
   * @param null
   * @return null
   */
  public function midorder()
  {
    $this->mid_order($this->root);
  }
  /**
   * 查找树中是否存在$key对应的节点
   * @param $key 待搜索数字
   * @return $key对应的节点
   */
  function search($key)
  {
    $current = $this->root;
    while ($current != null) {
      if ($current->key == $key) {
        return $current;
      } elseif ($current->key > $key) {
        $current = $current->left;
      } else {
        $current = $current->right;
      }
    }
    //结点不存在
    return $current;
  }
  /**
   * 将以$root为根节点的最小不平衡二叉树做右旋处理
   * @param $root（树或子树）根节点
   * @return null
   */
  private function r_rotate($root)
  {
    $l = $root->left;
    if (!is_null($root->parent)) {
      $p = $root->parent;
      if($root == $p->left){
        $p->left = $l;
      }else{
        $p->right = $l;
      }
      $l->parent = $p;
    } else {
      $l->parent = null;
    }
    $root->parent = $l;
    $root->left = $l->right;
    $l->right = $root;
    //这句必须啊！
    if ($l->parent == null) {
      $this->root = $l;
    }
  }
  /**
   * 将以$root为根节点的最小不平衡二叉树做左旋处理
   * @param $root（树或子树）根节点
   * @return null
   */
  private function l_rotate($root)
  {
    $r = $root->right;
    if (!is_null($root->parent)) {
      $p = $root->parent;
      if($root == $p->right){
        $p->right = $r;
      }else{
        $p->left = $r;
      }
      $r->parent = $p;
    } else {
      $r->parent = null;
    }
    $root->parent = $r;
    $root->right = $r->left;
    $r->left = $root;
    //这句必须啊！
    if ($r->parent == null) {
      $this->root = $r;
    }
  }
  /**
   * 查找树中的最小关键字
   * @param $root 根节点
   * @return 最小关键字对应的节点
   */
  function search_min($root)
  {
    $current = $root;
    while ($current->left != null) {
      $current = $current->left;
    }
    return $current;
  }
  /**
   * 查找树中的最大关键字
   * @param $root 根节点
   * @return 最大关键字对应的节点
   */
  function search_max($root)
  {
    $current = $root;
    while ($current->right != null) {
      $current = $current->right;
    }
    return $current;
  }
  /**
   * 查找某个$key在中序遍历时的直接前驱节点
   * @param $x 待查找前驱节点的节点引用
   * @return 前驱节点引用
   */
  function predecessor($x)
  {
    //左子节点存在，直接返回左子节点的最右子节点
    if ($x->left != null) {
      return $this->search_max($x->left);
    }
    //否则查找其父节点，直到当前结点位于父节点的右边
    $p = $x->parent;
    //如果x是p的左孩子，说明p是x的后继，我们需要找的是p是x的前驱
    while ($p != null && $x == $p->left) {
      $x = $p;
      $p = $p->parent;
    }
    return $p;
  }
  /**
   * 查找某个$key在中序遍历时的直接后继节点
   * @param $x 待查找后继节点的节点引用
   * @return 后继节点引用
   */
  function successor($x)
  {
    if ($x->left != null) {
      return $this->search_min($x->right);
    }
    $p = $x->parent;
    while ($p != null && $x == $p->right) {
      $x = $p;
      $p = $p->parent;
    }
    return $p;
  }
  /**
   * 将$key插入树中
   * @param $key 待插入树的数字
   * @return null
   */
  public function insert($key)
  {
    if (!is_null($this->search($key))) {
      throw new exception('结点' . $key . '已存在，不可插入！');
    }
    $root = $this->root;
    $inode = new node($key);
    $current = $root;
    $prenode = null;
    //为$inode找到合适的插入位置
    while ($current != null) {
      $prenode = $current;
      if ($current->key > $inode->key) {
        $current = $current->left;
      } else {
        $current = $current->right;
      }
    }
    $inode->parent = $prenode;
    //如果$prenode == null， 则证明树是空树
    if ($prenode == null) {
      $this->root = $inode;
    } else {
      if ($inode->key < $prenode->key) {
        $prenode->left = $inode;
      } else {
        $prenode->right = $inode;
      }
    }
    //将它重新修正为一颗红黑树
    $this->insertfixup($inode);
  }
  /**
   * 对插入节点的位置及往上的位置进行颜色调整
   * @param $inode 插入的节点
   * @return null
   */
  private function insertfixup($inode)
  {
    //情况一：需要调整条件，父节点存在且父节点的颜色是红色
    while (($parent = $inode->parent) != null && $parent->isred == true) {
      //祖父结点：
      $gparent = $parent->parent;
      //如果父节点是祖父结点的左子结点，下面的else与此相反
      if ($parent == $gparent->left) {
        //叔叔结点
        $uncle = $gparent->right;
        //case1:叔叔结点也是红色
        if ($uncle != null && $uncle->isred == true) {
          //将父节点和叔叔结点都涂黑，将祖父结点涂红
          $parent->isred = false;
          $uncle->isred = false;
          $gparent->isred = true;
          //将新节点指向祖父节点（现在祖父结点变红，可以看作新节点存在）
          $inode = $gparent;
          //继续while循环，重新判断
          continue;  //经过这一步之后，组父节点作为新节点存在（跳到case2）
        }
        //case2:叔叔结点是黑色，且当前结点是右子节点
        if ($inode == $parent->right) {
          //以父节点作为旋转结点做左旋转处理
          $this->l_rotate($parent);
          //在树中实际上已经转换，但是这里的变量的指向还没交换，
          //将父节点和字节调换一下，为下面右旋做准备
          $temp = $parent;
          $parent = $inode;
          $inode = $temp;
        }
        //case3:叔叔结点是黑色，而且当前结点是父节点的左子节点
        $parent->isred = false;
        $gparent->isred = true;
        $this->r_rotate($gparent);
      } //如果父节点是祖父结点的右子结点，与上面完全相反
      else {
        //叔叔结点
        $uncle = $gparent->left;
        //case1:叔叔结点也是红色
        if ($uncle != null && $uncle->isred == true) {
          //将父节点和叔叔结点都涂黑，将祖父结点涂红
          $parent->isred = false;
          $uncle->isred = false;
          $gparent->isred = true;
          //将新节点指向祖父节点（现在祖父结点变红，可以看作新节点存在）
          $inode = $gparent;
          //继续while循环，重新判断
          continue;  //经过这一步之后，组父节点作为新节点存在（跳到case2）
        }
        //case2:叔叔结点是黑色，且当前结点是左子节点
        if ($inode == $parent->left) {
          //以父节点作为旋转结点做右旋转处理
          $this->r_rotate($parent);
          //在树中实际上已经转换，但是这里的变量的指向还没交换，
          //将父节点和字节调换一下，为下面右旋做准备
          $temp = $parent;
          $parent = $inode;
          $inode = $temp;
        }
        //case3:叔叔结点是黑色，而且当前结点是父节点的右子节点
        $parent->isred = false;
        $gparent->isred = true;
        $this->l_rotate($gparent);
      }
    }
    //情况二：原树是根节点（父节点为空），则只需将根节点涂黑
    if ($inode == $this->root) {
      $this->root->isred = false;
      return;
    }
    //情况三：插入节点的父节点是黑色，则什么也不用做
    if ($inode->parent != null && $inode->parent->isred == false) {
      return;
    }
  }
  /**
   * （对外）删除指定节点
   * @param $key 删除节点的key值
   * @return null
   */
  function delete($key)
  {
    if (is_null($this->search($key))) {
      throw new exception('结点' . $key . "不存在，删除失败！");
    }
    $dnode = $this->search($key);
    if ($dnode->left == null || $dnode->right == null) { #如果待删除结点无子节点或只有一个子节点，则c = dnode
      $c = $dnode;
    } else { #如果待删除结点有两个子节点，c置为dnode的直接后继，以待最后将待删除结点的值换为其后继的值
      $c = $this->successor($dnode);
    }
    //为了后面颜色处理做准备
    $parent = $c->parent;
    //无论前面情况如何，到最后c只剩下一边子结点
    if ($c->left != null) {  //这里不会出现，除非选择的是删除结点的前驱
      $s = $c->left;
    } else {
      $s = $c->right;
    }
    if ($s != null) { #将c的子节点的父母结点置为c的父母结点，此处c只可能有1个子节点，因为如果c有两个子节点，则c不可能是dnode的直接后继
      $s->parent = $c->parent;
    }
    if ($c->parent == null) { #如果c的父母为空，说明c=dnode是根节点，删除根节点后直接将根节点置为根节点的子节点，此处dnode是根节点，且拥有两个子节点，则c是dnode的后继结点，c的父母就不会为空，就不会进入这个if
      $this->root = $s;
    } else if ($c == $c->parent->left) { #如果c是其父节点的左右子节点，则将c父母的左右子节点置为c的左右子节点
      $c->parent->left = $s;
    } else {
      $c->parent->right = $s;
    }
    $dnode->key = $c->key;
    $node = $s;
    //c的结点颜色是黑色，那么会影响路径上的黑色结点的数量，必须进行调整
    if ($c->isred == false) {
      $this->deletefixup($node,$parent);
    }
  }
  /**
   * 删除节点后对接点周围的其他节点进行调整
   * @param $key 删除节点的子节点和父节点
   * @return null
   */
  private function deletefixup($node,$parent)
  {
    //如果待删结点的子节点为红色，直接将子节点涂黑
    if ($node != null && $node->isred == true) {
      $node->isred = false;
      return;
    }
    //如果是根节点，那就直接将根节点置为黑色即可
    while (($node == null || $node->isred == false) && ($node != $this->root)) {
      //node是父节点的左子节点，下面else与这里相反
      if ($node == $parent->left) {
        $brother = $parent->right;
        //case1:兄弟结点颜色是红色（父节点和兄弟孩子结点都是黑色）
        //将父节点涂红，将兄弟结点涂黑，然后对父节点进行左旋处理（经过这一步，情况转换为兄弟结点颜色为黑色的情况）
        if ($brother->isred == true) {
          $brother->isred = false;
          $parent->isred = true;
          $this->l_rotate($parent);
          //将情况转化为其他的情况
          $brother = $parent->right; //在左旋处理后，$parent->right指向的是原来兄弟结点的左子节点
        }
        //以下是兄弟结点为黑色的情况
        //case2:兄弟结点是黑色，且兄弟结点的两个子节点都是黑色
        //将兄弟结点涂红，将当前结点指向其父节点，将其父节点指向当前结点的祖父结点。
        if (($brother->left == null || $brother->left->isred == false) && ($brother->right == null || $brother->right->isred == false)) {
          $brother->isred = true;
          $node = $parent;
          $parent = $node->parent;
        } else {
          //case3:兄弟结点是黑色，兄弟结点的左子节点是红色，右子节点为黑色
          //将兄弟结点涂红，将兄弟节点的左子节点涂黑，然后对兄弟结点做右旋处理（经过这一步，情况转换为兄弟结点颜色为黑色，右子节点为红色的情况）
          if ($brother->right == null || $brother->right->isred == false) {
            $brother->isred = true;
            $brother->left->isred = false;
            $this->r_rotate($brother);
            //将情况转换为其他情况
            $brother = $parent->right;
          }
          //case4:兄弟结点是黑色，且兄弟结点的右子节点为红色，左子节点为任意颜色
          //将兄弟节点涂成父节点的颜色，再把父节点涂黑，将兄弟结点的右子节点涂黑，然后对父节点做左旋处理
          $brother->isred = $parent->isred;
          $parent->isred = false;
          $brother->right->isred = false;
          $this->l_rotate($parent);
          //到了第四种情况，已经是最基本的情况了，可以直接退出了
          $node = $this->root;
          break;
        }
      } //node是父节点的右子节点
      else {
        $brother = $parent->left;
        //case1:兄弟结点颜色是红色（父节点和兄弟孩子结点都是黑色）
        //将父节点涂红，将兄弟结点涂黑，然后对父节点进行右旋处理（经过这一步，情况转换为兄弟结点颜色为黑色的情况）
        if ($brother->isred == true) {
          $brother->isred = false;
          $parent->isred = true;
          $this->r_rotate($parent);
          //将情况转化为其他的情况
          $brother = $parent->left; //在右旋处理后，$parent->left指向的是原来兄弟结点的右子节点
        }
        //以下是兄弟结点为黑色的情况
        //case2:兄弟结点是黑色，且兄弟结点的两个子节点都是黑色
        //将兄弟结点涂红，将当前结点指向其父节点，将其父节点指向当前结点的祖父结点。
        if (($brother->left == null || $brother->left->isred == false) && ($brother->right == null || $brother->right->isred == false)) {
          $brother->isred = true;
          $node = $parent;
          $parent = $node->parent;
        } else {
          //case3:兄弟结点是黑色，兄弟结点的右子节点是红色，左子节点为黑色
          //将兄弟结点涂红，将兄弟节点的左子节点涂黑，然后对兄弟结点做左旋处理（经过这一步，情况转换为兄弟结点颜色为黑色，右子节点为红色的情况）
          if ($brother->left == null || $brother->left->isred == false) {
            $brother->isred = true;
            $brother->right = false;
            $this->l_rotate($brother);
            //将情况转换为其他情况
            $brother = $parent->left;
          }
          //case4:兄弟结点是黑色，且兄弟结点的左子节点为红色，右子节点为任意颜色
          //将兄弟节点涂成父节点的颜色，再把父节点涂黑，将兄弟结点的右子节点涂黑，然后对父节点左左旋处理
          $brother->isred = $parent->isred;
          $parent->isred = false;
          $brother->left->isred = false;
          $this->r_rotate($parent);
          $node = $this->root;
          break;
        }
      }
    }
    if ($node != null) {
      $this->root->isred = false;
    }
  }
  /**
   * （对内）获取树的深度
   * @param $root 根节点
   * @return 树的深度
   */
  private function getdepth($root)
  {
    if ($root == null) {
      return 0;
    }
    $dl = $this->getdepth($root->left);
    $dr = $this->getdepth($root->right);
    return ($dl > $dr ? $dl : $dr) + 1;
  }
  /**
   * （对外）获取树的深度
   * @param null
   * @return null
   */
  public function depth()
  {
    return $this->getdepth($this->root);
  }
}
?>

更多关于php相关内容感兴趣的读者可查看本站专题：《php数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《php数组(array)操作技巧大全》、《php常用遍历算法与技巧总结》及《php数学运算技巧总结》

希望本文所述对大家php程序设计有所帮助。