以二叉链表作为二叉树的存储结构，编写以下算法，交换二叉树每个结点的左孩子和右孩子

### 回答1： 以下是交换二叉树每个节点的左孩子和右孩子的C语言代码及注释： ```c #include <stdio.h> #include <stdlib.h> // 二叉树节点结构体 typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; // 创建二叉树（手动输入） TreeNode* createBinaryTree() { int val; printf("请输入节点的值（-1表示该节点为空）："); scanf("%d", &val); if (val == -1) { return NULL; } TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = val; root->left = createBinaryTree(); root->right = createBinaryTree(); return root; } // 交换二叉树每个节点的左孩子和右孩子 void swapLeftAndRight(TreeNode* root) { if (root == NULL) { return; } // 交换左孩子和右孩子 TreeNode* temp = root->left; root->left = root->right; root->right = temp; // 递归处理左子树 swapLeftAndRight(root->left); // 递归处理右子树 swapLeftAndRight(root->right); } // 中序遍历二叉树（用于验证交换结果） void inorderTraversal(TreeNode* root) { if (root == NULL) { return; } inorderTraversal(root->left); printf("%d ", root->val); inorderTraversal(root->right); } int main() { // 创建二叉树 TreeNode* root = createBinaryTree(); // 交换二叉树每个节点的左孩子和右孩子 swapLeftAndRight(root); // 中序遍历二叉树（用于验证交换结果） inorderTraversal(root); return 0; } ``` 注：以上代码中，使用了二叉树的中序遍历来验证交换结果是否正确。如果交换成功，中序遍历的结果应该是一个完全颠倒的二叉树。 ### 回答2： 以下是用C语言编写的完整代码和注释： ```c #include<stdio.h> #include<stdlib.h> // 二叉树的结点结构 typedef struct Node { char data; // 结点数据 struct Node* left; // 左孩子指针 struct Node* right; // 右孩子指针 }Node; // 创建一个新的二叉树结点 Node* createNode(char data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } // 交换二叉树每个结点的左孩子和右孩子 void swapChildren(Node* root) { if (root == NULL) { return; } // 递归交换左右子树 Node* temp = root->left; root->left = root->right; root->right = temp; // 分别交换左右子树 swapChildren(root->left); swapChildren(root->right); } int main() { // 创建示例二叉树 Node* root = createNode('A'); Node* nodeB = createNode('B'); Node* nodeC = createNode('C'); Node* nodeD = createNode('D'); Node* nodeE = createNode('E'); root->left = nodeB; root->right = nodeC; nodeB->left = nodeD; nodeB->right = nodeE; // 输出交换前的二叉树结构 printf("交换前的二叉树结构：\n"); printf(" A\n"); printf(" / \\\n"); printf(" B C\n"); printf(" / \\ / \\\n"); printf(" D E NULL NULL\n"); // 交换二叉树每个结点的左孩子和右孩子 swapChildren(root); // 输出交换后的二叉树结构 printf("交换后的二叉树结构：\n"); printf(" A\n"); printf(" / \\\n"); printf(" C B\n"); printf(" / \\\n"); printf("NULL NULL\n"); return 0; } ``` 以上代码使用二叉链表作为二叉树的存储结构，并实现了一个`swapChildren`函数，用于交换每个结点的左孩子和右孩子。在`main`函数中创建了一个示例二叉树，并分别输出交换前和交换后的二叉树结构。运行代码后，可以看到交换前的二叉树结构为： ``` A / \ B C / \ / \ D E NULL NULL ``` 交换后的二叉树结构为： ``` A / \ C B / \ NULL NULL ``` ### 回答3： 以下是用C语言编写的交换二叉树每个结点左孩子和右孩子的算法： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树结点结构 typedef struct TreeNode { char data; // 结点数据 struct TreeNode* left; // 左孩子指针 struct TreeNode* right; // 右孩子指针 } TreeNode; // 创建二叉树 TreeNode* createBinaryTree() { char data; scanf("%c", &data); // 从输入读取结点数据 // 如果输入的是空格字符，则返回NULL指针，表示空结点 if (data == ' ') { return NULL; } else { // 创建新的结点并初始化 TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->data = data; // 递归创建左孩子和右孩子 newNode->left = createBinaryTree(); newNode->right = createBinaryTree(); return newNode; } } // 交换二叉树每个结点的左孩子和右孩子 void swapChildren(TreeNode* root) { // 递归基本情况：如果当前结点为空，则返回 if (root == NULL) { return; } // 交换当前结点的左右孩子指针 TreeNode* temp = root->left; root->left = root->right; root->right = temp; // 递归交换左孩子和右孩子 swapChildren(root->left); swapChildren(root->right); } // 先序遍历二叉树（用于验证交换结果） void preorderTraversal(TreeNode* root) { if (root == NULL) { return; } printf("%c ", root->data); // 输出当前结点数据 preorderTraversal(root->left); // 递归遍历左子树 preorderTraversal(root->right); // 递归遍历右子树 } int main() { printf("请输入二叉树的先序遍历序列（空结点用空格表示）："); TreeNode* root = createBinaryTree(); // 创建二叉树 printf("交换前的二叉树先序遍历序列："); preorderTraversal(root); // 输出交换前的二叉树 swapChildren(root); // 交换二叉树每个结点的左孩子和右孩子 printf("\n交换后的二叉树先序遍历序列："); preorderTraversal(root); // 输出交换后的二叉树 return 0; } ``` 运行代码时，输入二叉树的先序遍历序列，如“ABD CE ”。其中，空结点用空格表示。代码会先创建二叉树，然后通过先序遍历输出交换前的二叉树，再交换二叉树的左右孩子指针，最后再通过先序遍历输出交换后的二叉树序列。

