用C语言实现二叉树求结点个数,求树的高度,求叶子结点数、交换二叉树左右子树的算法。
时间: 2024-05-08 17:20:01 浏览: 76
编写一个将二叉树中每个结点的左右孩子交换的算法。
好的,我会为您回答这些问题。首先,以下是用C语言实现二叉树求结点个数的代码:
```
#include <stdio.h>
#include <stdlib.h>
struct Node{
int data;
struct Node* left;
struct Node* right;
};
int countNodes(struct Node* root){
if(root == NULL)
return 0;
else
return 1 + countNodes(root->left) + countNodes(root->right);
}
```
使用该函数时,只需传入二叉树的根节点并返回结点数。例如,以下是一个示例二叉树结构,它包括节点1、2、3、4、5、6、7、8、9:
```
1
/ \
2 3
/ \ / \
4 5 6 7
/
8
/
9
```
通过调用countNodes函数,您将得到该树的节点数(即9)。
接下来,下面是用C语言实现二叉树求高度的代码:
```
#include <stdio.h>
#include <stdlib.h>
struct Node{
int data;
struct Node* left;
struct Node* right;
};
int height(struct Node* root){
if(root == NULL)
return 0;
else{
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if(leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}
}
```
同样,将二叉树的根节点传递给height函数,它将返回该树的高度。例如,对于上面那个示例二叉树,高度是3。
接下来,以下是用C语言实现二叉树求叶子结点数的代码:
```
#include <stdio.h>
#include <stdlib.h>
struct Node{
int data;
struct Node* left;
struct Node* right;
};
int leafNodes(struct Node* node){
if(node == NULL)
return 0;
if(node->left == NULL && node->right == NULL)
return 1;
else
return leafNodes(node->left) + leafNodes(node->right);
}
```
同样,将二叉树的根节点传递给leafNodes函数,它将返回该树的叶子节点数。对于上述示例二叉树,结果为5。
最后是交换二叉树左右子树的算法:
```
#include <stdio.h>
#include <stdlib.h>
struct Node{
int data;
struct Node* left;
struct Node* right;
};
void swap(struct Node* node){
if(node == NULL)
return;
else{
struct Node* temp;
swap(node->left);
swap(node->right);
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
```
该函数将遍历整个二叉树,交换每个节点的左子树和右子树。当它完成后,整棵树的左右子树将被交换。
阅读全文