Dưới đây là chương trình C++ triển khai duyệt thứ tự kép (Double Order Traversal) của cây nhị phân.
Trong duyệt thứ tự kép, gốc của cây con sẽ được duyệt hai lần.
Thuật toán
Bắt đầu
Lớp BST có các hàm sau:
insert() = chèn phần tử vào cây:
Nhập gốc.
Nhập giá trị nút, nếu lớn hơn gốc thì chèn phải, ngược lại chèn trái.
doubleOrder() = Thực hiện inorder:
Nếu root = null
In "cây rỗng"
Ngược lại thực hiện:
Ghé thăm gốc của (cây con).
Ghé thăm cây con trái.
Ghé thăm lại gốc của (cây con).
Ghé thăm cây con phải.
Kết thúc
Mã ví dụ
#include <iostream>
#include <cstdlib>
using namespace std;
struct nod {
int info;
struct nod *l;
struct nod *r;
}*r;
class BST {
public:
void insert(nod *, nod *);
void doubleOrder(nod *);
void show(nod *, int);
BST() {
r = NULL;
}
};
void BST::insert(nod *tree, nod *newnode) {
if (r == NULL) {
r = new nod;
r->info = newnode->info;
r->l = NULL;
r->r = NULL;
cout << "Root Node is Added" << endl;
return;
}
if (tree->info == newnode->info) {
cout << "Element already in the tree" << endl;
return;
}
if (tree->info > newnode->info) {
if (tree->l != NULL) {
insert(tree->l, newnode);
} else {
tree->l = newnode;
(tree->l)->l = NULL;
(tree->l)->r = NULL;
cout << "Node Added To Left" << endl;
return;
}
} else {
if (tree->r != NULL) {
insert(tree->r, newnode);
} else {
tree->r = newnode;
(tree->r)->l = NULL;
(tree->r)->r = NULL;
cout << "Node Added To Right" << endl;
return;
}
}
}
void BST::doubleOrder(nod *ptr) {
if (r == NULL) {
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL) {
cout << ptr->info << " ";
doubleOrder(ptr->l);
cout << ptr->info << " ";
doubleOrder(ptr->r);
}
}
void BST::show(nod *ptr, int level) {
int i;
if (ptr != NULL) {
show(ptr->r, level + 1);
cout << endl;
if (ptr == r)
cout << "Root->: ";
else {
for (i = 0; i < level; i++)
cout << " ";
}
cout << ptr->info;
show(ptr->l, level + 1);
}
}
int main() {
int c, n;
BST bst;
nod *t;
while (1) {
cout << "1. Chèn phần tử" << endl;
cout << "2. Duyệt Double-Order" << endl;
cout << "3. Hiển thị" << endl;
cout << "4. Thoát" << endl;
cout << "Nhập lựa chọn: ";
cin >> c;
switch (c) {
case 1:
t = new nod;
cout << "Nhập số cần chèn: ";
cin >> t->info;
bst.insert(r, t);
break;
case 2:
cout << "Duyệt Double-Order của BST:" << endl;
bst.doubleOrder(r);
cout << endl;
break;
case 3:
cout << "In BST:" << endl;
bst.show(r, 1);
cout << endl;
break;
case 4:
exit(1);
default:
cout << "Lựa chọn sai" << endl;
}
}
}
Kết quả đầu ra
1. Chèn phần tử 2. Duyệt Double-Order 3. Hiển thị 4. Thoát Nhập lựa chọn: 1 Nhập số cần chèn: 7 Root Node is Added 1. Chèn phần tử 2. Duyệt Double-Order 3. Hiển thị 4. Thoát Nhập lựa chọn: 1 Nhập số cần chèn: 6 Node Added To Left 1. Chèn phần tử 2. Duyệt Double-Order 3. Hiển thị 4. Thoát Nhập lựa chọn: 1 Nhập số cần chèn: 4 Node Added To Left 1. Chèn phần tử 2. Duyệt Double-Order 3. Hiển thị 4. Thoát Nhập lựa chọn: 1 Nhập số cần chèn: 2 Node Added To Left 1. Chèn phần tử 2. Duyệt Double-Order 3. Hiển thị 4. Thoát Nhập lựa chọn: 1 Nhập số cần chèn: 10 Node Added To Right 1. Chèn phần tử 2. Duyệt Double-Order 3. Hiển thị 4. Thoát Nhập lựa chọn: 3 In BST: 10 Root->: 7 6 4 2 1. Chèn phần tử 2. Duyệt Double-Order 3. Hiển thị 4. Thoát Nhập lựa chọn: 2 Duyệt Double-Order của BST: 7 6 4 2 2 4 6 7 10 10 1. Chèn phần tử 2. Duyệt Double-Order 3. Hiển thị 4. Thoát Nhập lựa chọn: 4