Nếu cây nhị phân được duyệt trung thứ tự (in-order), cây con trái được thăm trước, rồi gốc, sau đó cây con phải. Kết quả duyệt in-order cho ra các khóa theo thứ tự tăng dần. Đây là chương trình C++ duyệt cây trung thứ tự không dùng đệ quy.
Thuật toán
Begin
Khai báo cấu trúc n.
Khai báo d kiểu nguyên.
Khai báo con trỏ l trỏ đến cấu trúc n.
Khai báo con trỏ r trỏ đến cấu trúc n.
Khai báo hàm tạo của cấu trúc n.
Truyền biến nguyên d làm tham số.
this->d = d
l = r = NULL
Khai báo hàm inOrder(struct n *root).
Khai báo stack s.
Khai báo con trỏ current trỏ đến cấu trúc n.
Khởi tạo n *current = root.
while (current != NULL || s.empty() == false)
while (current != NULL)
s.push(current)
current = current->l
current = s.top()
s.pop()
in current->d.
current = current->r.
Chèn giá trị vào các nút của cây.
Gọi inOrder(root) để duyệt cây.
End.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
struct n {
int d;
struct n* l;
struct n* r;
n (int d) {
this->d = d;
l = r = NULL;
}
};
void inOrder(struct n *root) {
stack<n *> s;
n *current = root;
while (current != NULL || s.empty() == false) {
while (current != NULL) {
s.push(current);
current = current->l;
}
current = s.top();
s.pop();
cout << current->d << " ";
current = current->r;
}
}
int main() {
struct n* root = new n(6);
root->l = new n(4);
root->r= new n(7);
root->l->l = new n(8);
root->l->r= new n(5);
root->r->l = new n(9);
root->r->r = new n(10);
inOrder(root);
return 0;
}
Kết quả
8 4 5 6 9 7 10