class Node {
int value; // zna4enie v uzle
int kordsus; // koli4etvo povtorenii nekotorogo zna4enija
Node left, right;
public Node(int uus) {
value = uus;
kordsus = 0;
}
/* vstavitj zna4enie v nuznom napravlenii
* lil uveli4itj zna4enie "kordsus"
*/
public void insert(Node node) {
if(node.value > value)
if(right != null)
right.insert(node);
else right = node;
else
if(node.value < value)
if(left != null)
left.insert(node);
else
left = node;
else
kordsus++;
}
//vozvrasjaet zna4enie povtorenii uzla ili nolj
public int search(Node node) {
if(node.value == value)
return kordsus;
else
if(node.value > value)
search(right);
else
if(node.value < value)
search(left);
return 0;
}
//pe4ataet sna4ala levqe vetvi dereva, zatem uzel, zatem pravqe vetvi
//NB! peatj vqpolnitj tak, 4tobq legko bqlo izobrazitj derevo grafi4eski!
public void print() {
if ( left != null) left.print();
System.out.println("Left:");
System.out.println( "Value=" + value+" Kordsus="+kordsus );
if ( right != null ) right.print();
System.out.println("Right:");
System.out.println( "Value=" + value+" Kordsus="+kordsus );
}
}
class BST {
private static Node root;
public static void main(String[] args) {
int sItem = -1;
root = new Node(rand());
for (int i = 0; i < 10; i++) insert(rand());
root.print();
sItem = search(rand());
System.out.println("Kordsuse arv="+sItem);
}
//dobavlenie uzlaja v derevo
public static void insert(int v) {
root.insert(new Node(v));
}
//vozvrasjaet zna4enie "kordsus" ili nolj
public static int search(int v) {
int valueKordsus = root.search(new Node(v));
return (valueKordsus == 0 ? 0 : valueKordsus);
}
//pe4atj vsego dereva
public void print() {
}
public static int rand() {
return (int)(Math.random()*100);
}
}
Binary Search Tree (JAVA)
Помогите доделать дерево бинарного поиска
возникла проблемма с выводом дерева. Помогите, пожалуйста.
Код:
возникла проблемма с выводом дерева. Помогите, пожалуйста.
Оо, вывод - это отдельная история. Писать нет времени, могу кинуть как нечто подобное решил я, на дельфе правда. Но при желании можно разобраться.
Или юзай JTree.
Или юзай JTree.
А вставка и поиск у меня релизованы правильно? :confused:
Не могу JTtree, так как консольная прога. С удовольстаием взгляну на ваш дэльфийскифй пример:)
Не могу JTtree, так как консольная прога. С удовольстаием взгляну на ваш дэльфийскифй пример:)
а в Исходниках на форуме искал? в полезных ссылках адресса сайтов, где может быть нужная тебе прога, только на С или Паскаль. поищи. поиск по форуму тоже вещь хорошая.
[URL="http://www.codenet.ru/"][COLOR=#800080]Статьи[/COLOR][COLOR=black][/url][/COLOR]
[URL="http://www.codenet.ru/"][COLOR=#800080]Статьи[/COLOR][COLOR=black][/url][/COLOR]
Код:
procedure TIvFormulaTree.ShowAsText(Memo: TMemo);
var
Iterator: PIvTreeNode;
TraceStack: TIvPtrStack;
I: Integer;
S: string;
begin
Memo.Clear;
TraceStack := TIvPtrStack.Create;
Iterator := Root;
TraceStack.Push(Iterator);
while TraceStack.GetTop <> nil do
begin
while Iterator <> nil do
begin
// Формирование строки и добавление ее в поле
S := '';
for I := 1 to Iterator^.Level do
S := S + ' ';
S := S + Iterator^.Data;
Memo.Lines.Add(S);
TraceStack.Push(Iterator);
Iterator := Iterator^.LeftChild;
end;
Iterator := TraceStack.Pop;
while Iterator^.RightChild = nil do
Iterator := TraceStack.Pop;
Iterator := Iterator^.RightChild;
end;
TraceStack.Free;
end;
var
Iterator: PIvTreeNode;
TraceStack: TIvPtrStack;
I: Integer;
S: string;
begin
Memo.Clear;
TraceStack := TIvPtrStack.Create;
Iterator := Root;
TraceStack.Push(Iterator);
while TraceStack.GetTop <> nil do
begin
while Iterator <> nil do
begin
// Формирование строки и добавление ее в поле
S := '';
for I := 1 to Iterator^.Level do
S := S + ' ';
S := S + Iterator^.Data;
Memo.Lines.Add(S);
TraceStack.Push(Iterator);
Iterator := Iterator^.LeftChild;
end;
Iterator := TraceStack.Pop;
while Iterator^.RightChild = nil do
Iterator := TraceStack.Pop;
Iterator := Iterator^.RightChild;
end;
TraceStack.Free;
end;
Код:
procedure TIvFormulaTree.Paint(Canvas: TCanvas; Center: Word);
var
Iterator: PIvTreeNode;
TraceStack: TIvPtrStack;
begin
with Canvas do
begin
Brush.Color := clWhite;
Pen.Color := clBlack;
Rectangle(-1, -1, 1000, 1000);
Brush.Style := bsClear;
Font.Name := 'Courier New';
end;
// Если дерева нет, то выходим
if Root = nil then
Exit;
TraceStack := TIvPtrStack.Create;
Iterator := Root;
TraceStack.Push(Iterator);
while TraceStack.GetTop <> nil do
begin
while Iterator <> nil do
begin
// Вывод символа в листе
Canvas.TextOut(Iterator^.Position.X + Center - 3,
Iterator^.Position.Y - 7, Iterator^.Data);
// Рисование вокруг него окружности
Canvas.Ellipse(Iterator^.Position.X + Center - 10,
Iterator^.Position.Y - 10,
Iterator^.Position.X + Center + 10,
Iterator^.Position.Y + 10);
TraceStack.Push(Iterator);
// Если есть дети, то рисование линий до них
if Iterator^.LeftChild <> nil then
begin
Canvas.MoveTo(Iterator^.Position.X + Center - 5,
Iterator^.Position.Y + 5);
Canvas.LineTo(Iterator^.LeftChild^.Position.X + Center + 5,
Iterator^.LeftChild^.Position.Y - 5);
end;
if Iterator^.RightChild <> nil then
begin
Canvas.MoveTo(Iterator^.Position.X + Center + 5,
Iterator^.Position.Y + 5);
Canvas.LineTo(Iterator^.RightChild^.Position.X + Center - 5,
Iterator^.RightChild^.Position.Y - 5);
end;
Iterator := Iterator^.LeftChild;
end;
Iterator := TraceStack.Pop;
while Iterator^.RightChild = nil do
Iterator := TraceStack.Pop;
Iterator := Iterator^.RightChild;
end;
TraceStack.Free;
end;
var
Iterator: PIvTreeNode;
TraceStack: TIvPtrStack;
begin
with Canvas do
begin
Brush.Color := clWhite;
Pen.Color := clBlack;
Rectangle(-1, -1, 1000, 1000);
Brush.Style := bsClear;
Font.Name := 'Courier New';
end;
// Если дерева нет, то выходим
if Root = nil then
Exit;
TraceStack := TIvPtrStack.Create;
Iterator := Root;
TraceStack.Push(Iterator);
while TraceStack.GetTop <> nil do
begin
while Iterator <> nil do
begin
// Вывод символа в листе
Canvas.TextOut(Iterator^.Position.X + Center - 3,
Iterator^.Position.Y - 7, Iterator^.Data);
// Рисование вокруг него окружности
Canvas.Ellipse(Iterator^.Position.X + Center - 10,
Iterator^.Position.Y - 10,
Iterator^.Position.X + Center + 10,
Iterator^.Position.Y + 10);
TraceStack.Push(Iterator);
// Если есть дети, то рисование линий до них
if Iterator^.LeftChild <> nil then
begin
Canvas.MoveTo(Iterator^.Position.X + Center - 5,
Iterator^.Position.Y + 5);
Canvas.LineTo(Iterator^.LeftChild^.Position.X + Center + 5,
Iterator^.LeftChild^.Position.Y - 5);
end;
if Iterator^.RightChild <> nil then
begin
Canvas.MoveTo(Iterator^.Position.X + Center + 5,
Iterator^.Position.Y + 5);
Canvas.LineTo(Iterator^.RightChild^.Position.X + Center - 5,
Iterator^.RightChild^.Position.Y - 5);
end;
Iterator := Iterator^.LeftChild;
end;
Iterator := TraceStack.Pop;
while Iterator^.RightChild = nil do
Iterator := TraceStack.Pop;
Iterator := Iterator^.RightChild;
end;
TraceStack.Free;
end;
Вот в таком ключе. Первая процедурка делает текстом - по строчкам. Вторая - рисует на подсунутой канве. В принципе, заменяя писелы на символы, можно также отрисовывать в консоли. Главное - принцип обхода и смещений.
А, ну для полноты - описание структуры узла:
Обрати внимание на "Level". Помнится, я ввел его специально, чтобы решить кое-какие проблемы с отрисовкой. Указывается при создании дерева.
Код:
PIvTreeNode = ^TIvTreeNode;
TIvTreeNode = record
// Содержимое узла
Data: string;
// Левый и правый ребенок
LeftChild,
RightChild: PIvTreeNode;
// Позиция узла
Position: TPoint;
// Уровень узла
Level: Word;
end;
TIvTreeNode = record
// Содержимое узла
Data: string;
// Левый и правый ребенок
LeftChild,
RightChild: PIvTreeNode;
// Позиция узла
Position: TPoint;
// Уровень узла
Level: Word;
end;
Обрати внимание на "Level". Помнится, я ввел его специально, чтобы решить кое-какие проблемы с отрисовкой. Указывается при создании дерева.