1.编写二叉树的递归遍历算法,实现:给定一棵二叉树的“扩展先序遍历序列”,创建这棵叉树。 (1)输出二叉树的先序遍历的结点序列。 (2)输出二叉树的后序遍历的结点序列。 (3)输出二叉树的中序遍历的结点序列。 (4)输出二叉树的叶子结点。 (5)统计二叉树的结点个数。
时间: 2024-11-09 20:18:33 浏览: 12
数据结构实验报告6-树-二叉树的遍历算法-实验内容及要求.docx
要实现二叉树的递归遍历算法并根据给定的扩展先序遍历序列创建二叉树,我们可以使用递归的方式来构建树结构。这里我会分别给出构建树以及进行遍历的函数示例。首先,我们需要定义二叉树节点的数据结构:
```c
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左子节点
struct TreeNode* right; // 右子节点
} TreeNode;
```
接下来,我们可以通过扩展先序遍历序列来构造二叉树:
```c
TreeNode* createTree(int* preorder, int n) {
if (n <= 0) return NULL;
TreeNode* root = malloc(sizeof(TreeNode));
root->val = preorder[0];
int i = 1;
root->left = createTree(preorder + i, n / 2);
root->right = createTree(preorder + i + n / 2, n - n / 2 - 1);
return root;
}
```
现在,我们可以为题目要求的遍历操作编写函数:
1. 先序遍历(根-左-右):
```c
void preOrderTraversal(TreeNode* node) {
if (node != NULL) {
printf("%d ", node->val); // 输出节点值
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
}
```
2. 后序遍历(左-右-根):
```c
void postOrderTraversal(TreeNode* node) {
if (node != NULL) {
postOrderTraversal(node->left);
postOrderTraversal(node->right);
printf("%d ", node->val); // 输出节点值
}
}
```
3. 中序遍历(左-根-右):
```c
void inOrderTraversal(TreeNode* node) {
if (node != NULL) {
inOrderTraversal(node->left);
printf("%d ", node->val); // 输出节点值
inOrderTraversal(node->right);
}
}
```
4. 计算叶子节点(没有子节点的节点):
```c
int countLeaves(TreeNode* node, int count) {
if (node == NULL) return count;
if (node->left == NULL && node->right == NULL) count++;
count = countLeaves(node->left, count) + countLeaves(node->right, count);
return count;
}
```
5. 统计结点个数:
```c
int countNodes(TreeNode* node) {
return node ? 1 + countNodes(node->left) + countNodes(node->right) : 0;
阅读全文