php通過前序遍歷樹實現無需遞歸的無限極分類

本文實例講述了php通過前序遍歷樹實現無需遞歸的無限極分類。分享給大家供大家參考。具體如下：

大家通常都是使用遞歸實現無限極分類都知道遞歸效率很低，下面介紹一種改進的前序遍歷樹算法，不適用遞歸實現無限極分類，在大數據量實現樹狀層級結構的時候效率更高。

sql代碼如下：

CREATE TABLE IF NOT EXISTS `category` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `title` varchar(50) NOT NULL,
 `lft` int(11) NOT NULL,
 `rgt` int(11) NOT NULL,
 `order` int(11) NOT NULL COMMENT '排序',
 `create_time` int(11) NOT NULL,
 PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=12 ;
--
-- 轉存表中的數據 `category`
--
INSERT INTO `category` (`id`, `title`, `lft`, `rgt`, `order`, `create_time`) VALUES
(1, '頂級欄目', 1, 20, 1, 1261964806),
(2, '編輯後的分類', 16, 19, 50, 1264586212),
(4, '公司產品', 10, 15, 50, 1264586249),
(5, '榮譽資質', 8, 9, 50, 1264586270),
(6, '資料下載', 6, 7, 50, 1264586295),
(7, '人才招聘', 4, 5, 50, 1264586314),
(8, '留言板', 2, 3, 50, 1264586884),
(9, '總裁', 17, 18, 50, 1267771951),
(10, '新的分類的子分類', 11, 14, 0, 1400044841),
(11, 'PHP點點通-http://www.phpddt.com', 12, 13, 0, 1400044901);

php代碼如下：

<?php
/**
 * 純屬測試
 * 
 * @author Mckee
 * @link http://www.phpddt.com
 */
class Category extends CI_Controller {
  public function __construct()
  {
    parent::__construct();
    $this->load->database();
  }
  public function view()
  {
    $lists = $this->db->order_by('lft', 'asc')->get('category')->result_array();
    //相鄰的兩條記錄的右值第一條的右值比第二條的大那麼就是他的父類
    //我們用一個數組來存儲上一條記錄的右值，再把它和本條記錄的右值比較，如果前者比後者小，說明不是父子關系，就用array_pop彈出數組，否則就保留
    //兩個循環而已，沒有遞歸
    $parent = array();
    $arr_list = array();
    foreach($lists as $item){
      if(count($parent)){
        while (count($parent) -1 > 0 && $parent[count($parent) -1]['rgt'] < $item['rgt']){
          array_pop($parent);
        }  
      }
      $item['depath'] = count($parent);
      $parent[] = $item;
      $arr_list[]= $item;
    }
    //顯示樹狀結構
    foreach($arr_list as $a)
    {
      echo str_repeat('--', $a['depath']) . $a['title'] . '<br />';
    }
  }
  /**
   * 
   * 插入操作很簡單找到其父節點，之後把左值和右值大於父節點左值的節點的左右值加上2，之後再插入本節點，左右值分別為父節點左值加一和加二
   */
  public function add()
  {
    //獲取到父級分類的id
    $parent_id = 10;
    $parent_category = $this->db->where('id', $parent_id)->get('category')->row_array();
    //1.左值和右值大於父節點左值的節點的左右值加上2
    $this->db->set('lft', 'lft + 2', FALSE)->where(array('lft >' => $parent_category['lft']))->update('category');
    $this->db->set('rgt', 'rgt + 2', FALSE)->where(array('rgt >' => $parent_category['lft']))->update('category');
    //2.插入新的節點
    $this->db->insert('category', array(
      'title' => '新的分類的子分類',
      'lft' => $parent_category['lft'] + 1,
      'rgt' => $parent_category['lft'] + 2,
      'order' => 0,
      'create_time' => time()
    ));
    echo 'add success';
  }
  /**
   * 刪除
   * 
   * //1.得到刪除的節點，將右值減去左值然後加1，得到值$width = $rgt - $lft + 1;
   * //2.刪除左右值之間的所有節點
   * //3.修改條件為大於本節點右值的所有節點，操作為把他們的左右值都減去$width
   */
  public function delete()
  {
    //通過分類id獲取分類
    $id = 3;
    $category = $this->db->where('id', $id)->get('category')->row_array();
    //計算$width
    $width = $category['rgt'] - $category['lft'] + 1;
    //1.刪除該條分類
    $this->db->delete('category', array('id' => $id));
    //2.刪除左右值之間的所有分類
    $this->db->delete('category', array('lft >' => $category['lft'], 'lft <' => $category['rgt']));
    //3.修改其它節點的值
    $this->db->set('lft', "lft - {$width}", FALSE)->where(array('lft >' => $category['rgt']))->update('category');
    $this->db->set('rgt', "rgt - {$width}", FALSE)->where(array('rgt >' => $category['rgt']))->update('category');
    echo 'delete success';
  }
  //編輯，
  public function edit()
  {
    //不用說了， 直接通過id編輯
    $id = 2;
    $this->db->update('category', array(
      'title' => '編輯後的分類'
    ), array(
      'id' => $id
    ));
    echo 'edit success';
  }
}

希望本文所述對大家的php程序設計有所幫助。