已知二叉树采用二叉链表存储结构，使用c语言设计一个算法，使二叉树中所有结点的左、右子树相互交换。

### 交换二叉树左右子树的算法实现 在C语言中，可以通过递归或非递归的方式实现二叉树左右子树的交换。以下是两种方法的具体实现： --- #### 方法一：递归实现 递归是一种直观且易于理解的方法，通过自顶向下的方式逐层交换每个节点的左、右子树。 ```c // 定义二叉树节点结构体 typedef struct BiNode { char data; struct BiNode *lchild, *rchild; } BiNode, *BiTree; // 递归交换左右子树 void SwapSubtreesRecursively(BiTree T) { if (T == NULL) return; // 如果当前节点为空，则直接返回 // 临时保存左子树 BiTree temp = T->lchild; // 交换左右子树 T->lchild = T->rchild; T->rchild = temp; // 继续递归处理新的左右子树 SwapSubtreesRecursively(T->lchild); SwapSubtreesRecursively(T->rchild); } ``` 上述代码实现了递归交换功能，其中核心部分是对当前节点的两个子树进行交换，并继续递归地对其子树执行相同的操作[^2]。 --- #### 方法二：非递归实现 为了克服递归可能带来的栈溢出问题，可以采用基于栈的数据结构来模拟递归的过程。这种方式适用于较深的二叉树场景。 ```c #include <stdio.h> #include <stdlib.h> // 栈定义 #define MAX_SIZE 100 typedef struct Stack { BiTree items[MAX_SIZE]; int top; } Stack; // 初始化栈 void InitStack(Stack *stack) { stack->top = -1; } // 判断栈是否为空 int IsEmpty(Stack *stack) { return stack->top == -1; } // 入栈操作 void Push(Stack *stack, BiTree item) { if (stack->top >= MAX_SIZE - 1) { printf("Stack Overflow\n"); exit(1); } stack->items[++stack->top] = item; } // 出栈操作 BiTree Pop(Stack *stack) { if (IsEmpty(stack)) { printf("Stack Underflow\n"); exit(1); } return stack->items[stack->top--]; } // 非递归交换左右子树 void SwapSubtreesIteratively(BiTree T) { if (T == NULL) return; // 若根节点为空，则无需操作 Stack s; InitStack(&s); // 初始化栈 Push(&s, T); // 将根节点压入栈中 while (!IsEmpty(&s)) { // 当栈不为空时循环 BiTree current = Pop(&s); // 取出栈顶元素 // 交换当前节点的左右子树 BiTree temp = current->lchild; current->lchild = current->rchild; current->rchild = temp; // 如果存在左子树，则将其压入栈中 if (current->lchild != NULL) { Push(&s, current->lchild); } // 如果存在右子树，则将其压入栈中 if (current->rchild != NULL) { Push(&s, current->rchild); } } } ``` 这段代码利用了一个显式的栈来代替函数调用栈的作用，从而避免了因递归层数过多而引起的栈溢出问题[^3]。 --- #### 中序遍历验证结果 无论使用递归还是非递归方法，都可以通过中序遍历来验证最终的结果是否正确。 ```c // 中序遍历打印二叉树 void InOrderTraversal(BiTree T) { if (T == NULL) return; InOrderTraversal(T->lchild); printf("%c ", T->data); InOrderTraversal(T->rchild); } ``` 调用该函数即可按顺序输出二叉树中的所有节点值，便于对比原树与交换后的差异。 --- ### 总结 - **递归方法**简单易懂，适合浅层二叉树。 - **非递归方法**虽然稍微复杂一些，但在面对深层嵌套的情况下表现更为稳健可靠[^4]。 无论是哪一种方法都需注意边界情况（如空树），以确保程序运行的安全性和鲁棒性。 ---