以二叉链表作为二叉树的存储结构,编写算法实现交换二叉树每个结点的左孩子和右孩子。
时间: 2023-11-14 16:06:16 浏览: 53
以下是交换二叉树每个节点左右孩子的算法实现:
```
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void swap(BiTree root) {
if (root == NULL) {
return;
}
BiTNode *temp = root->lchild;
root->lchild = root->rchild;
root->rchild = temp;
swap(root->lchild);
swap(root->rchild);
}
```
首先判断当前节点是否为空,如果为空则返回。否则将当前节点的左孩子和右孩子进行交换,并对左右孩子分别递归调用 `swap` 函数。这样就可以实现交换二叉树中每个节点的左右孩子。
相关问题
以二叉链表作为二叉树的存储结构,编写交换二叉树每个结点的左孩子和右孩子的算法
假设二叉树的二叉链表存储结构如下所示:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
可以使用递归的方式来实现交换二叉树的每个结点的左孩子和右孩子。具体的实现过程如下:
```python
def swapTree(root: TreeNode) -> TreeNode:
if not root:
return None
# 交换左右孩子
root.left, root.right = root.right, root.left
# 递归处理左右子树
swapTree(root.left)
swapTree(root.right)
return root
```
在上面的代码中,我们首先交换当前结点的左右孩子,然后递归处理左右子树。最后返回根节点即可。
用c语言实现以二叉链表作为二叉树的存储结构,编写算法实现交换二叉树每个结点的左孩子和右孩子。
以下是用C语言实现的交换二叉树节点左右孩子的算法:
```c
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node* createNode(int data)
{
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void swap(struct node* node)
{
if(node == NULL)
{
return;
}
else
{
struct node* temp = node->left;
node->left = node->right;
node->right = temp;
swap(node->left);
swap(node->right);
}
}
void inorderTraversal(struct node* root)
{
if(root == NULL)
{
return;
}
inorderTraversal(root->left);
printf("%d -> ", root->data);
inorderTraversal(root->right);
}
int main()
{
struct node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Inorder traversal before swapping:\n");
inorderTraversal(root);
swap(root);
printf("\nInorder traversal after swapping:\n");
inorderTraversal(root);
return 0;
}
```
此算法首先创建了一个二叉树,然后通过递归的方式遍历二叉树,将每个节点的左右孩子进行交换。最后再次遍历二叉树,输出结果。