нужен алгоритм для зарисовка элементов в treeview

← →
linuxoid (2010-08-09 08:24) [0]

Здравствуйте!
Задача состоит в том, чтобы зарисовать элементы дерева рисунками из imagelista. есть 3 вида рисунка, которые обозначены индексами - 0,1,2.
самый нижний подузел рисуется выбирая индекс из базы
treenode.imageindex:=0 или 1. а третий индекс зависит от состояния подузлов.
примеры:

если все подузлы какого нибудь узла имееют индекс 0, то узел будет равен 0. treenode.imagindex:=0;
узел-1
подузел1 - 0
подузел2 - 0
подузел3 - 0

если подузлы какого нибудь узла равны 1, то узел будет равен 1. treenode.imagindex:=1;
узел-2.
подузел1 - 1
подузел2 - 1
подузел3 - 1

если подузлы иееют индексы и 0 и 1, то узел равен 2. treenode.imagindex:=2;
узел-3
подузел1 - 0
подузел2 - 1
подузел3 - 0

рисунки должны рисоваться с нижних узлов. первоначальные индексы берутся из базы. а последующие в зависимости от них.

вот листинг:

{************************************************
Заполнение дерева
************************************************}

procedure TMainForm.FillTree();
var
i: Integer;
Child : TTreeNode;
begin
SubjectTree.Items.BeginUpdate;//Не перерисовывать дерево
if SubjectTree.Items.Count > 0 then
begin //if
SubjectTree.Items.Clear;
end; //if

BaseQuery.Active := false;
BaseQuery.SQL.Clear;
//Составление запроса и ввод параметров
//Выбираем элементы не имеющие родителя, т.е. корневые
BaseQuery.SQL.Text := "SELECT NodeID, ParentID, NodeName, NodeType "+
"FROM MainTable WHERE ParentID = :ParentID";
BaseQuery.Parameters.ParseSQL(BaseQuery.SQL.Text, true);
BaseQuery.Parameters.ParamByName("ParentID").Value := 0;

try
BaseConnect.Open; //Открываем соединение с базой
BaseQuery.Active := true;

if BaseQuery.RecordCount <> 0 then
begin
while not BaseQuery.Eof do
begin
SubjectTree.Items.AddObject(nil,
BaseQuery.Fields[2].AsString,
Pointer(BaseQuery.Fields[0].AsInteger));

BaseQuery.Next;
end; //while

Child := SubjectTree.Items.GetFirstNode;
while Child <> nil do
begin
FillBranch(Child);
Child := Child.GetNextSibling;
end;//while
end; //if

finally
BaseConnect.Close; //Закрываем коннект
end;
SubjectTree.Items.EndUpdate; //Разрешить прорисовку
end; {FillTree}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
procedure TMainForm.FillBranch(tn: TTreeNode);
var
i: Integer;
TreeNode : TTreeNode;
begin
BaseQuery.Active := false;
BaseQuery.SQL.Clear;
//Составление запроса и ввод параметров
//Выбираем элементы не имеющие родителя, т.е. корневые
BaseQuery.SQL.Text := "SELECT NodeID, ParentID, NodeName, NodeType "+
"FROM MainTable WHERE ParentID = :ParentID";
BaseQuery.Parameters.ParseSQL(BaseQuery.SQL.Text, true);
BaseQuery.Parameters.ParamByName("ParentID").Value := Integer(tn.Data);

BaseQuery.Active := true;

if BaseQuery.RecordCount <> 0 then
begin
while not BaseQuery.Eof do
begin
TreeNode := SubjectTree.Items.AddChildObject(tn,
BaseQuery.Fields[2].AsString,
Pointer(BaseQuery.Fields[0].AsInteger));

BaseQuery.Next;
end; //while

Child := tn.getFirstChild;
while Child <> nil do
begin
FillBranch(Child);
Child := Child.GetNextSibling;
end;//while

end; //if
end; {FillBranch}
{************************************************}

← →
12 © (2010-08-09 08:48) [1]

> алгоритм для зарисовка элементов в treeview

выбрать все последние узлы, проставить им индексы
от каждого, поднимаясь наверх, добавляем родителю 1 в некое поле "кол-во детей" и 1+индекс в поле "вес детей"

