实现树状结构的两种方法

实现树状结构的两种方法 1。递归法
递归是指在函数中显式的调用它自身。
利用递归法实现树状结构的特点是写入数据速度较快，显示速度较慢（在树的分支/层次较多的情况下尤其明显）。适用与写入数据量大，树的结构复杂的情况下。
数据结构(以mysql为例)

代码:--------------------------------------------------------------------------------
CREATE TABLE `tree1` (
  `id` tinyint(3) unsigned NOT NULL auto_increment,
  `parentid` tinyint(3) unsigned NOT NULL default '0',
  `topic` varchar(50) default NULL,
  PRIMARY KEY  (`id`),
  KEY `parentid` (`parentid`)
) TYPE=MyISAM;

INSERT INTO `tree1` (`id`, `parentid`, `topic`) VALUES
  (1,0,'树1'),
  (2,0,'树2'),
  (3,0,'树3'),
  (4,2,'树2-1'),
  (5,4,'树2-1-1'),
  (6,2,'树2-2'),
  (7,1,'树1-1'),
  (8,1,'树1-2'),
  (9,1,'树1-3'),
  (10,8,'树1-2-1'),
  (11,7,'树1-1-1'),
  (12,11,'树1-1-1-1');
--------------------------------------------------------------------------------


字段说明
id,记录的id号
parentid,记录的父记录id（为0则为根记录）
topic,记录的显示标题

显示程序

顺序树:

PHP代码:--------------------------------------------------------------------------------


mysql_connect();
mysql_select_db('tree');


function tree($parentid = 0) {
   
    $sql = "select topic,id from tree1 where parentid = $parentid order by id asc";
    $rs = mysql_query($sql);
   
    echo("

");
    while($ra = mysql_fetch_row($rs)) {
        
        echo('
• '.$ra[0].'
');
        
        tree($ra[1]);
    }
    echo("

");
}
tree();
?>

--------------------------------------------------------------------------------


逆序树:

PHP代码:--------------------------------------------------------------------------------


mysql_connect();
mysql_select_db('tree');


function tree($parentid = 0) {
   
    $sql = "select topic,id from tree1 where parentid = $parentid order by id desc";
    $rs = mysql_query($sql);
   
    echo("

");
    while($ra = mysql_fetch_row($rs)) {
        
        echo('
• '.$ra[0].'
');
        
        tree($ra[1]);
    }
    echo("

");
}
tree();
?>

--------------------------------------------------------------------------------


插入数据程序

PHP代码:--------------------------------------------------------------------------------


mysql_connect();
mysql_select_db('tree');
$sql = "insert into tree (topic,parentid) values('树3-1',3);";
mysql_query($sql);
?>

--------------------------------------------------------------------------------


2。排序字段法
此方法是通过在数据结构中增加一个标志记录在整个树中的顺序位置的字段来实现的。特点是显示速度和效率高。但在单个树的结构复杂的情况下，数据写入效率有所不足。而且顺序排列时候，插入，删除记录的算法过于复杂，故通常用逆序排列。

数据结构(以mysql为例)

代码:--------------------------------------------------------------------------------
CREATE TABLE `tree2` (
  `id` tinyint(3) unsigned NOT NULL auto_increment,
  `parentid` tinyint(3) unsigned NOT NULL default '0',
  `rootid` tinyint(3) unsigned NOT NULL default '0',
  `layer` tinyint(3) unsigned NOT NULL default '0',
  `orders` tinyint(3) unsigned NOT NULL default '0',
  `topic` varchar(50) default NULL,
  PRIMARY KEY  (`id`),
  KEY `parentid` (`parentid`),
  KEY `rootid` (`rootid`)
) TYPE=MyISAM

INSERT INTO `tree2` (`id`, `parentid`, `rootid`, `layer`, `orders`, `topic`) VALUES
  (1,0,1,0,0,'树1'),
  (2,0,2,0,0,'树2'),
  (3,0,3,0,0,'树3'),
  (4,2,2,1,2,'树2-1'),
  (5,4,2,2,3,'树2-1-1'),
  (6,2,2,1,1,'树2-2'),
  (7,1,1,1,4,'树1-1'),
  (8,1,1,1,2,'树1-2'),
  (9,1,1,1,1,'树1-3'),
  (10,8,1,2,3,'树1-2-1'),
  (11,7,1,2,5,'树1-1-1'),
  (12,11,1,3,6,'树1-1-1-1');
--------------------------------------------------------------------------------


显示程序

PHP代码:--------------------------------------------------------------------------------


mysql_connect();
mysql_select_db('tree');


$sql = "select id from tree2 where parentid = 0 order by id desc";
$rs = mysql_query($sql);
echo("

");
$lay = 0;
while($ra = mysql_fetch_row($rs)) {
    echo("
");
   
    $sql = "select topic,layer from tree2 where rootid = $ra[0] order by orders";
    $rs1 = mysql_query($sql);
    while($ra1 = mysql_fetch_row($rs1)) {
        
        if($ra1[1]>$lay) {
            echo(str_repeat("
",$ra1[1]-$lay));
        }elseif($ra1[1]<$lay) {
            echo(str_repeat("
",$lay-$ra1[1]));
        }
        
        //echo("$ra1[1]>$lay");
        echo("
• $ra1[0]
");
        $lay = $ra1[1];
    }
    echo("
");
}
echo("

");
?>

--------------------------------------------------------------------------------


插入数据程序

PHP代码:--------------------------------------------------------------------------------


mysql_connect();
mysql_select_db('tree');


$sql = "insert into tree2 (topic) values ('树5')";
mysql_query($sql);
$sql = "update tree2 set rootid = id where id = ".mysql_insert_id();
mysql_query($sql);


$parentid = 5;//父记录id

$sql = "select rootid,layer,orders from tree2 where id = $parentid";
list($rootid,$layer,$orders) = mysql_fetch_row(mysql_query($sql));

$sql = "update tree2 set orders = orders + 1 where orders > $orders";
mysql_query($sql);

$sql = "insert into tree2 (rootid,parentid,orders,layer,topic) values ($rootid,$parentid,".($orders+1).",".($layer+1).",'树2-1-1-2')";
mysql_query($sql);?>