การข้ามแนวเกลียวทวนเข็มนาฬิกาของต้นไม้ไบนารีเป็นการลัดเลาะองค์ประกอบของต้นไม้ในลักษณะที่ว่าหากสำรวจแล้วจะเกิดเป็นวงก้นหอย แต่จะเรียงกลับกัน รูปต่อไปนี้แสดงการเคลื่อนที่ของต้นไม้ไบนารีทวนเข็มนาฬิกาตามเข็มนาฬิกา
อัลกอริธึมที่กำหนดไว้สำหรับการข้ามผ่านแบบเกลียวของไบนารีทรีทำงานด้วยวิธีต่อไปนี้ -
สองตัวแปร i และ j ถูกเตรียมใช้งาน และค่าจะเท่ากับ i =0 และ j =ความสูงของตัวแปร แฟล็กถูกใช้เพื่อตรวจสอบในขณะที่กำลังพิมพ์ส่วน ตั้งค่าสถานะเป็นเท็จในขั้นต้น ลูปทำงานจนถึง i ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
struct Node {
struct Node* left;
struct Node* right;
int data;
Node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int height(struct Node* root) {
if (root == NULL)
return 0;
int lheight = height(root->left);
int rheight = height(root->right);
return max(1 + lheight, 1 + rheight);
}
void leftToRight(struct Node* root, int level) {
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
leftToRight(root->left, level - 1);
leftToRight(root->right, level - 1);
}
}
void rightToLeft(struct Node* root, int level) {
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
rightToLeft(root->right, level - 1);
rightToLeft(root->left, level - 1);
}
}
int main() {
struct Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(7);
root->left->left->left = new Node(10);
root->left->left->right = new Node(11);
root->right->right->left = new Node(8);
int i = 1;
int j = height(root);
int flag = 0;
while (i <= j) {
if (flag == 0) {
rightToLeft(root, i);
flag = 1;
i++;
} else {
leftToRight(root, j);
flag = 0;
j--;
}
}
return 0;
} ผลลัพธ์
1 10 11 8 3 2 4 5 7