### 层次遍历的算法实现 层次遍历是一种按照树的每一层依次访问节点的方式。对于二叉链表存储结构，可以借助队列来完成这一操作。以下是基于二叉链表存储结构实现二叉树层次遍历的具体方法。 #### 实现代码 以下是一个完整的 C 风格代码示例： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树节点结构体 typedef struct BiTNode { char data; struct BiTNode* lchild, *rchild; } BiTNode, *BiTree; // 创建二叉树（先序方式） void CreateBiTree(BiTree* T) { char ch; scanf(" %c", &ch); if (ch == '#') *T = NULL; // 如果读取到'#'，则该位置为空 else { *T = (BiTree)malloc(sizeof(struct BiTNode)); (*T)->data = ch; CreateBiTree(&((*T)->lchild)); // 构建左子树 CreateBiTree(&((*T)->rchild)); // 构建右子树 } } // 层次遍历函数 void LevelOrderTraversal(BiTree T) { if (!T) return; // 若树为空，则直接返回 // 使用数组模拟队列 const int MAX_QUEUE_SIZE = 100; BiTree queue[MAX_QUEUE_SIZE]; int front = 0, rear = 0; // 将根节点入队 queue[rear++] = T; while (front != rear) { // 当队列不为空时继续循环 BiTree p = queue[front++]; printf("%c ", p->data); // 访问当前节点的数据 // 左子树存在时将其加入队列 if (p->lchild) queue[rear++] = p->lchild; // 右子树存在时将其加入队列 if (p->rchild) queue[rear++] = p->rchild; } printf("\n"); } ``` 以上代码通过队列实现了二叉树的层次遍历功能[^1]。具体逻辑如下： - 初始化一个队列用于暂存待处理的节点。 - 将根节点压入队列作为起始点。 - 循环执行直到队列为空为止：每次取出队首元素并打印其值；如果它有左右子节点，则分别将它们加入队列。 #### 关键点说明 - **队列的作用**：由于层次遍历需要逐层访问所有节点，因此采用先进先出(FIFO)特性的队列非常适合此场景。 - **时间复杂度分析**：假设 n 表示二叉树中总的节点数目，则整个过程只需扫描一遍整棵树即可完成全部工作量，故总的时间复杂度为 O(n)。 --- ###