PDA

View Full Version : [Q] Thắc mắc về cây nhị phân



anhvietabc
25-05-2003, 08:11
_Mình đang bí không biết làm sao có thể viết được các giải thuật
duyệt cây nhị phân(preorder,inorder,postorder)mà không dùng đệ quy(khử đệ quy),mình đã thử dùng stack nhưng càng làm càng rối,các bạn giúp mình với.

mqt
25-05-2003, 20:21
Muốn trả lời cho bạn lắm nhưng mình thật sự không hiểu những chữ tiếng Việt này. :.(

Giải thuật duyệt là gì?
đệ quy là gì?

Bạn có thể giả thích ngắn gọn để mình coi những cái này gọi là gì trong tiếng Mỹ được không?

tại sao bạn đang muốn implement tree mà lại dùng stack trong này?

Mach2
25-05-2003, 23:03
Giải thuật duyệt: Traversal algorithm
Đệ quy: Recursion
ko biết có đúng hông ;)

anhvietabc
27-05-2003, 17:08
Đúng rồi đó,trong tiếng Mỹ giải thuật duyệt gọi là Traversal algorithm,còn Đệ quy gọi là Recursion
_Giải thuật duyệt cây tức là tìm cách đi qua được hết các nút trong cây,có 3 cách duyệt cây:duyệt đầu ,sau và giữa(preorder,postorder,inorder).
_Giải thuật duyệt cây trong hầu hết các tài liệu mình tìm thấy chỉ hướng dẫn cài đặt theo cách đệ quy,giờ minh đang thử làm theo kiểu không đệ quy(non recursion),mình có nghe gợi ý là cần làm bằng stack nên thử làm mà chưa được.

monkeyvu
28-05-2003, 02:43
procedure Tree_insert(x:integer);
var
p1,p2:ref;
d:integer;
begin
p2:=Head;
p1:=p2^.Right;
d:=1;
while (p1<>nil) and (d<>0) do
begin
p2:=p1;
if x<p1^.key then
begin
p1:=p1^.Left;
d:=-1;
end;
else
if x>p1^.key then
begin
p1:=p1^.Right;
d:=1
end
else d:=0;
end;
if d=0 then p1^.Count:=p1^.Count+1
else
begin
new(p1);
with(p1^) do
begin
key:=x;count:=1;
left:=nil;Right:=nil;
end;
if d<0 then p2^.left:=p1
else p2^.Right:=p1;
end
end;

mqt
29-05-2003, 22:44
Mới nghĩ long weekend xong quá đã!!! :)

anhvietabc,
bạn kiếm đâu ra cái đề ác nhơn vậy?! Sao không cho xài recursive cho nó phẻ trời.

OK. Ở đây mqt chỉ có làm cho preorder thôi nha. Bạn figure out inorder và postorder. Cũng giống giống như vậy thôi.


typedef node *link; // node là một node trong tree
void visit (link); // subroutine này chỉ để visit a node.
stack s;
/*
có hai implementations khác nhau cho function pop của stack.
Ở đây, mqt chọn pop là lấy item ra khỏi stack và return value.
Cách kia thì chỉ lấy item ra khỏi stack thôi chứ không có return
value.
*/

void traverse (link n, void visit (link)) {
link cur = n; // node đang được visit.

while (cur != 0) {
visit (cur);
s.push (cur);
cur = cur->left;
}

while (!s.empty()) {
cur = s.pop();
cur = cur->right;

while (cur != 0) {
visit (cur);
s.push(cur);
cur = cur->left;
}
}
}

mqt chưa có test nha. Nếu bạn thấy có problem thì cho mqt biết. Cái idea dùng stack của bạn thiệt là có lý. :)

anhvietabc
30-05-2003, 18:01
mình cám ơn bạn mqt rất nhiều .
Đề này mình chỉ tự nghĩ ra để tập làm quen với cả 2 cách làm là đệ quy và không đệ quy thôi ,làm bằng đệ quy tuy khoẻ thiệt đó nhưng chưa chắc đã là tối ưu nhất và hay nhất
:D

monkeyvu
30-05-2003, 23:50
Bạn dzì đó ơi,bạn đi mua cuốn Cấu trúc dữ liệu của Nguyễn Trung Trực về mà coi,nó có đủ cả cách đệ quy và không đệ quy đấy thôi.

mqt
31-05-2003, 07:40
Leehee. Làm mình tưởng có ông thầy nào cắc cớ.
Mình đồng ý. Cho nhiều khi đệ quy không có tốt lắm về performance.

