//print_array 函數
//
//功能：打印一維數組的元素。
//參數：arr - 要打印的數組，n - 數組的大小。
//返回值：無。
//preorder 函數
//
//功能：執行二叉樹數組的先序遍歷並打印元素。
//參數：arr - 二叉樹數組，i - 當前節點索引，n - 數組大小。
//返回值：無。
//inorder 函數
//
//功能：執行二叉樹數組的中序遍歷並打印元素。
//參數：arr - 二叉樹數組，i - 當前節點索引，n - 數組大小。
//返回值：無。
//postorder 函數
//
//功能：執行二叉樹數組的後序遍歷並打印元素。
//參數：arr - 二叉樹數組，i - 當前節點索引，n - 數組大小。
//返回值：無。
//levelorder 函數
//
//功能：執行二叉樹數組的層序遍歷並打印元素。
//參數：arr - 二叉樹數組，n - 數組大小。
//返回值：無。
//iterative_preorder 函數
//
//功能：使用迭代方法執行二叉樹數組的先序遍歷並打印元素。
//參數：arr - 二叉樹數組，n - 數組大小。
//返回值：無。
//iterative_inorder 函數
//
//功能：使用迭代方法執行二叉樹數組的中序遍歷並打印元素。
//參數：arr - 二叉樹數組，n - 數組大小。
//返回值：無。
//iterative_postorder 函數
//
//功能：使用迭代方法執行二叉樹數組的後序遍歷並打印元素。
//參數：arr - 二叉樹數組，n - 數組大小。
//返回值：無。
//generate_tree 函數
//
//功能：生成包含隨機數的數組。
//參數：tree - 要填充的數組，size - 數組大小。
//返回值：無。
//generate_skewed_tree 函數
//
//功能：生成包含隨機數的數組，呈現左偏樹或右偏樹的形式。
//參數：arr - 要填充的數組，size - 數組大小，skew_factor - 1 表示左偏樹，2 表示右偏樹。
//返回值：無。
//main 函數
//
//功能：程序的入口點，調用其他函數展示不同的數組遍歷方式。
//參數：無。
//返回值：0（程序運行成功）。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 40

// Function to print the array
void print_array(int arr[], int n) {
    int element_in_one_line = 10;
	int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
        if ((i + 1) % element_in_one_line == 0) printf("\n");
    }
}

// Preorder traversal
void preorder(int arr[], int i, int n) {
    if (i < n) {
        printf("%d ", arr[i]);
        preorder(arr, 2 * i + 1, n);
        preorder(arr, 2 * i + 2, n);
    }
}

// Inorder traversal
void inorder(int arr[], int i, int n) {
    if (i < n) {
        inorder(arr, 2 * i + 1, n);
        printf("%d ", arr[i]);
        inorder(arr, 2 * i + 2, n);
    }
}

// Postorder traversal
void postorder(int arr[], int i, int n) {
    if (i < n) {
        postorder(arr, 2 * i + 1, n);
        postorder(arr, 2 * i + 2, n);
        printf("%d ", arr[i]);
    }
}

// Level order traversal
void levelorder(int arr[], int n) {
    int i;
	for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
}

// Iterative preorder traversal
void iterative_preorder(int arr[], int n) {
    int stack[SIZE], top = -1;
    int curr = 0;

    while (curr < n || top != -1) {
        while (curr < n) {
            printf("%d ", arr[curr]);  // Print before going to the left subtree
            stack[++top] = curr;
            curr = 2 * curr + 1;
        }

        curr = stack[top--];
        curr = 2 * curr + 2;  // Move to the right subtree
    }
}

// Iterative inorder traversal
void iterative_inorder(int arr[], int n) {
    int stack[SIZE], top = -1;
    int curr = 0;

    while (curr < n || top != -1) {
        while (curr < n) {
            stack[++top] = curr;
            curr = 2 * curr + 1;
        }

        curr = stack[top--];
        printf("%d ", arr[curr]);
        curr = 2 * curr + 2;
    }
}

// Iterative postorder traversal
void iterative_postorder(int arr[], int n) {
    int stack1[SIZE], stack2[SIZE];
    int top1 = -1, top2 = -1;
    int curr = 0;

    stack1[++top1] = curr;

    while (top1 != -1) {
        curr = stack1[top1--];
        stack2[++top2] = curr;

        if (2 * curr + 1 < n)  // Left child
            stack1[++top1] = 2 * curr + 1;
        if (2 * curr + 2 < n)  // Right child
            stack1[++top1] = 2 * curr + 2;
    }

    while (top2 != -1) {
        printf("%d ", arr[stack2[top2--]]);
    }
}


void generate_tree(int tree[], int size) {
    int range = 100, offset = 1, len = size;
    srand(time(NULL));
    int i;
	for (i = 0; i < len; i++)
        tree[i] = rand() % range + offset;
}

void generate_skewed_tree(int arr[], int size, int skew_factor) {    // 1 for left skewed, 2 for right skewed
    int range = 100, offset = 1;
    srand(time(NULL));
	int i;
    for (i = 0; i < size; i = i * 2 + skew_factor) {
        arr[i] = rand() % range + offset;
    }
}


int main() {
    int tree[SIZE] = {0};

    // (a) Generate random numbers and insert into the tree
    generate_tree(tree, SIZE);
    // generate_skewed_tree(tree, SIZE, 2);    // 1 for left skewed, 2 for right skewed

    // Print the generated numbers
    print_array(tree, SIZE);    // default 10 elements in one line
    printf("\n");

    // (b) Preorder traversal
    printf("Preorder traversal:\n");
    preorder(tree, 0, SIZE);
    printf("\n\n");

    // (c) Inorder traversal
    printf("Inorder traversal:\n");
    inorder(tree, 0, SIZE);
    printf("\n\n");

    // (d) Postorder traversal
    printf("Postorder traversal:\n");
    postorder(tree, 0, SIZE);
    printf("\n\n");

    // (e) Level order traversal
    printf("Level order traversal:\n");
    levelorder(tree, SIZE);
    printf("\n\n");

    // (f) Iterative inorder traversal
    printf("Iterative inorder traversal:\n");
    iterative_inorder(tree, SIZE);
    printf("\n\n");

    // (*) Iterative preorder traversal
    printf("Iterative preorder traversal:\n");
    iterative_preorder(tree, SIZE);
    printf("\n\n");

    // (*) Iterative postorder traversal
    printf("Iterative postorder traversal:\n");
    iterative_postorder(tree, SIZE);
    printf("\n\n");

    return 0;
}