Chinaunix首页 | 论坛 | 博客
  • 博客访问: 892087
  • 博文数量: 91
  • 博客积分: 803
  • 博客等级: 准尉
  • 技术积分: 1051
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-24 13:42
文章分类

全部博文(91)

文章存档

2021年(1)

2020年(4)

2019年(4)

2018年(9)

2017年(11)

2016年(11)

2015年(6)

2014年(3)

2013年(28)

2012年(14)

分类: PHP

2020-09-08 15:42:12


点击(此处)折叠或打开

  1. <?php
  2. class Node {
  3.     public $left = null;
  4.     public $right = null;
  5.     public $height = null;
  6.     public $data = '';

  7.     public function __construct($data) {
  8.         $this->data = $data;
  9.         $this->height = 1;
  10.     }

  11.     /**
  12.      * 计算节点高度 (叶子 节点1 每往上一层 + 1)
  13.      * 在插入结点时, 沿插入的路径更新结点的高度值
  14.      * 在删除结点时(delete),沿删除的路径更新结点的高度值
  15.      * @param $node
  16.      * @return int|mixed
  17.      */
  18.     function getHeight($node) {
  19.         if ($node == null) {
  20.             return 0;
  21.         }
  22.         return max($node->getHeight($node->left),$node->getHeight($node->right)) +1;
  23.     }

  24.     /**
  25.      * 获取平衡因子
  26.      * @param $node
  27.      * @return int
  28.      */
  29.     function getBf($node) {
  30.         if ($node == null) {
  31.             return 0;
  32.         }
  33.         $leftHeight = $node->left->height ?? 0;
  34.         $rightHeight = $node->right->height ?? 0;
  35.         return $leftHeight - $rightHeight;
  36.     }

  37.     /**
  38.      * 右旋操作
  39.      * @param $node
  40.      * @return mixed
  41.      */
  42.     function treeRotateRight($node) {
  43.         //获取左子节点
  44.         $left = $node->left;

  45.         //将要被抛弃的节点 转为旋转后的root的左孩子
  46.         $node->left = $left->right;
  47.         //$left 作为根节点
  48.         $left->right = $node;

  49.         $left->height = $this->getHeight($left);
  50.         $node->height = $this->getHeight($node);

  51.         return $left;
  52.     }

  53.     /**
  54.      * 左旋操作
  55.      * @param $nodesz
  56.      * @return mixed
  57.      */
  58.     function treeRotateLeft($node) {
  59.         $right = $node->right;
  60.         $node->right = $right->left;
  61.         $right->left = $node;

  62.         $right->height = $this->getHeight($right);
  63.         $node->height = $this->getHeight($node);

  64.         return $right;
  65.     }

  66.     /**
  67.      * 平衡节点
  68.      * @param $node
  69.      * @return mixed
  70.      */
  71.     function balance($node) {
  72.         $factor = $this->getBf($node);
  73.         if($factor > 1 && $this->getBf($node->left) > 0 ){//LL
  74.             return $this->treeRotateRight($node);
  75.         } elseif ($factor > 1 && $this->getBf($node->left) <= 0) {
  76.             //LR 先左旋 left子节点
  77.             $temp = $this->treeRotateLeft($node->left);
  78.             //再右旋
  79.             return $this->treeRotateRight($temp);
  80.         } elseif ($factor < -1 && $this->getBf($node->right) <= 0) {
  81.             return $this->treeRotateLeft($node);
  82.         } elseif ($factor < -1 && $this->getBf($node->right) > 0 ) {
  83.             $temp = $this->treeRotateRight($node->right);
  84.             return $this->treeRotateLeft($temp);
  85.         } else {
  86.             return $node;
  87.         }
  88.     }

  89.     function add($node,$value) {
  90.         if($node == null) {
  91.             $node = new Node($value);
  92.             return $node;
  93.         } elseif ($value > $node->data) {
  94.             $node->right = $this->add($node->right,$value);
  95.         } elseif ($value < $node->data) {
  96.             $node->left = $this->add($node->left,$value);
  97.         } else {

  98.         }
  99.         //插入新节点后重新计算节点高度
  100.         $node->height = max($node->getHeight($node->left),$node->getHeight($node->right)) + 1;

  101.         //计算节点的平衡因子
  102.         $bf = $node->getBf($node);
  103.         if(abs($bf) > 1) {
  104.             $node = $node->balance($node);
  105.         }
  106.         return $node;
  107.     }

  108. }

  109. /**
  110.  * 中序遍历
  111.  * @param $tree
  112.  */
  113. function inOrder($tree) {
  114.     if($tree === null) {
  115.         return;
  116.     }
  117.     inOrder($tree->left);
  118.     var_dump($tree->data);
  119.     inOrder($tree->right);
  120. }

  121. //根节点
  122. $root = new Node(5);
  123. $root = $root->add($root,4);
  124. $root = $root->add($root,3);
  125. $root = $root->add($root,2);
  126. $root = $root->add($root,1);
  127. $root = $root->add($root,0);
  128. $root = $root->add($root,-1);
  129. $root = $root->add($root,-2);
  130. $root = $root->add($root,10000);
  131. $root = $root->add($root,100001);
  132. inOrder($root);
  133. print_r($root);
  134. ?>

阅读(22078) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~