0

Информация о деревьях хранится в базе данных на MySQL в виде двух таблиц, в одной из которых хранится список деревьев, а в другой - данные об узлах дерева. Дерево вида

Дерево


Вот наработка

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css">
    .style1
    {
        width: 100%;
    }
    .style2_1
    {
        border-width: 1px;
        border-style: solid;
        text-align: center;
        background-color: #FFFF00;
        }
    .style2
    {
        border-width: 1px;
        text-align: center;
        background-color: #FFFF00;
        border-right-style: solid;
        border-bottom-style: solid;
        border-top-style: solid;
    }
</style>
</head>
<body>



<?php
class Db{
    const DB_HOST = 'localhost';
    const DB_NAME = 'tree';
    const DB_USER = 'root';
    const DB_PASS = '';

    private static $instance;
    private static $db_link;

    private function __construct() {
        self::$db_link = mysqli_connect(Db::DB_HOST, Db::DB_USER, Db::DB_PASS);
        if (!self::$db_link) die('Could not connect: ' . mysqli_error());
        if (!mysqli_select_db(self::$db_link, Db::DB_NAME)) die ('Can\'t use foo : ' . mysqli_error());
        mysqli_query(self::$db_link, 'SET NAMES utf8');
    }
    public static function query($query, $return = ''){
        if (!isset(self::$instance)) {
            $c = __CLASS__;
            self::$instance = new $c;
        }
        $link = mysqli_query(self::$db_link, $query);
        if (!$link) die (mysqli_error(self::$db_link) . '<br/>' . $query);

        if ($return == 'link') {
            return $link;
        } elseif ($return == 'field') {
            $row = mysqli_fetch_row($link);
            return $row ? $row[0] : 0;
        } elseif ($return == 'a') {
            return mysqli_fetch_object($link);
        } elseif (!(strpos($query, 'SELECT') === false)) {
            return mysqli_fetch_array($link);
        } else {
            return $link;
        }
    }
}

$_tree_name = 'blablatable';
$_tree_id   = 2;
$link  = Db::query('SELECT * FROM nodes WHERE tree_id=' . $_tree_id . ' ORDER BY crit', 'link');

$nodes = $parents = $levels = $last = array();

while ($row = mysqli_fetch_assoc($link)) 
{
    $nodes[$row['id']]      = $row;       //basic nodes array - wont change in script
    $parents[$row['pid']][] = $row['id']; //nodes tree
}

//arrange nodes by levels and create end points array
make_levels($parents, $nodes, 0, 0, $levels, $last);
function make_levels($parents, $nodes, $pid, $level, &$levels, &$last)
{
    foreach ($parents[$pid] AS $child) {
        $levels[$level][$nodes[$child]['crit']] = $child; //levels tree
        if (isset($parents[$child])) {
            make_levels($parents, $nodes, $child, $level+1, $levels, $last);
        } else {            
            $last[$nodes[$child]['crit']] = array($level, $child); //last nodes
        }
    }
}

ksort($last);

$rows         = count($last);
$columns      = count($levels);
$to_add_level = $columns - 1;

//add last points
$table = $positions = $to_add_parents = array(); $row = 0;
foreach ($last AS $crit => $tmp) 
{
    list($level, $child) = $tmp;
    $table[$row][$level] = array('child' => $child, 'is_last' => 1, 'crit' => $crit);
    $positions[$child]    = $row;
    if ($level == $to_add_level) 
    {
        $to_add_parents[]     = $nodes[$child]['pid'];
    }
    $row++;
}

// add internal points
add_parents($parents, $nodes, $levels, $table, $positions, $to_add_parents, $to_add_level);
function add_parents($parents, $nodes, $levels, &$table, &$positions, $to_add_parents, &$to_add_level) 
{
    $to_add_level--;
    foreach ($to_add_parents AS $pid) 
    {
        if (isset($positions[$pid])) continue;
        $all_childs = $parents[$pid]; $all_positions = array();
        foreach ($all_childs AS $child) 
        {
            $all_positions[] = $positions[$child];
        }

        $center_position = round(array_sum($all_positions) / count($all_positions));

        if (isset($table[$center_position][$to_add_level])) 
        {
            for($i=0;$i<3;$i++) 
            {
                if (!isset($table[$center_position+$i][$to_add_level])) {
                    $center_position = $center_position + $i;
                    break;
                } elseif (!isset($table[$center_position-$i][$to_add_level])) {
                    $center_position = $center_position - $i;
                    break;
                }
            }
        }

        $table[$center_position][$to_add_level] = array('child' => $pid);
        $positions[$pid] = $center_position;
    }

    $new_to_add_parents = array();

    foreach($levels[$to_add_level-1] AS $next_pid) {
        if (isset($positions[$next_pid])) continue;
        $new_to_add_parents[] = $next_pid;
    }

    if ($new_to_add_parents) 
    {
        add_parents($parents, $nodes, $levels, $table, $positions, $new_to_add_parents, $to_add_level);
    }

}
//add table name
$pid = 0;
$all_childs = $parents[$pid];
$_tree_name_min = $_tree_name_max = $_tree_name_sum = $positions[$all_childs[0]];
$_tree_name_count = count($all_childs);
for ($i=1; $i<$_tree_name_count; $i++) 
{
    $pos = $positions[$all_childs[$i]];
    $_tree_name_sum += $pos;
    if ($_tree_name_min > $pos) $_tree_name_min = $pos;
    if ($_tree_name_max < $pos) $_tree_name_max = $pos;
}

