用C实现以二叉链表存储结构的方式创建如下图的二叉树,输入时将下图二叉树变为基于括号表示的字符串。创建二叉树和实现二叉树的三种遍历和层次遍历。最后求出叶子节点个数和二叉树深度
时间: 2024-01-23 09:48:19 浏览: 28
首先,我们需要定义二叉树的结构体:
```c
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
然后,我们可以按照下面的方式创建二叉树:
```c
TreeNode* createTree() {
TreeNode *root = (TreeNode*) malloc(sizeof(TreeNode));
root->data = 'A';
root->left = (TreeNode*) malloc(sizeof(TreeNode));
root->left->data = 'B';
root->left->left = (TreeNode*) malloc(sizeof(TreeNode));
root->left->left->data = 'D';
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (TreeNode*) malloc(sizeof(TreeNode));
root->left->right->data = 'E';
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (TreeNode*) malloc(sizeof(TreeNode));
root->right->data = 'C';
root->right->left = (TreeNode*) malloc(sizeof(TreeNode));
root->right->left->data = 'F';
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode*) malloc(sizeof(TreeNode));
root->right->right->data = 'G';
root->right->right->left = NULL;
root->right->right->right = NULL;
return root;
}
```
这样,我们就创建了一个如下图所示的二叉树:
```
A
/ \
B C
/ \ / \
D E F G
```
接下来,我们可以实现遍历算法。下面是先序遍历的代码:
```c
void preorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%c ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
```
中序遍历和后序遍历的代码类似,这里不再给出。
最后,我们可以实现层次遍历算法:
```c
void levelOrderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
Queue *queue = createQueue();
enqueue(queue, root);
while (!isEmpty(queue)) {
TreeNode *node = dequeue(queue);
printf("%c ", node->data);
if (node->left != NULL) {
enqueue(queue, node->left);
}
if (node->right != NULL) {
enqueue(queue, node->right);
}
}
}
```
其中,我们需要使用队列来实现层次遍历。
最后,我们可以实现求叶子节点个数和二叉树深度的算法:
```c
int countLeaves(TreeNode *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
int maxDepth(TreeNode *root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}
```
这样,我们就完成了对于二叉树的创建、遍历、层次遍历、求叶子节点个数和二叉树深度的实现。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)