1. kiểm tra rỗng
nếu cây rỗng thì kết thúc
nếu không rỗng thì khởi tạo stack
2. thực hiện duyệt
in ra khóa của nút gốc
nếu cây con phải khác rỗng thì lưu địa chỉ gốc cây con phải vào stack
chuyển xuống cây con trái, in ra khóa của nút con trái... (lặp lại)
P_L Trỏ tới cây con trái
DATA Chứa dữ liệu
P_R Trỏ tới cây con phải
TT_TRUOC(TREE){
if(TREE == NULL){
printf("Cây rỗng");
return; //thoát hàm luôn
}else{ //không rỗng
TOP = -1;
PUSH(STACK, TOP, TREE);
}
while(TOP > -1){
P = POP(STACK, TOP);
while(P != NULL){
printf(P->DATA) //thăm nút P
if(P->P_R){
PUSH(STACK, TOP, P->P_R); //lưu địa chỉ nhánh bên phải để tí POP ra
}
P = P->P_L;
}
}
}
6. Trình bày (bằng ngôn ngữ tựa C) giải thuật duyệt cây theo thứ tự giữa bằng giải thuật không đệ qui có sử dụng STACK. Mỗi nút trên cây có cấu trúc như sau:
Ý tưởng:
1. kiểm tra rỗng
nếu cây rỗng thì kết thúc
nếu không rỗng thì khởi tạo stack
2. thực hiện duyệt
lưu địa chỉ của nút gốc vào stack, chuyển xuống cây con trái (lặp lại bước này tới
khi cây con trái là rỗng)
lấy phần tử trên cùng ra khỏi stack, trỏ vào vị trí của nút đó trên cây
in ra khóa của nút đang xét
trỏ đến cây con phải
.... (lặp lại cho tới khi stack rỗng)
P_L Trỏ tới cây con trái
DATA Chứa dữ liệu
P_R Trỏ tới cây con phải
TT_GIUA(TREE){
if(TREE == NULL){
printf("Cay rong");
Chia sẻ với bạn bè của bạn: |
