无为清净楼资源网

PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】
网络编程 2024/11/18 佚名
3 2
无为清净楼资源网 Design By www.qnjia.com

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

前言：

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

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

效果显示：

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

1、搜索二叉树：

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

2、平衡二叉树：

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

3、红黑树：

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

上代码：

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

image.php 文件：

<"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：

<" ";
      $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 "htmlcode">



<"-" . $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 "htmlcode">



<"-" . ($root->IsRed "不存在，删除失败！");
    }
    $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 "_blank" href="https://www.jb51.net/Special/614.htm">PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》


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


                                

                                

                                     

                                

                                    标签：
                                        
PHP,绘制,二叉树,图形,二叉搜索树,平衡树,红黑树

                                     

                                
无为清净楼资源网 Design By www.qnjia.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
无为清净楼资源网 Design By www.qnjia.com
www.qnjia.com 无为清净楼资源网
139,976互联网资源
144,792高清电影
21,817无损音乐
631,128技术资源

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接