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

Anti-clockwise Spiral Traversal – Duyệt cây nhị phân theo vòng xoắn ngược chiều kim đồng hồ: cấp 1 trái→phải, cấp 2 phải→trái, cấp 3 trái→phải, ...

Thuật toán

• Tính chiều cao cây h.
• Duyệt xen kẽ: cấp lẻ (từ trên xuống) trái→phải, cấp chẵn (từ dưới lên) phải→trái.
• Dùng hai hàm đệ quy: leftToRight(level) và rightToLeft(level).

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

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

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

int main() {
    // Xây cây mẫu
    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 h = height(root);
    cout << "Anti-clockwise Spiral: ";
    for (int i = 1, j = h, flag = 0; i <= j; ) {
        if (flag == 0) { rightToLeft(root, i); flag = 1; i++; }
        else { leftToRight(root, j); flag = 0; j--; }
    }
    return 0;
}

Kết quả

Anti-clockwise Spiral: 1 10 11 8 3 2 4 5 7