еще раз обходим дерево,
у кого "кол-во детей" = "вес детей" - тот типа 0
у кого "кол-во детей" = 2*"вес детей" - тот типа 1
иначе - 2

> если подузлы иееют индексы и 0 и 1, то узел равен 2.

а если подузлы иемеют индекс 2?

← →
linuxoid (2010-08-09 08:54) [2]

если подузлы имеют индекс 2 то тогда узел будет равен тоже 2. самый нижний подузел не может быть равен 2.

узел-2
подузел1-0
подподузел1-0
подподузел2-0
подподузел3-0
подподузел4-0
подузел2-1
подподузел1-1
подподузел2-1
подподузел3-1
подподузел4-1
подузел3-2
подподузел1-1
подподузел2-0
подподузел3-1
подподузел4-1

← →
linuxoid (2010-08-09 09:00) [3]

а здесь нужно рекурсию использовать? в программе может быть несколько подуровней.

← →
12 © (2010-08-09 09:23) [4]

как угодно,

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

> если подузлы имеют индекс 2 то тогда узел будет равен тоже
> 2.

> выбрать все последние узлы, проставить им индексы
> от каждого, поднимаясь наверх, добавляем родителю 1 в некое
> поле "кол-во детей" и 1+индекс в поле "вес детей",
если 1 или 0. Или -maxint, если 2.
>
> еще раз обходим дерево,
> у кого "кол-во детей" = "вес детей" - тот типа 0
> у кого "кол-во детей" = 2*"вес детей" - тот типа 1
иначе - 2

← →
MBo © (2010-08-09 09:23) [5]

>а здесь нужно рекурсию использовать?
да.

Еще вариант формирования индекса - изменить набор (0,1,2) на (1,2,3), тогда индекс родителя - OR индексов деток (можно без изменения набора, но тогда +-1 придется делать)

← →
linuxoid (2010-08-09 09:40) [6]

во первых: до начало всего этого все узлы имеют индекс 0 и 1. после обхода уже будут 0,1 или 2.

правилен ли алгоритм этот, для того, чтоб выбрать самые нижние узлы?

1)делаем запрос к базе и выбираем самые верхние узлы
(select * from maintable where parentid=:0)
2)откраем цикл для выбранных узлов
3) проверям: имеют ли данные узлы подузлы:
если нет то это нижний подузел для этого узла
//...................
если да, то
4) делаем запрос к базе (select * from maintable where
parentid=nodeid) (здесь мы вытащим подузлы для узлов)
//............................

← →
12 © (2010-08-09 09:46) [7]

> правилен ли алгоритм этот, для того, чтоб выбрать самые нижние узлы?

зачем?
Может сделать запрос и выбрать самые нижние?

select * from maintable m1
left join maintable m2 on m1.Id = m2.parentId
where m2.ID is null

← →
linuxoid (2010-08-09 09:57) [8]

этот же алгоритм вроде подойдет тока для двухуровневого. у меня дерево трех уровневое

← →
12 © (2010-08-09 10:01) [9]

почему это?
к таблице присоединяешь таблицу, где не присоединилось - там и есть те, кто без родителя. И без разницы сколько там уровней.

← →
linuxoid (2010-08-09 10:30) [10]

в этом алгоритме есть одна промашка. в выбранных узлах отсутствует узлы, которые имеют под узлы. как их выбрать тоже, так как они тоже являются под узлами вышестоящего узла?

← →
12 © (2010-08-09 10:40) [11]

> там и есть те, кто без родителя. И без разницы сколько там
> уровней.

кто не имеет детей, т.е.

> в этом алгоритме есть одна промашка. в выбранных узлах отсутствует
> узлы, которые имеют под узлы. как их выбрать тоже, так как
> они тоже являются под узлами вышестоящего узла?

не понял
Алгоритм был таков:

Запрос дает всех, кто без детей
Берем их и для каждого поднимаемся по дереву, пока Parent <> nil, попутно пишем в поля
1 в поле "кол-во детей" и 1+индекс в поле "вес детей", если 1 или 0.
Или -maxint, если 2.

Если мы это сделаем для каждого листа - не останется ни одной ветки, через которую бы не прошли, по разу, для каждого листа этой ветки

