二叉树的创建(用先序递归算法创建) 2、二叉树的先序递归遍历 3、二叉树的中序递归遍历 4、二叉树的后序递归遍历 5、二叉树的中序非递归遍历(调用栈实现 6、求二叉树的节点总数 7、求二叉树的叶子节点总数 8、求二叉树的深度 输入结点信息,能完成所有功能,有适当的注释使用C语言
时间: 2024-10-21 12:07:10 浏览: 36
二叉树的遍历中序非递归,先序后序递归
首先,我们来理解如何用C语言通过先序递归算法创建二叉树:
```c
// 定义二叉树结点结构
typedef struct TreeNode {
int val;
struct TreeNode *left; // 左孩子指针
struct TreeNode *right; // 右孩子指针
} TreeNode;
// 创建二叉树函数 (先序遍历)
TreeNode* createTree(int value[], int start, int end) {
if (start > end) return NULL; // 如果索引超出范围,返回空节点
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); // 分配内存
root->val = value[start]; // 设置当前值
root->left = createTree(value, start + 1, end); // 递归左子树
root->right = createTree(value, start + 2, end); // 递归右子树
return root;
}
```
接下来,是四种基本的二叉树递归遍历:
1. **先序遍历**: 访问根 -> 左 -> 右
```c
void preOrderTraversal(TreeNode* node) {
if (node != NULL) {
printf("%d ", node->val); // 访问节点
preOrderTraversal(node->left); // 左子树
preOrderTraversal(node->right); // 右子树
}
}
```
2. **中序遍历**: 左 -> 访问根 -> 右
```c
void inOrderTraversal(TreeNode* node) {
if (node != NULL) {
inOrderTraversal(node->left);
printf("%d ", node->val);
inOrderTraversal(node->right);
}
}
```
3. **后序遍历**: 左 -> 右 -> 访问根
```c
void postOrderTraversal(TreeNode* node) {
if (node != NULL) {
postOrderTraversal(node->left);
postOrderTraversal(node->right);
printf("%d ", node->val);
}
}
```
4. **中序非递归遍历**(利用栈实现):
```c
void iterativeInOrderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* curr = root;
while (curr || !s.empty()) {
while (curr) {
s.push(curr);
curr = curr->left;
}
curr = s.top(); // 弹出栈顶元素
s.pop();
printf("%d ", curr->val);
curr = curr->right;
}
}
```
对于计算节点总数、叶子节点总数和深度,我们可以分别添加以下函数:
- 节点总数(包括根节点)
- ```c
int countNodes(TreeNode* node) {
if (node == NULL) return 0;
return 1 + countNodes(node->left) + countNodes(node->right);
}
```
- 叶子节点总数
- ```c
int countLeaves(TreeNode* node) {
if (node == NULL) return 0;
if (node->left == NULL && node->right == NULL) return 1; // 判断是否为叶子节点
return countLeaves(node->left) + countLeaves(node->right);
}
```
- 深度(假设根节点深度为0)
- ```c
int depth(TreeNode* node) {
if (node == NULL) return 0;
return 1 + MAX(depth(node->left), depth(node->right));
}
```
请注意,`MAX`是一个宏或者函数,用于获取两个整数的最大值。以上代码仅作为示例,并未包含错误处理和边界检查,实际编写时需要完善。
阅读全文