Duyệt cây không dùng đệ quy và stack _Lập trình C++ căn bản

*)Giới thiệu:

- Những thao tác trên cây thường rất đa dạng, mỗi loại thao tác lại có những phương thức và cách thao tác khác nhau. Thường thì người ta sẽ dùng đệ quy để tránh sự dài dòng, rắc rối. Chính vì đó, trong các tài liệu học tập trên trường học người ta ít đề cập đến việc thao tác với cây mà KHÔNG cần dùng đệ quy. Vậy hôm nay mình xin giới thiệu với các bạn cách duyệt cây nhị phân tìm kiếm theo kiểu InOrder(duyệt LNR) để minh họa.  Các kiểu duyệt khác (PreOrder, PostOrder,...) các bạn tự điều chỉnh lại cho phù hợp.

*) Đối tượng hướng đến:

 - Các bạn đang học lập trình C++, cấu trúc dữ liệu và giải thuật, có kiến thức vững chắc về con trỏ, cây nhị phân.

*) Nội dung: 

từ trước đến nay, khi tạo một cây thì chúng ta luôn thấy các nút lá có 2 con trỏ left và right là NULL(đây là dấu hiệu để nhận biết nó là nút lá(nói hơi thừa 😁😁😁😁)), ta sẽ lợi dụng các nút trống này để kết nối với các Node "tổ tiên" của nó. Những tác vụ này khiến các Node trên cây sẽ liên kết với nhau một cách chặt chẽ,các nút lá cũng có "con", mà "con" ở đây lại là "tổ tiên" của chính nó, nghe thật là rắc rối phải không nào? Nhưng tất nhiên việc kết nối như thế nào thì phải cần có một thuật toán tương đối khó (với những người như chúng ta, chứ mấy ông thánh thì không nói rồi😁😁😁😁), Thông qua thuật toán kết nối đó cùng với vòng lặp while, một chút khéo léo sử dụng câu lệnh if, chúng ta có thể xuất ra các giá trị trên từng Node theo một thứ tự nào đó trên cây nhị phân(ở đây đang đề cập cây nhị phân tìm kiếm). Sau đây là một bài toán minh họa, thêm các phần tử vào cây, nhập số 0 để kết thúc quá trình nhập, sau đó duyệt kiểu InOrder mà không cần đệ quy, không cần stack, mời các bạn tham khảo code sau:

#include <iostream>
using namespace std;

struct Node{
int val;
Node *left, *right;
};

void add_node(Node* &root, int x){
if (root == NULL){
root = new Node;
root->val = x;
root->left = root->right = NULL;
}
else {
if (x < root->val) add_node(root->left, x);
else if (x > root->val) add_node(root->right, x);
}
}

/* Function to traverse binary tree without recursion and
without stack */
void lnr(Node *root)
{
Node*pre;
Node*current=root;
while (current)
{
if (!current->left)
{
cout << current->val << "\n";
current = current->right;
}
else
{
pre = current->left;
while (pre->right&&pre->right != current)
{
pre = pre->right;
}
if (!pre->right)
{
pre->right = current;
current = current->left;
}
else
{
cout << current->val << "\n";
pre->right = NULL;
current = current->right;
}
}
}
}


int height(Node* t){
if (t){
int l = height(t->left), r = height(t->right);
return (l < r ? r : l) + 1;
}
return 0;
}
int main()
{

Node* root = NULL;

while (true){
int x; cin >> x;
if (x == 0) break;
add_node(root, x);
}

lnr(root);

return 0;
}