c语言实验： 二叉树基本操作 实验要求： 1．按先序序列构造一棵二叉链表表示的二叉树T； 2．对这棵二叉树进行递归遍历：先序、中序、后序以及层次遍历遍历序列，分别输出结点的遍历序列； 3. 对这棵树用非递归方式进行遍历：先序、中序以及后序遍历序列，分别输出结点的遍历序列； 4．求二叉树的深度/结点数目/叶结点数目； 5．将二叉树每个结点的左右子树交换位置； 6. 设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）； 7. 计算二叉树最大宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）； 8. 求二叉树中第一条最长的路径长度，并输出此路径上各结点。

很好，这是一个比较全面的二叉树操作实验，我们可以一步一步来完成。

1. 按先序序列构造一棵二叉链表表示的二叉树T

先序序列构造二叉树的方法是：从先序序列中取出一个元素作为根节点，然后将剩余序列分成左子树和右子树两个部分，递归构造左右子树。代码如下：

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* buildTree(int* preorder, int preorderSize) {
    if (preorderSize == 0) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = preorder[0];
    int i = 1;
    while (i < preorderSize && preorder[i] < root->data) {
        i++;
    }
    root->left = buildTree(preorder + 1, i - 1);
    root->right = buildTree(preorder + i, preorderSize - i);
    return root;
}

2. 对这棵二叉树进行递归遍历

二叉树的递归遍历有四种：先序遍历、中序遍历、后序遍历和层次遍历。代码如下：

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

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

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

void levelorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Queue* q = createQueue();
    enqueue(q, root);
    while (!isEmpty(q)) {
        TreeNode* node = dequeue(q);
        printf("%d ", node->data);
        if (node->left != NULL) {
            enqueue(q, node->left);
        }
        if (node->right != NULL) {
            enqueue(q, node->right);
        }
    }
}

3. 对这棵树用非递归方式进行遍历

非递归遍历需要借助栈的数据结构，对于先序、中序和后序遍历，分别有不同的实现方法。代码如下：

void preorderTraversal2(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* s = createStack();
    push(s, root);
    while (!isEmpty(s)) {
        TreeNode* node = pop(s);
        printf("%d ", node->data);
        if (node->right != NULL) {
            push(s, node->right);
        }
        if (node->left != NULL) {
            push(s, node->left);
        }
    }
}

void inorderTraversal2(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* s = createStack();
    TreeNode* node = root;
    while (node != NULL || !isEmpty(s)) {
        while (node != NULL) {
            push(s, node);
            node = node->left;
        }
        node = pop(s);
        printf("%d ", node->data);
        node = node->right;
    }
}

void postorderTraversal2(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* s1 = createStack();
    Stack* s2 = createStack();
    push(s1, root);
    while (!isEmpty(s1)) {
        TreeNode* node = pop(s1);
        push(s2, node);
        if (node->left != NULL) {
            push(s1, node->left);
        }
        if (node->right != NULL) {
            push(s1, node->right);
        }
    }
    while (!isEmpty(s2)) {
        TreeNode* node = pop(s2);
        printf("%d ", node->data);
    }
}

4. 求二叉树的深度、结点数目、叶结点数目

二叉树的深度可以递归地求解，结点数目和叶结点数目也可以通过递归遍历的方式求解。代码如下：

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

int countNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int countLeaves(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeaves(root->left) + countLeaves(root->right);
}

5. 将二叉树每个结点的左右子树交换位置

交换左右子树的方法也可以递归实现。代码如下：

void swap(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    swap(root->left);
    swap(root->right);
}

6. 设计二叉树的双序遍历算法

双序遍历是一种比较特殊的遍历方式，它可以由先序和中序遍历序列推导出来。具体实现方法可以参考以下代码：

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

7. 计算二叉树最大宽度

二叉树的最大宽度可以通过层次遍历的方式求解。代码如下：

int maxWidth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    Queue* q = createQueue();
    enqueue(q, root);
    int maxWidth = 0;
    while (!isEmpty(q)) {
        int size = getSize(q);
        maxWidth = size > maxWidth ? size : maxWidth;
        for (int i = 0; i < size; i++) {
            TreeNode* node = dequeue(q);
            if (node->left != NULL) {
                enqueue(q, node->left);
            }
            if (node->right != NULL) {
                enqueue(q, node->right);
            }
        }
    }
    return maxWidth;
}

8. 求二叉树中第一条最长的路径长度，并输出此路径上各结点

求解二叉树中第一条最长路径的方法是：递归遍历每个结点，计算左子树和右子树的深度之和，并记录下经过当前结点的路径长度。代码如下：

void findLongestPath(TreeNode* root, int* maxLen, Stack* pathStack) {
    if (root == NULL) {
        return;
    }
    Stack* leftStack = createStack();
    Stack* rightStack = createStack();
    findLongestPath(root->left, maxLen, leftStack);
    findLongestPath(root->right, maxLen, rightStack);
    int leftDepth = getDepth(leftStack);
    int rightDepth = getDepth(rightStack);
    int len = leftDepth + rightDepth;
    if (len > *maxLen) {
        *maxLen = len;
        while (!isEmpty(pathStack)) {
            pop(pathStack);
        }
        while (!isEmpty(leftStack)) {
            push(pathStack, pop(leftStack));
        }
        push(pathStack, root->data);
        while (!isEmpty(rightStack)) {
            push(pathStack, pop(rightStack));
        }
    }
    push(leftStack, root->data);
    push(rightStack, root->data);
}

void printStack(Stack* s) {
    while (!isEmpty(s)) {
        printf("%d ", pop(s));
    }
    printf("\n");
}

void longestPath(TreeNode* root) {
    int maxLen = 0;
    Stack* pathStack = createStack();
    findLongestPath(root, &maxLen, pathStack);
    printStack(pathStack);
}