C语言采用二叉链表作为二叉树的存储结构，编写程 序，实现下述功能： 1、实现二叉树的创建、先中后序递归遍历、销 毁。 。（必做） 2、实现二叉树的层次遍历、中序非递归遍历、求 二叉树的深度、求叶子结点个数、交换左右子树 等。 （选做）

在C语言中，我们首先定义二叉链表结构用于表示二叉树，然后实现相应的操作。以下是基本的二叉树结构及一些核心功能的实现：

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

// 定义二叉树节点
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
    struct TreeNode* next; // 层次遍历时的指针
} TreeNode;

// 创建新节点
TreeNode* create_node(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = val;
    node->left = node->right = node->next = NULL;
    return node;
}

// 插入节点（二叉链表形式）
void insert(TreeNode** root, int val) {
    if (*root == NULL) {
        *root = create_node(val);
    } else {
        TreeNode* cur = *root;
        while (cur->next != NULL) {
            cur = cur->next;
        }
        cur->next = create_node(val);
    }
}

// 先序遍历（递归）
void preorder_traversal(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder_traversal(root->left);
        preorder_traversal(root->right);
    }
}

// 中序遍历（递归）
void inorder_traversal(TreeNode* root) {
    if (root != NULL) {
        inorder_traversal(root->left);
        printf("%d ", root->data);
        inorder_traversal(root->right);
    }
}

// 后序遍历（递归）
void postorder_traversal(TreeNode* root) {
    if (root != NULL) {
        postorder_traversal(root->left);
        postorder_traversal(root->right);
        printf("%d ", root->data);
    }
}

// 水平遍历（层序遍历）
void level_order_traversal(TreeNode* root) {
    if (root == NULL) return;
    TreeNode* queue[100]; // 假设最大100层
    int front = rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode* cur = queue[front++];
        printf("%d ", cur->data);
        if (cur->left) queue[rear++] = cur->left;
        if (cur->right) queue[rear++] = cur->right;
    }
}

// 非递归中序遍历
void iterative_inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    TreeNode* curr = root;
    
    while (curr || !s.isEmpty()) {
        while (curr) {
            s.push(curr);
            curr = curr->left;
        }
        
        curr = s.pop();
        printf("%d ", curr->data);
        curr = curr->right;
    }
}

// 另外的选做部分：
// 求树的深度
int max_depth(TreeNode* root) {
    if (root == NULL) return 0;
    int left_depth = max_depth(root->left);
    int right_depth = max_depth(root->right);
    return 1 + MAX(left_depth, right_depth);
}

// 求叶节点个数
int count_leaves(TreeNode* root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return count_leaves(root->left) + count_leaves(root->right);
}

// 交换左右子树
void swap_left_right(TreeNode** root) {
    if (*root) {
        TreeNode* temp = (*root)->left;
        (*root)->left = (*root)->right;
        (*root)->right = temp;
    }
}

// 销毁二叉树
void destroy_tree(TreeNode** root) {
    if (*root) {
        destroy_tree(&(*root)->left);
        destroy_tree(&(*root)->right);
        free(*root);
        *root = NULL;
    }
}

int main() {
    TreeNode* root = NULL;
    // ... 实现插入和其他操作 ...
    return 0;
}

相关问题：
1. 层次遍历和非递归中序遍历的区别是什么？
2. 怎么通过栈来实现非递归中序遍历？
3. 求二叉树深度的最坏时间复杂度是多少？