Автор: Гоблин 28.04.2007 1:44
Мне необходимо построить Т-дерево(тоже что бинарное только там от 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.
Автор: hardcase 28.04.2007 19: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
Автор: Гоблин 28.04.2007 22:49
Цитата(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
Народ не могу понять как с ним работать, покожите пожалуйста хотябы вставку в него!
или подскажите, если кто знает ресурс, или книгу, если у кого есть, по Т-дереву!