Осталось еще раз обойти дерево и
> у кого "кол-во детей" = "вес детей" - тот типа 0
> у кого "кол-во детей" = 2*"вес детей" - тот типа 1
иначе - 2

← →
12 © (2010-08-09 10:43) [12]

а вообще, изначально, откуда берутся эти 1 или 0? Из БД?, поля там такое? или как?

К чему - может проще в запросе получить датасет, по которому строится дерево, где уже будет известен тип каждого узла

← →
linuxoid (2010-08-09 10:56) [13]

первоначальный вид
id |parantid| name
10 0 узел0
11 10 узел1
12 10 узел2
13 10 узел3
14 10 узел4
15 11 узел5
16 11 узел6

узел0
узел1
узел5
узел6
узел2
узел3
узел4

после отбора остаются
12 10 узел2
13 10 узел3
14 10 узел4
15 11 узел5
16 11 узел6

узел первый я зарисую исходя из индексов узела5 и узла 6.

как потом мне подняться вверх и зарисовать узел 0? нужно же как то выбрать узел1, узел2, узел3, узел4. последние три я выберу. как последнии добавить к нм?

← →
linuxoid (2010-08-09 11:00) [14]

> а вообще, изначально, откуда берутся эти 1 или 0? Из БД?
> , поля там такое? или как?

есть столбец index. где изначально стоят 0 или 1. после обхода они меняются исходя от индексов нижних узлов.

а насчет датасета можно конечно.

← →
linuxoid (2010-08-09 11:01) [15]

> как последнии добавить к нм?

как первый к ним добавить?

> нужно же как то выбрать ... узел2, узел3, узел4

по твоему условию - они конечные, значит, индекс для них есть

> нужно же как то выбрать узел1

вот и я к чему, надо писать процедуру "всплытия"
аля

while GetParentNode <> nil do
Push(Node."Вес детей")
Node := GetParentNode
Node."кол-во детей" := Node."кол-во детей" +1
Node."Вес детей" := Node."Вес детей" + Pop (Node."Вес детей")

и применить ее для всех записей

> select * from maintable m1
> left join maintable m2 on m1.Id = m2.parentId
> where m2.ID is nu

Потом обойти дерево (без разницы как, просто по глобольному индексу нода)
и

> > у кого "кол-во детей" = "вес детей" - тот типа 0
> > у кого "кол-во детей" = 2*"вес детей" - тот типа 1
> иначе - 2

← →
linuxoid (2010-08-09 12:57) [17]

в начале у мя таблица выглядит так.

id |parantid| name | index
10 0 узел0 0
11 10 узел1 1
12 10 узел2 0
13 10 узел3 0
14 10 узел4 1
15 11 узел5 1
16 11 узел6 0

а после обхода оно должно быть
id |parantid| name | index
10 0 узел0 0
11 10 узел1 2
12 10 узел2 1
13 10 узел3 0
14 10 узел4 1
15 11 узел5 1
16 11 узел6 0

по алгоритму
1 действие:
выбираем узел5 и узел6. так как у них смешанные индексы (узел5=1, узел6=0), значит берем его родителя (это узел1) и ставим туда индекс 2.
2 действие:
выбираем узел1, узел2, узел3, узел4, их индексы соответственно равны 2, 1, 0, 1. берем его родитель (узел0). и ставим туда 2, так как индексы детей этого узла разные.

а вашем алгоритме при запросе исключаются такой узел как узел1, как я понял.

> а вашем алгоритме при запросе исключаются такой узел как
> узел1, как я понял.

естественно исключается, т.к. он не конечный
он будет вычислен, когда будет "всплытие" с узлов 5 и 6

Еще раз -
1/ спрашиваем только конечные узлы, они определены (по условию)
2/ "всплываем" от них до верха (до parent = nil), по пути модифицируя весь свой "путь всплывания"
3/ обходим дерево, вычисляя кто есть кто, используя "модификации всплывания" (предыдущий пункт).

1. - запрос
2. - процедура всплывания, применяется для всех из 1.
3. - простой обход дерева и сравнивание 2х чисел, "кол-во детей" и "вес детей"

← →
linuxoid (2010-08-09 15:51) [19]

спасибо!

нужен алгоритм для зарисовка элементов в treeview Найти похожие ветки