编程题：实现对一颗二叉树的所有左右子节点位置交换

编程题：实现对一颗二叉树的所有左右子节点位置交换

引用

CSDN

1.

https://blog.csdn.net/zhu134/article/details/138508403

改变前的二叉树：

改变后的二叉树：

实际上就是镜像反转

代码实现

#include<iostream>
#include<stack>
using namespace std;

// 定义二叉树节点结构体
typedef struct BTNode{
    char show;              // 节点的数据
    struct BTNode* left;    // 左孩子节点指针
    struct BTNode* right;   // 右孩子节点指针
} BTNode;

// 定义二叉树结构体
typedef struct{
    BTNode* root;   // 根节点指针
    int count;      // 节点个数
} BinaryTree;

// 非递归中序遍历二叉树，用于检查交换结果
void inorderTraversal(BTNode* root) {
    stack<BTNode*> s;
    BTNode* current = root;
    while (current || !s.empty()) {
        while (current) {
            s.push(current);
            current = current->left;
        }
        current = s.top();
        s.pop();
        cout << current->show << " ";
        current = current->right;
    }
}

// 交换二叉树所有节点的左右子节点的位置
void swapChildren(BinaryTree* tree) {
    stack<BTNode*> s;
    s.push(tree->root);
    while (!s.empty()) {
        BTNode* current = s.top();
        s.pop();
        // 交换左右子节点
        BTNode* temp = current->left;
        current->left = current->right;
        current->right = temp;
        // 将左右子节点入栈
        if (current->left) s.push(current->left);
        if (current->right) s.push(current->right);
    }
}

// 创建节点
BTNode* createBTNode(char show){
    BTNode* node = new BTNode;
    node->show = show;
    node->left = nullptr;
    node->right = nullptr;
    return node;
}

// 初始化树根节点
void initBTreeRoot(BinaryTree* tree, BTNode* node){
    tree->count = 1;
    tree->root = node;
}

// 创建树
BinaryTree* createBTree(BTNode* root){
    BinaryTree* tree = new BinaryTree;
    if(root){ // 非空树
        initBTreeRoot(tree, root);
    } else{   // 空树
        tree->root = NULL;
        tree->count = 0;
    }
    return tree;
}

// 插入节点
// 在树中插入newNode节点，该节点的双亲节点为parent
// flag==1则该节点为左孩子，flag==0则该节点为右孩子 
void insertBTNode(BinaryTree* tree, BTNode* parent, BTNode* newNode, int flag){
    if(flag == 1){
        parent->left = newNode;
    } else{
        parent->right = newNode;
    }
    tree->count++;
}

// 初始化一棵具体的树
// 创建并初始化一棵具体的二叉树，返回根节点指针
BinaryTree* initBTree(){
    // 初始化节点
    BTNode* a = createBTNode('A');
    BTNode* b = createBTNode('B');
    BTNode* c = createBTNode('C');
    BTNode* d = createBTNode('D');
    BTNode* e = createBTNode('E');
    BTNode* f = createBTNode('F');
    BTNode* g = createBTNode('G');
    BTNode* h = createBTNode('H');
    BTNode* i = createBTNode('I');
    
    // 初始化树根
    BinaryTree* tree = createBTree(a);
    
    // 插入
    insertBTNode(tree, a, b, 1);
    insertBTNode(tree, a, e, 0);
    insertBTNode(tree, b, c, 0);
    insertBTNode(tree, c, d, 1);
    insertBTNode(tree, e, f, 0);
    insertBTNode(tree, f, g, 1);
    insertBTNode(tree, g, h, 1);
    insertBTNode(tree, g, i, 0);
    
    return tree;    // 返回树根节点
} 

int main(){
    // 初始化一棵具体的二叉树
    BinaryTree* tree = initBTree();
    // 输出交换前的二叉树中序遍历结果
    cout << "交换前的二叉树中序遍历结果：" << endl;
    inorderTraversal(tree->root);
    cout << endl;
    // 交换二叉树所有节点的左右子节点的位置
    swapChildren(tree);
    // 输出交换后的二叉树中序遍历结果
    cout << "交换后的二叉树中序遍历结果：" << endl;
    inorderTraversal(tree->root);
    cout << endl;
    // 释放内存
    delete tree;
    return 0;
}

输出结果：