2、设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
要在链式存储结构上交换二叉树中所有节点的左右子树,你可以采用递归的方式。对于每个节点,交换其左右子树,并递归地对左子树和右子树执行相同的操作。
#include <iostream>struct TreeNode {int data;TreeNode* left;TreeNode* right;//构造,可根据需要删除TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};//核心交换代码
void swapLeftAndRight(TreeNode* root) {if (root == nullptr) {return;}// 递归交换左右子树swapLeftAndRight(root->left);swapLeftAndRight(root->right);// 交换左右子树的指针TreeNode* temp = root->left;root->left = root->right;root->right = temp;
}// 验证交换结果:中序遍历
void inorderTraversal(TreeNode* root) {if (root != nullptr) {inorderTraversal(root->left);std::cout << root->data << " ";inorderTraversal(root->right);}
}int main() {// 构建一个简单的二叉树作为例子TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5); inorderTraversal(root); printf("\n");// 交换左右子树swapLeftAndRight(root);inorderTraversal(root); return 0;
}
这段代码中,swapLeftAndRight 函数通过递归地交换每个节点的左右子树,并且在 main 函数中构建了一个简单的二叉树,然后进行了交换并输出了交换后的中序遍历结果。