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

可以使用递归的方式交换每个节点的左右孩子。具体算法如下：

// 二叉树节点的定义
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 交换二叉树每个节点的左右孩子
void swap(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    // 交换当前节点的左右孩子
    TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    // 递归交换左右子树
    swap(root->left);
    swap(root->right);
}

这样，对于任意一个二叉树，调用 `swap(root)` 即可完成左右孩子的交换。

相关问题

C++以二叉链表作为二叉树的存储结构，编写以下算法： 1.统计二叉树的叶结点个数。 2.判别两棵树是否相等。 3.交换二叉树每个结点的左孩子和右孩子。 4.设计二叉树的双序遍历算法。

1. 统计二叉树的叶结点个数

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int countLeafNodes(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

2. 判别两棵树是否相等

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == nullptr && q == nullptr) {
        return true;
    }
    if (p == nullptr || q == nullptr) {
        return false;
    }
    if (p->val != q->val) {
        return false;
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

3. 交换二叉树每个结点的左孩子和右孩子

void swapLeftRight(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    swap(root->left, root->right);
    swapLeftRight(root->left);
    swapLeftRight(root->right);
}

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

void doubleOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";  // 访问根节点
    doubleOrderTraversal(root->left);   // 访问左子树
    cout << root->val << " ";  // 访问根节点
    doubleOrderTraversal(root->right);  // 访问右子树
}

以二叉链表作为二叉树的存储结构，编写以下算法： 1.统计二叉树的叶结点个数。 2.判别两棵树是否相等。 3.交换二叉树每个结点的左孩子和右孩子。 4.设计二叉树的双序遍历算法

下面是四个算法的具体实现：

1. 统计二叉树的叶结点个数

int countLeaf(BiTree T) {
    if (T == nullptr) {
        return 0;
    } else if (T->lchild == nullptr && T->rchild == nullptr) {
        return 1;
    } else {
        return countLeaf(T->lchild) + countLeaf(T->rchild);
    }
}

2. 判别两棵树是否相等

bool isEqual(BiTree T1, BiTree T2) {
    if (T1 == nullptr && T2 == nullptr) {
        return true;
    } else if (T1 == nullptr || T2 == nullptr) {
        return false;
    } else if (T1->data != T2->data) {
        return false;
    } else {
        return isEqual(T1->lchild, T2->lchild) && isEqual(T1->rchild, T2->rchild);
    }
}

3. 交换二叉树每个结点的左孩子和右孩子

void swapChildren(BiTree T) {
    if (T == nullptr) {
        return;
    }
    BiTree temp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = temp;
    swapChildren(T->lchild);
    swapChildren(T->rchild);
}

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

void doubleOrder(BiTree T) {
    if (T != nullptr) {
        visit(T);
        doubleOrder(T->lchild);
        visit(T);
        doubleOrder(T->rchild);
    }
}

其中，visit(T)是访问结点T的操作，双序遍历的顺序是：先前序遍历（访问结点后），再中序遍历（访问结点前），最后后序遍历（访问结点后）。