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

好的，这是一个很全面的二叉树操作实验，我可以帮你解答相关问题。

首先，你需要明确二叉树的定义：二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，分别为左子节点和右子节点。而二叉链表则是指用链表的方式来实现二叉树，每个节点包含三个信息：该节点的数据、它的左子节点的指针、它的右子节点的指针。

接下来，我将分别回答每个实验要求：

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

按照先序序列构造一棵二叉链表表示的二叉树的算法如下：

void createTree(node *&root) {
    char ch;
    cin >> ch;
    if (ch == '#') { // 如果输入为#，表示该节点为空节点 
        root = NULL;
    } else {
        root = new node; // 创建新的节点 
        root->data = ch;
        createTree(root->left); // 构造左子树 
        createTree(root->right); // 构造右子树 
    }
}

其中，node是二叉链表中节点的结构体，包含数据data和指向左右子节点的指针left和right。输入的先序序列中，#表示空节点，其他字符表示节点的数据。

2. 对这棵二叉树进行递归遍历：先序、中序、后序以及层次遍历遍历序列，分别输出结点的遍历序列。

二叉树的递归遍历算法如下：

void preorder(node *root) { // 先序遍历 
    if (root != NULL) {
        cout << root->data << " ";
        preorder(root->left);
        preorder(root->right);
    }
}

void inorder(node *root) { // 中序遍历 
    if (root != NULL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

void postorder(node *root) { // 后序遍历 
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        cout << root->data << " ";
    }
}

int getDepth(node *root) { // 求二叉树的深度 
    if (root == NULL) {
        return 0;
    }
    int left_depth = getDepth(root->left);
    int right_depth = getDepth(root->right);
    return max(left_depth, right_depth) + 1;
}

int getNodeCount(node *root) { // 求二叉树的节点数目 
    if (root == NULL) {
        return 0;
    }
    int left_count = getNodeCount(root->left);
    int right_count = getNodeCount(root->right);
    return left_count + right_count + 1;
}

int getLeafCount(node *root) { // 求二叉树的叶节点数目 
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    int left_count = getLeafCount(root->left);
    int right_count = getLeafCount(root->right);
    return left_count + right_count;
}

void swapChild(node *root) { // 将二叉树每个节点的左右子树交换位置 
    if (root != NULL) {
        swap(root->left, root->right);
        swapChild(root->left);
        swapChild(root->right);
    } 
}

void doubleOrder(node *root) { // 设计二叉树的双序遍历算法 
    if (root != NULL) {
        cout << root->data << " ";
        doubleOrder(root->left);
        cout << root->data << " ";
        doubleOrder(root->right);
    }
}

int getMaxWidth(node *root) { // 计算二叉树最大宽度 
    if (root == NULL) {
        return 0;
    }
    queue<node*> q;
    q.push(root);
    int max_width = 1;
    while (!q.empty()) {
        int current_level_size = q.size();
        max_width = max(max_width, current_level_size);
        for (int i = 0; i < current_level_size; i++) {
            node *p = q.front();
            q.pop();
            if (p->left != NULL) {
                q.push(p->left);
            }
            if (p->right != NULL) {
                q.push(p->right);
            }
        }
    }
    return max_width;
}

int getLongestPath(node *root, vector<node*> &path) { // 求二叉树中第一条最长的路径长度，并输出此路径上各结点 
    if (root == NULL) {
        return 0;
    }
    vector<node*> left_path;
    int left_len = getLongestPath(root->left, left_path);
    vector<node*> right_path;
    int right_len = getLongestPath(root->right, right_path);
    if (left_len > right_len) {
        path = left_path;
    } else {
        path = right_path;
    }
    path.insert(path.begin(), root);
    return max(left_len, right_len) + 1;
}

其中，层次遍历需要用到队列来实现，代码如下：

void levelOrder(node *root) { // 层次遍历 
    queue<node*> q;
    if (root != NULL) {
        q.push(root);
    }
    while (!q.empty()) {
        node *p = q.front();
        q.pop();
        cout << p->data << " ";
        if (p->left != NULL) {
            q.push(p->left);
        }
        if (p->right != NULL) {
            q.push(p->right);
        }
    }
}

3. 对这棵树用非递归方式进行遍历：先序、中序以及后序遍历序列，分别输出结点的遍历序列。

二叉树的非递归遍历算法需要用到栈来辅助实现，具体实现如下：

void preorderNonRecursive(node *root) { // 非递归先序遍历 
    stack<node*> s;
    node *p = root;
    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            cout << p->data << " ";
            s.push(p);
            p = p->left;
        }
        if (!s.empty()) {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

void inorderNonRecursive(node *root) { // 非递归中序遍历 
    stack<node*> s;
    node *p = root;
    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            s.push(p);
            p = p->left;
        }
        if (!s.empty()) {
            p = s.top();
            s.pop();
            cout << p->data << " ";
            p = p->right;
        }
    }
}

void postorderNonRecursive(node *root) { // 非递归后序遍历 
    stack<node*> s;
    node *p = root;
    node *last_visited = NULL; // 记录上一个访问的节点 
    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            s.push(p);
            p = p->left;
        }
        p = s.top();
        if (p->right == NULL || p->right == last_visited) {
            cout << p->data << " ";
            s.pop();
            last_visited = p;
            p = NULL;
        } else {
            p = p->right;
        }
    }
}

4. 求二叉树的深度/节点数目/叶节点数目。

求二叉树深度、节点数目和叶节点数目的算法已经在上面给出了，这里不再赘述。

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

将二叉树每个节点的左右子树交换位置的算法已经在上面给出了，这里不再赘述。

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

二叉树的双序遍历算法已经在上面给出了，这里不再赘述。

7. 计算二叉树最大宽度。

计算二叉树最大宽度的算法已经在上面给出了，这里不再赘述。

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

求二叉树中第一条最长的路径长度，并输出此路径上各结点的算法已经在上面给出了，这里不再赘述。