Đi ngang theo đường xoắn ốc Ngược chiều kim đồng hồ của cây nhị phân là đi qua các phần tử của cây theo cách mà nếu đi qua chúng sẽ tạo thành một đường xoắn ốc nhưng theo thứ tự ngược lại. Hình dưới đây cho thấy cách thức đi qua xoắn ốc ngược chiều kim đồng hồ của cây nhị phân.
Thuật toán được xác định cho truyền theo đường xoắn ốc của cây nhị phân hoạt động theo cách sau -
Hai biến i và j được khởi tạo và các giá trị được gọi là i =0 và j =chiều cao của biến. Một cờ được sử dụng để kiểm tra phần trong khi sẽ được in. Cờ ban đầu được đặt là sai. Một vòng lặp hoạt động cho đến khi i Ví dụ
#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;
} Đầu ra
1 10 11 8 3 2 4 5 7