$_tree_name_position = round($_tree_name_sum / $_tree_name_count);

echo '<table class="style1" cellpadding="0" cellspacing="0" style="vertical-align: bottom; font-size: small;">';
echo '<tr><td class="style2_1">0-й ярус</td>';
for($j=1;$j<=$columns;$j++) echo '<td class="style2"> ' . $j . '-й ярус</td>';
echo '<td style="text-align: center"> Номер критерия</td></tr>';
echo '<tr>' . str_repeat('<td>&nbsp;</td>', $columns + 2) . '</tr>';
$_tree_name_min++;
for ($i=0; $i<=$rows; $i++) 
{
    $row = $table[$i]; $crit = 0;
    echo '<tr>';
    if ($i == $_tree_name_position) {
        echo '<td style="border-bottom-style: solid; border-bottom-width: 1px;';
        if ($i > $_tree_name_min || $i < $_tree_name_max) {
            echo "border-right-style: solid; border-right-width: 1px;";
        }
        echo '">' . $_tree_name . '</td>';
    }elseif ($i < $_tree_name_min || $i > $_tree_name_max) {
        echo '<td>&nbsp;</td>';
    }else{
        echo '<td style="border-right-style: solid; border-right-width: 1px;">&nbsp;</td>';
    }

    for($j=0; $j<=$columns; $j++) 
    {
        if (isset($row[$j])) {
            $tmp = $row[$j];
            $child = $tmp['child'];
            $node  = $nodes[$child];
            if (isset($tmp['is_last'])) {
                $colspan = $columns - $j;
                echo '<td style="vertical-align: bottom; font-size: small;  border-bottom-style: solid; border-bottom-width: 1px;" colspan="' . $colspan . '">';
                echo $node['crit'] . '. ' . $node['name'] . ' [id:' . $node['id'] . ',pid:' . $node['pid'] . ']</td>';
                echo '<td style="text-align: center">' . $tmp['crit'] . '</td></tr>';
                break;
            } else {
                echo '<td style="vertical-align: bottom; font-size: small;  border-bottom-style: solid; border-bottom-width: 1px;">';
                echo $node['crit'] . '. ' . $node['name'] . ' [id:' . $node['id'] . ',pid:' . $node['pid'] . ']</td>';
            }

        } else {
            echo '<td>&nbsp;</td>';
        }
    }
}
echo '</table>';

ВОТ и дамп таблицы) туда можно еще загнать значений кому не лень

-- phpMyAdmin SQL Dump
-- version 3.4.3.1
-- http://www.phpmyadmin.net
--
-- Хост: localhost
-- Время создания: Авг 07 2011 г., 13:16
-- Версия сервера: 5.0.87
-- Версия PHP: 5.2.17

SET SQL_MODE="NO_AUTO_VALUE_ON_ZERO";
SET time_zone = "+00:00";


/*!40101 SET @OLD_CHARACTER_SET_CLIENT=@@CHARACTER_SET_CLIENT */;
/*!40101 SET @OLD_CHARACTER_SET_RESULTS=@@CHARACTER_SET_RESULTS */;
/*!40101 SET @OLD_COLLATION_CONNECTION=@@COLLATION_CONNECTION */;
/*!40101 SET NAMES utf8 */;

