當前位置:開發者網絡 >> 技術教程 >> PHP教程 >> PHP應用 >> 內容
精彩推薦
分類最新教程
分類熱點教程
    
實現樹狀結構的兩種方法
作者:未知
日期:2005-03-21
人氣:
投稿:snow(轉貼)
來源:未知
字體:
收藏:加入瀏覽器收藏
以下正文:
實現樹狀結構的兩種方法
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查詢,獲取記錄的標題和id*/
$sql = "select topic,id from tree1 where parentid = $parentid order by id asc";
$rs = mysql_query($sql);
/* 縮進*/
echo("<ul>");
while($ra = mysql_fetch_row($rs)) {
/* 顯示記錄標題 */
echo('<li>'.$ra[0].'</li>');
/* 遞歸調用 */
tree($ra[1]);
}
echo("</ul>");
}
tree();
?>

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


逆序樹:

PHP代碼:--------------------------------------------------------------------------------

<?
/* 數據庫連接 */
mysql_connect();
mysql_select_db('tree');

/* 樹狀顯示的遞歸函數 */
function tree($parentid = 0) {
/*執行sql查詢,獲取記錄的標題和id*/
$sql = "select topic,id from tree1 where parentid = $parentid order by id desc";
$rs = mysql_query($sql);
/* 縮進*/
echo("<ul>");
while($ra = mysql_fetch_row($rs)) {
/* 顯示記錄標題 */
echo('<li>'.$ra[0].'</li>');
/* 遞歸調用 */
tree($ra[1]);
}
echo("</ul>");
}
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');

/* 選出所有根記錄id */
$sql = "select id from tree2 where parentid = 0 order by id desc";
$rs = mysql_query($sql);
echo("<ul>");
$lay = 0;
while($ra = mysql_fetch_row($rs)) {
echo("<ul>");
/* 選出此樹所有記錄,並按orders字段排序 */
$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("<ul>",$ra1[1]-$lay));
}elseif($ra1[1]<$lay) {
echo(str_repeat("</ul>",$lay-$ra1[1]));
}
/* 記錄顯示 */
//echo("$ra1[1]>$lay");
echo("<li>$ra1[0]</li>");
$lay = $ra1[1];
}
echo("</ul>");
}
echo("</ul>");
?>

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


插入數據程序

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
/* 取出 根記錄id,父記錄縮進層次,父記錄順序位置 */
$sql = "select rootid,layer,orders from tree2 where id = $parentid";
list($rootid,$layer,$orders) = mysql_fetch_row(mysql_query($sql));
/* 更新插入位置後記錄的orders值 */
$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);?>

相關文章: