[Q] Thắc mắc về cây nhị phân

[anhvietabc]

_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]

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]

Giải thuật duyệt: Traversal algorithm
Đệ quy: Recursion
ko biết có đúng hông

[anhvietabc]

Đú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]

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]

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]

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

[monkeyvu]

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]

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]

* 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;