oak
19-07-2003, 06:59
* Giải thuật IN_ORDER:

Procedure INORDER(TreeTOP:TreePointer);
Var
TOP:StackPointer;
P:TreePointer;
Begin
If TreeTOP=NIL then Write('Cay rong')
Else
Begin
TOP:=NIL;
P:=TreeTOP;

Repeat
While P<>NIL do
Begin
PUSH(TOP,P);
P:=P^.Left;
End;

POP(TOP,P);
Writeln(P^.Node);
P:=P^.Right;
Until (TOP=NIL) And (P=NIL);
End;
End;

{-----------------------}

* Giải thuật POST_ORDER:

Procedure POSTORDER(TreeTOP:TreePointer);
Var
TOP:StackPointer;
P:TreePointer;
Begin
If TreeTOP=NIL then Write('Cay rong')
Else
Begin
TOP:=NIL;
P:=TreeTOP;

While TRUE do
Begin
While P<>NIL do
Begin
PUSH(TOP,P);
P:=P^.Left;
End;

While TOP^.Number < 0 do
Begin
POP(TOP,P);
Writeln(P^.Node);

If TOP=NIL then Exit;
End;

P:=TOP^.TreeLink;
P:=P^.Right;
TOP^.Number:=-TOP^.Number;
End;
End;
End;

kimphuc
13-12-2004, 09:09
{Chuong trinh duoi day toi da test chay tot roi}
Type Arr= Array[1..50] of Integer;
Link = ^node;
node = Record
Value:Integer;
l,r:link
End;

{Inoder}
{Truong hop co de qui}
Procedure Inorder(Node : Link);
Begin
if Node<>nil then
Begin
inorder(node^.l);
Write(node^.value,' ');
inorder(node^.r);
End;
End;

{Truong hop khong de qui}

Procedure Inorder_NonRecursion(Node : Link);
Label 1,2,3;
Var STN : Array[1..50] of Link;
Top,Addr_Return : Integer;
STADDR : Arr;
Begin
Top:=0;
1: if Node=nil then goto 3;
Inc(Top);
STN[Top]:=Node;
STADDR[Top]:=2;
Node:=Node^.L;
Goto 1;
2: Write(node^.value,' ');
Inc(Top);
STN[Top]:=Node;
STADDR[Top]:=3;
Node:=Node^.r;
Goto 1;
3: If Top<>0 then
Begin
Node:=STN[Top];
Addr_Return:=STADDR[Top];
Dec(Top);
If Addr_Return=2 then goto 2
Else goto 3;
End;
End;

{Postorder}
{Truong ho co su dung de qui}
Procedure Postorder(Node : Link);
Begin
if Node<>nil then
Begin
Postorder(node^.l);
Postorder(node^.r);
Write(node^.value,' ');
End;
End;
{Truong hop khong de qui}
Procedure Postorder_NonRecursion(Node : Link);
Label 1,2,3;
Var STN : Array[1..50] of Link;
Top,Addr_Return : Integer;
STADDR : Arr;
Begin
Top:=0;
1: if Node=nil then goto 3;
Inc(Top);
STN[Top]:=Node;
STADDR[Top]:=2;
Node:=Node^.L;
Goto 1;
2: Inc(Top);
STN[Top]:=Node;
STADDR[Top]:=3;
Node:=Node^.r;
Goto 1;
3: If Node<>nil then Write(Node^.value,' ');
If Top<>0 then
Begin
Node:=STN[Top];
Addr_Return:=STADDR[Top];
Dec(Top);
If Addr_Return=2 then goto 2
Else goto 3;
End;
End;

nguyennhunai
03-03-2014, 11:21
anh mqt, em mới học về tree nên chưa hiểu chương trình của anh lắm, anh có thể chỉ cho cách thức hoạt động của biển cur được không ạ???

kimphuc
03-03-2014, 11:30
anh mqt, em mới học về tree nên chưa hiểu chương trình của anh lắm, anh có thể chỉ cho cách thức hoạt động của biển cur được không ạ???

Hi Em, Cái này lúc trước a đăng khi a đang học KS2, giờ a bỏ lâu lắm rùi, nên a không nhớ để giúp e được. Nhưng những gì a đăng là a đã chạy, e đọc thêm để hiểu chứ a ko nhớ. Chúc e thành công nhé

deid
25-03-2014, 09:35
Sao ko đọc sách, có hết trong sách mà !