--
-- База данных: `turtus_test`
--

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

    --
    -- Структура таблицы `nodes`
    --

    CREATE TABLE `nodes` (
      `id` int(11) NOT NULL auto_increment,
      `tree_id` varchar(11) collate utf8_unicode_ci NOT NULL,
      `pid` varchar(11) collate utf8_unicode_ci NOT NULL,
      `node_num` varchar(11) collate utf8_unicode_ci NOT NULL,
      `name` varchar(500) collate utf8_unicode_ci NOT NULL,
      `crit` varchar(11) collate utf8_unicode_ci NOT NULL,
      PRIMARY KEY  (`id`)
    ) ENGINE=MyISAM  DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci AUTO_INCREMENT=119 ;

    --
    -- Дамп данных таблицы `nodes`
    --

    INSERT INTO `nodes` (`id`, `tree_id`, `pid`, `node_num`, `name`, `crit`) VALUES
    (1, '1', '0', '1', 'Ветка1', '1'),
    (2, '1', '0', '1', 'Ветка2', '2'),
    (3, '1', '1', '2', 'Ветка1_1', '3'),
    (4, '1', '1', '2', 'Ветка1_2', '4'),
    (5, '1', '3', '3', 'Ветка2_1', '5'),
    (6, '1', '3', '3', 'Ветка2_2', '6'),
    (7, '1', '5', '4', 'Ветка2_1_1', '7'),
    (117, '2', '0', '1', 'оргработа по франшизам', '17'),
    (118, '2', '0', '1', 'результаты деятелности', '18'),
    (113, '2', '117', '2', 'обобщенная характеристика франшиз', '13'),
    (114, '2', '117', '2', 'продажи франшиз', '14'),
    (115, '2', '118', '2', 'франчайзи', '15'),
    (116, '2', '118', '2', 'франчайзера', '16'),
    (112, '2', '113', '3', 'распространеннность по кол-ву франчайзинговых точек', '12'),
    (101, '2', '112', '3', 'количество франчайзи с несколькими франшизами', '1'),
    (102, '2', '112', '3', 'общее количество франчайзи', '2'),
    (103, '2', '112', '3', 'общее количество франчайзи 2', '3');

база вбита тупо для примера и не совпадает с тем что на картинке. Ни у кого ничего не получилось?)

9
  • Кстати, задача на алгоритм очень интересная. Как я понимаю, на входе список категорий и для каждой указан ее родитель. И неизвестный уровень вложенности.
    – scorN
    6 авг 2011 в 20:32
  • scorN, Именно. Это все начинается с 1 яруса. Идею подали - МАТРИЦА. Пляшем отсюда дальше) 6 авг 2011 в 21:06
  • Номер ряда, в котором разместить название, можно определить как floor((КОЛ_ВО ВЕТОК БЕЗ ДЕТЕЙ+1)/2). 6 авг 2011 в 21:17
  • Так программа есть у вас оказывается? Или она не рабочая? Логику я с 20-го раза догнал, и про матрицу и про ряды. Думаю в приведенной вами программе слишком много кода. Можно мою программу подправить и все получится.
    – scorN
    7 авг 2011 в 19:58
  • она недоделаная. но корректно формирует структуру. потрачена на нее ночь) Проблема только в вертикальных рамках. 7 авг 2011 в 20:01

2 ответа 2

1

Вот что получилось. :) Конечно, нужно оптимизировать, но пока так. Под скриптом скрин того, что выдает скрипт.

$c= mysql_connect( $db_host, $db_login, $db_password );
mysql_select_db( $db_name, $c );

$main= 0;

$tmp= mysql_query( "SELECT * FROM scorn WHERE parent=". $main ." ORDER BY id", $c );

$arr_c= 0;
$arr_child[ $arr_c ]= array(
    'id' => $main,
    'result' => $tmp,
    'max' => mysql_num_rows( $tmp ) - 1,
    'count' => 0
);

do
{
    for( $k=$arr_child[ $arr_c ][ 'count' ]; $k<=$arr_child[ $arr_c ][ 'max' ]; $k++ )
    {
        print '<div style="display:table;border:1px solid #ccc;padding:3px;margin-left:20px;margin-bottom:5px;">item_' .  mysql_result( $arr_child[ $arr_c ][ 'result' ], $k, 'id' );

        $arr_child[ $arr_c ][ 'count' ] += 1;

        $tmp= mysql_query( "SELECT * FROM scorn WHERE parent=". mysql_result( $arr_child[ $arr_c ][ 'result' ], $k, 'id' ) ." ORDER BY id", $c );

        if( mysql_num_rows( $tmp ) > 1 )
        {
            $arr_c += 1;
            $arr_child[ $arr_c ]= array(
                'id' => mysql_result( $arr_child[ $arr_c ][ 'result' ], $k, 'id' ),
                'result' => $tmp,
                'max' => mysql_num_rows( $tmp ) - 1,
                'count' => 0
            );

            continue( 2 );
        }

        print '</div>';
    }

    unset( $arr_child[ $arr_c ] );
    $arr_c -= 1;

    print '</div>';
}
while( $arr_c != 0 );

