使用二叉链表创建一棵二叉树，并完成如下操作： （1） 对这棵二叉树分别进行先序、中序、后序和层序遍历； （2） 统计这棵二叉树的深度、叶子结点数、结点总数； （3） 销毁这棵二叉树（提示：使用后序遍历的方法）。 （4）判断两颗树是否相等 （5）计算二叉树的深度 （6）复制二叉树 （7）交换二叉树每个结点的左右孩子

二叉树的数据结构定义：

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node, *Tree;

其中，`data`表示节点存储的数据，`left`和`right`分别指向左右子节点。

1. 先序遍历

先访问根节点，再访问左子树，最后访问右子树。代码如下：

void preOrder(Tree root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

2. 中序遍历

先访问左子树，再访问根节点，最后访问右子树。代码如下：

void inOrder(Tree root) {
    if (root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

3. 后序遍历

先访问左子树，再访问右子树，最后访问根节点。代码如下：

void postOrder(Tree root) {
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

4. 层序遍历

从根节点开始，按照从上到下、从左到右的顺序依次访问每个节点。代码如下：

void levelOrder(Tree root) {
    if (root == NULL) return;
    Queue queue;  // 队列用于存储待访问的节点
    initQueue(&queue);
    enqueue(&queue, root);  // 将根节点入队
    while (!isEmpty(queue)) {
        Tree node = dequeue(&queue);  // 取出队首元素
        printf("%d ", node->data);
        if (node->left != NULL) {
            enqueue(&queue, node->left);  // 左子节点入队
        }
        if (node->right != NULL) {
            enqueue(&queue, node->right);  // 右子节点入队
        }
    }
    destroyQueue(&queue);
}

5. 统计二叉树的深度、叶子节点数和节点总数

深度可以通过递归计算左右子树的深度，然后取较大值再加1得到。叶子节点数可以通过递归计算左右子树的叶子节点数，如果当前节点没有左右子树，就说明它是叶子节点。节点总数可以通过递归计算左右子树的节点总数，然后加上1得到。代码如下：

int depth(Tree root) {
    if (root == NULL) return 0;
    int leftDepth = depth(root->left);
    int rightDepth = depth(root->right);
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

int leafCount(Tree root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return leafCount(root->left) + leafCount(root->right);
}

int nodeCount(Tree root) {
    if (root == NULL) return 0;
    return nodeCount(root->left) + nodeCount(root->right) + 1;
}

6. 销毁二叉树

通过后序遍历的方式销毁二叉树，先销毁左右子树，最后销毁根节点。代码如下：

void destroyTree(Tree root) {
    if (root == NULL) return;
    destroyTree(root->left);
    destroyTree(root->right);
    free(root);
}

7. 判断两棵树是否相等

如果两棵树都为空，则它们相等；如果其中一个为空而另一个不为空，则它们不相等；如果两个根节点的数据不相等，则它们不相等；否则分别递归比较左右子树。代码如下：

bool isEqual(Tree t1, Tree t2) {
    if (t1 == NULL && t2 == NULL) return true;
    if (t1 == NULL || t2 == NULL) return false;
    if (t1->data != t2->data) return false;
    return isEqual(t1->left, t2->left) && isEqual(t1->right, t2->right);
}

8. 计算二叉树的深度

可以使用层序遍历的方式，每一层节点的个数就是该层的深度。代码如下：

int depth(Tree root) {
    if (root == NULL) return 0;
    Queue queue;
    initQueue(&queue);
    enqueue(&queue, root);
    int depth = 0;
    while (!isEmpty(queue)) {
        int size = getSize(queue);  // 当前层的节点个数
        depth++;
        for (int i = 0; i < size; i++) {
            Tree node = dequeue(&queue);
            if (node->left != NULL) {
                enqueue(&queue, node->left);
            }
            if (node->right != NULL) {
                enqueue(&queue, node->right);
            }
        }
    }
    destroyQueue(&queue);
    return depth;
}

9. 复制二叉树

可以使用先序遍历的方式，先复制当前节点，然后递归复制左右子树。代码如下：

Tree copyTree(Tree root) {
    if (root == NULL) return NULL;
    Tree node = (Tree) malloc(sizeof(Node));
    node->data = root->data;
    node->left = copyTree(root->left);
    node->right = copyTree(root->right);
    return node;
}

10. 交换二叉树每个节点的左右孩子

可以使用先序遍历的方式，对于每个节点，交换它的左右孩子，然后递归交换左右子树。代码如下：

void swapChildren(Tree root) {
    if (root == NULL) return;
    Tree temp = root->left;
    root->left = root->right;
    root->right = temp;
    swapChildren(root->left);
    swapChildren(root->right);
}