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

好的，这是一个比较全面的二叉树实验，需要实现多种操作。下面我将分步介绍如何实现这些操作。

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

先序遍历的顺序是：根节点，左子树，右子树。我们可以利用这个顺序来构造二叉树。具体实现如下：

typedef struct TreeNode {
    char data;                  // 结点数据
    struct TreeNode *lchild;    // 左子树
    struct TreeNode *rchild;    // 右子树
} TreeNode, *Tree;

Tree createTree() {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {    // 以 '#' 表示空结点
        return NULL;
    }
    Tree node = (Tree)malloc(sizeof(TreeNode));
    node->data = ch;
    node->lchild = createTree();
    node->rchild = createTree();
    return node;
}

在调用 createTree 函数时，输入一个字符串，其中 '#' 表示空结点。例如输入：`AB#CD##E##`，则构造出的二叉树如下：

    A
   / \
  B   C
     / \
    D   E

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

递归遍历二叉树的方法有很多种，这里我们实现先序、中序、后序和层次遍历。

// 先序遍历
void preOrder(Tree T) {
    if (T == NULL) {
        return;
    }
    printf("%c ", T->data);
    preOrder(T->lchild);
    preOrder(T->rchild);
}

// 中序遍历
void inOrder(Tree T) {
    if (T == NULL) {
        return;
    }
    inOrder(T->lchild);
    printf("%c ", T->data);
    inOrder(T->rchild);
}

// 后序遍历
void postOrder(Tree T) {
    if (T == NULL) {
        return;
    }
    postOrder(T->lchild);
    postOrder(T->rchild);
    printf("%c ", T->data);
}

// 层次遍历
void levelOrder(Tree T) {
    if (T == NULL) {
        return;
    }
    Queue q;
    initQueue(&q);
    enQueue(&q, T);
    while (!isQueueEmpty(q)) {
        Tree node = deQueue(&q);
        printf("%c ", node->data);
        if (node->lchild != NULL) {
            enQueue(&q, node->lchild);
        }
        if (node->rchild != NULL) {
            enQueue(&q, node->rchild);
        }
    }
}

其中，Queue 是一个队列结构体，可以用数组实现。initQueue 函数用来初始化队列，enQueue 函数用来入队，deQueue 函数用来出队，isQueueEmpty 函数用来判断队列是否为空。

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

除了递归遍历，我们还可以用非递归的方式来遍历二叉树。这里我们实现先序、中序和后序遍历。

// 非递归先序遍历
void preOrderNonRecursive(Tree T) {
    Stack s;
    initStack(&s);
    push(&s, T);
    while (!isStackEmpty(s)) {
        Tree node = pop(&s);
        printf("%c ", node->data);
        if (node->rchild != NULL) {
            push(&s, node->rchild);
        }
        if (node->lchild != NULL) {
            push(&s, node->lchild);
        }
    }
}

// 非递归中序遍历
void inOrderNonRecursive(Tree T) {
    Stack s;
    initStack(&s);
    Tree p = T;
    while (p != NULL || !isStackEmpty(s)) {
        while (p != NULL) {
            push(&s, p);
            p = p->lchild;
        }
        if (!isStackEmpty(s)) {
            p = pop(&s);
            printf("%c ", p->data);
            p = p->rchild;
        }
    }
}

// 非递归后序遍历
void postOrderNonRecursive(Tree T) {
    Stack s;
    initStack(&s);
    Tree p = T, lastVisit = NULL;
    while (p != NULL || !isStackEmpty(s)) {
        while (p != NULL) {
            push(&s, p);
            p = p->lchild;
        }
        p = getTop(s);
        if (p->rchild == NULL || p->rchild == lastVisit) {
            printf("%c ", p->data);
            pop(&s);
            lastVisit = p;
            p = NULL;
        } else {
            p = p->rchild;
        }
    }
}

其中，Stack 是一个栈结构体，可以用数组实现。initStack 函数用来初始化栈，push 函数用来入栈，pop 函数用来出栈，getTop 函数用来获取栈顶元素，isStackEmpty 函数用来判断栈是否为空。

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

求二叉树的深度、结点数目和叶结点数目都可以用递归的方式实现。具体实现如下：

// 求二叉树深度
int getTreeDepth(Tree T) {
    if (T == NULL) {
        return 0;
    }
    int leftDepth = getTreeDepth(T->lchild);
    int rightDepth = getTreeDepth(T->rchild);
    return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}

// 求二叉树结点数目
int getNodeCount(Tree T) {
    if (T == NULL) {
        return 0;
    }
    return getNodeCount(T->lchild) + getNodeCount(T->rchild) + 1;
}

// 求二叉树叶结点数目
int getLeafCount(Tree T) {
    if (T == NULL) {
        return 0;
    }
    if (T->lchild == NULL && T->rchild == NULL) {
        return 1;
    }
    return getLeafCount(T->lchild) + getLeafCount(T->rchild);
}

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

交换二叉树每个结点的左右子树只需要递归交换左右子树即可。具体实现如下：

void swapTree(Tree T) {
    if (T == NULL) {
        return;
    }
    Tree tmp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = tmp;
    swapTree(T->lchild);
    swapTree(T->rchild);
}

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

二叉树的双序遍历可以通过先序遍历和后序遍历来实现。具体实现如下：

void doubleOrder(Tree T) {
    if (T == NULL) {
        return;
    }
    printf("%c ", T->data);
    doubleOrder(T->lchild);
    printf("%c ", T->data);
    doubleOrder(T->rchild);
}

7. 计算二叉树最大宽度

计算二叉树最大宽度可以用层次遍历的方式实现。具体实现如下：

int getMaxWidth(Tree T) {
    if (T == NULL) {
        return 0;
    }
    Queue q;
    initQueue(&q);
    enQueue(&q, T);
    int maxWidth = 0;
    while (!isQueueEmpty(q)) {
        int size = q.size;
        maxWidth = (size > maxWidth) ? size : maxWidth;
        while (size--) {
            Tree node = deQueue(&q);
            if (node->lchild != NULL) {
                enQueue(&q, node->lchild);
            }
            if (node->rchild != NULL) {
                enQueue(&q, node->rchild);
            }
        }
    }
    return maxWidth;
}

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

求二叉树中第一条最长的路径长度可以用递归的方式实现。具体实现如下：

int getLongestPath(Tree T, Tree *path) {
    if (T == NULL) {
        return 0;
    }
    Tree leftPath[MAX_TREE_DEPTH], rightPath[MAX_TREE_DEPTH];
    int leftPathLen = getLongestPath(T->lchild, leftPath);
    int rightPathLen = getLongestPath(T->rchild, rightPath);
    if (leftPathLen >= rightPathLen) {
        leftPath[leftPathLen++] = T;
        *path = leftPath[leftPathLen-1];
        memcpy(path+1, leftPath, sizeof(Tree)*leftPathLen);
        return leftPathLen;
    } else {
        rightPath[rightPathLen++] = T;
        *path = rightPath[rightPathLen-1];
        memcpy(path+1, rightPath, sizeof(Tree)*rightPathLen);
        return rightPathLen;
    }
}

其中，path 是一个指向结点的指针数组，用来存储最长路径上的结点。

完整代码：