IPB
ЛогинПароль:

> ВНИМАНИЕ!

Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Т-дерево, Проблемы с построением
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 2
Пол: Мужской

Репутация: -  0  +


Мне необходимо построить Т-дерево(тоже что бинарное только там от 2 до 4 элементов в узле).
Казалось бы ничего сложного, построил бинарное дерево, добавил два элемента и все!
Но элементы в узле упорядочены по возростанию, я не могу понять как их распределять по узлам, не нарушая баланса, во время вставки и как их там сортировать! Помогите пожалуйста :-(
Пока у меня есть только бинарное дерево
Код

type
  ptree=^ttree;
  ttree=record
    left,right:ptree;
    data : integer;
  end;


  TForm1 = class(TForm)
    Button1: TButton;
    TreeView1: TTreeView;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
root:ptree;
implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
procedure push_to_tree(i:integer);
var n,temp : ptree;
    placed : boolean;

begin
   temp:=root; placed := false;
   while not placed do
      if temp^.data>i then begin
        if temp^.right<>nil then temp := temp^.right else
        begin
           new(n);
           n^.left := nil;
           n^.right := nil;
           n^.data := i;
           temp^.right := n;
           placed := true;
        end
      end
      else
      if temp^.data<i then
        if temp^.left<>nil then temp := temp^.left else
        begin
           new(n);
           n^.left := nil;
           n^.right := nil;
           n^.data := i;
           temp^.left := n;
           placed := true;
        end
      else
        placed := true;
end;
procedure print_tree_to_tree_view(root:ptree;parent:TTreeNode);
var next_parent : TTreeNode;
begin
   next_parent:=TreeView1.Items.AddChild(parent,inttostr(root^.data));
   if root^.left <> nil then print_tree_to_tree_view(root^.left, next_parent);
   if root^.right<> nil then print_tree_to_tree_view(root^.right,next_parent);
end;
var i : integer;
begin
    {creating tree from root}
    new(root);
    root^.data := 10;
    root^.left := nil; root^.right := nil;
    for i := 0 to Memo1.Lines.Count-1 do
       push_to_tree(strtoint(Memo1.Lines.Strings[i]));
    TreeView1.Items.Clear;
    print_tree_to_tree_view(root,nil);
end;

end.


Сообщение отредактировано: Гоблин -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


code warrior
****

Группа: Пользователи
Сообщений: 484
Пол: Мужской
Реальное имя: Славен

Репутация: -  8  +


Рассмотри бинарное дерево:
A - узел. L - левый сын, R - правый сын.

У L также будут левый LL и правый LR сыновья. Аналогично у R - RL и RR

тогда легко видно, как можно свернуть двоичное дерево в Т- дерево
Код

       A
   /      \
  L        R
/ \      / \
LL  LR   RL  RR



Смотрим на узел M:
Код

         M

  /   /     \   \
LL   L     RL   R
      \          \        
       LR        RR


Сообщение отредактировано: hardcase -


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 2
Пол: Мужской

Репутация: -  0  +


Цитата(hardcase @ 28.04.2007 16:40) *

Рассмотри бинарное дерево:
A - узел. L - левый сын, R - правый сын.

У L также будут левый LL и правый LR сыновья. Аналогично у R - RL и RR

тогда легко видно, как можно свернуть двоичное дерево в Т- дерево
Код

       A
   /      \
  L        R
/ \      / \
LL  LR   RL  RR



Смотрим на узел M:
Код

         M

  /   /     \   \
LL   L     RL   R
      \          \        
       LR        RR



Народ не могу понять как с ним работать, покожите пожалуйста хотябы вставку в него!
или подскажите, если кто знает ресурс, или книгу, если у кого есть, по Т-дереву!

Сообщение отредактировано: Гоблин -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 4:41
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name