снимок

8
  • Нет, тут именно матрицей работать надо, получаем сразу данные, загнанные под структуру таблицы. 7 авг 2011 в 17:26
  • Как тут много кода выложить, больше 500 символов и картинку приатачить? 7 авг 2011 в 17:31
  • Приведите тогда матрицу, которая должна получится.
    – scorN
    7 авг 2011 в 17:34
  • @Виктор Давыдов Чтобы выложить код и добавить картинку, надо отредактировать исходный вопрос. 7 авг 2011 в 17:38
  • Матрица будет размерностью [количество уровней]х[количество рядов]. $matrix[i][j]=array('title'=>'ИМЯ поля', 'opt'=>array(false, false, true,false)); opt - это массив, который хранит, нужна ли граница у ячейки (лево, право, верх, низ). Вот такая вот мысль пришла. 7 авг 2011 в 17:41
1

Код:

<?php

mysql_connect('localhost', 'root', '');
mysql_select_db('test');

class Node {

    private $_parent = NULL;
    private $_childs = array();
    private $_name = '';
    private $_crit = '';
    private $_child_pos = 0;


    public function __constructor($parent = NULL){
        $this->_parent = $parent;
    }

    public function getName(){ return $this->_name; }
    public function setName($n){ $this->_name = $n; }

    public function getCrit(){ return $this->_crit; }
    public function setCrit($c){ $this->_crit = $c; }

    public function addChild($r){
        $n = new Node($this);
        $n->_name = $r['name'];
        $n->_crit = $r['crit'];
        return $this->_childs[] = $n;
    }

    function __destruct() {
        if (!isset($this->_childs) || !is_array($this->_childs)) return;
        foreach ($this->_childs as $ch) {
            $ch->__destruct();
            unset($ch);
        }
        unset($this->childs);
    }

    public function __construct ($parent) {
        $this->_parent = &$parent;
    }

    public function childFirst(){
        $this->_child_pos = 0;
        return @$this->_childs[$this->_child_pos];
    }

    public function childNext(){
        return @$this->_childs[++$this->_child_pos];
    }

    public function getChilds(){
        return $this->_childs;
    }

    public function getChildsCnt(){
        return count($this->_childs);
    }

    public function getParent(){
        return $this->_parent;
    }

    public function getMaxChilds($max=0) {
        foreach ($this->_childs as $ch) {
            $cur = $ch->getChildsCnt();
            if($cur > $max) $max = $cur;
            $cur = $ch->getMaxChilds($max);
            if($cur > $max) $max = $cur;
        }
        return $max;
    }

    public function getMaxDeep($deep = 0, $maxDeep) {
        if($deep > $maxDeep) $maxDeep = $deep;
        foreach ($this->_childs as $ch) {
            $maxDeep = $ch->getMaxDeep($deep + 1, $maxDeep);
        }
        return $maxDeep;
    }

    public function getMax(&$cnt = 0) {
        if ($this->getChildsCnt() == 0) {
            $cnt++;
        }
        foreach ($this->_childs as $ch) {
            $ch->getMax($cnt);
        }
        return $cnt;
    }

}


function readTree($treeId, $tree, $pid=0) {
    $res = mysql_query('select * from nodes where tree_id='.($treeId*1).' and pid='.($pid*1));
    while ($r = mysql_fetch_assoc($res)) {
        readTree($treeId, $tree->addChild($r), $r['id']);
    }
    mysql_free_result($res);
}

$root = new Node(NULL);
$root->setName('Gold Fran');
readTree(2, $root);
$t = '<table border="1">';
outPut($root, $t);
echo $t;

function outPut($n, &$t, $lvl = 0) {
    if($lvl == 0) $t .= '<tr>';

    $t .= '<td rowspan="'.($n->getMax()).'">'.$n->getCrit().'. '.$n->getName().'</td>';
    $r = $n->childFirst();

    do {
        if ($r != NULL) {
            outPut($r, $t, $lvl+1);
            $t .= '</tr>';
        }
    } while($r = $n->childNext());
    return $t;
}

?>

Снимок:

alt text

1
  • если я правильно понял задачу, то это не то что нужно!
    – scorN
    9 авг 2011 в 17:34

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.