Duyệt cây nhị phân xoắn ngược chiều kim đồng hồ trong C++

Duyệt cây nhị phân theo chiều xoắn ốc ngược chiều kim đồng hồ: mức 1 trái→phải, mức 2 phải→trái, mức 3 trái→phải...

Thuật toán

2 con trỏ i (từ trên xuống), j (từ dưới lên). Flag đổi chiều. In mức i trái→phải, mức j phải→trái, xen kẽ.

Chương trình

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int d) : data(d), left(NULL), right(NULL) {}
};

int height(Node* root) {
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}

void printL2R(Node* root, int level) {
    if (!root) return;
    if (level == 1) cout << root->data << " ";
    else { printL2R(root->left, level-1); printL2R(root->right, level-1); }
}

void printR2L(Node* root, int level) {
    if (!root) return;
    if (level == 1) cout << root->data << " ";
    else { printR2L(root->right, level-1); printR2L(root->left, level-1); }
}

void antiClock(Node* root) {
    int i = 1, j = height(root), flag = 0;
    while (i <= j) {
        if (!flag) { printR2L(root, i); flag = 1; i++; }
        else { printL2R(root, j); flag = 0; j--; }
    }
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2); root->right = new Node(3);
    root->left->left = new Node(4); root->left->right = new Node(5);
    root->right->left = new Node(6); root->right->right = new Node(7);
    root->left->left->left = new Node(8); root->left->left->right = new Node(9);
    root->left->right->left = new Node(10); root->left->right->right = new Node(11);
    root->right->left->left = new Node(12); root->right->left->right = new Node(13);
    root->right->right->left = new Node(14); root->right->right->right = new Node(15);
    
    antiClock(root);
    return 0;
}

Kết quả

1 8 9 10 11 12 13 14 15 3 2 4 5 6 7