Anti-Clockwise Spiral Traversal ของ Binary Tree ในภาษา C

การเดินทาง (Traversal) แบบ Anti-Clockwise Spiral: เริ่มจากราก (root) ไปขวา-ซ้าย สลับทิศทางทีละระดับ

ตัวอย่างต้นไม้

1

2 3

4 5 6 7

8 9 10 11 12 13 14 15

ลำดับ: 1, 8, 9, 10, 11, 12, 13, 14, 15, 3, 2, 4, 5, 6, 7

อัลกอริทึม

ใช้สอง pointer i (top level) และ j (bottom level) สลับทิศทางพิมพ์แต่ละระดับ

โค้ดตัวอย่าง (C++)

#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 printLeftToRight(Node* root, int level) {
    if (!root) return;
    if (level == 1) cout << root->data << " ";
    else { printLeftToRight(root->left, level-1); printLeftToRight(root->right, level-1); }
}

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

void antiClockwise(Node* root) {
    int i = 1, j = height(root), flag = 0;
    while (i <= j) {
        if (!flag) { printRightToLeft(root, i); flag = 1; i++; }
        else { printLeftToRight(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);
    antiClockwise(root);
    return 0;
}

ผลลัพธ์

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