用c语言尽量详细地用括号表示法以非递归的方式输出二叉树的代码
时间: 2023-06-07 09:07:17 浏览: 98
二叉树的非递归实现(C版本)
好的,下面是用C语言以非递归的方式输出二叉树的代码,使用了括号表示法:
```c
#include <stdio.h>
#include <stdlib.h>
#include "stack.h" // 自定义栈的头文件
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 非递归后序遍历二叉树
void postorder(struct TreeNode* root) {
if (root == NULL) return;
struct TreeNode* prev = NULL;
struct Stack* stack = createStack(); // 创建一个栈
push(stack, root); // 把根节点压栈
while (!isEmpty(stack)) {
struct TreeNode* curr = peek(stack); // 获取栈顶元素
// 如果当前节点没有子节点或者已经访问过
if ((curr->left == NULL && curr->right == NULL) ||
(prev != NULL && (prev == curr->left || prev == curr->right))) {
printf("%d", curr->val);
pop(stack); // 弹出栈顶元素
prev = curr; // 更新prev节点为当前节点
} else {
// 右子节点入栈,保证先搜索左子树
if (curr->right != NULL) push(stack, curr->right);
// 左子节点入栈
if (curr->left != NULL) push(stack, curr->left);
}
}
destroyStack(stack); // 销毁栈
}
int main() {
// 创建以下二叉树
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* l1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* r1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* l2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* r2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* l3 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* r3 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
root->left = l1;
root->right = r1;
l1->val = 2;
l1->left = l2;
l1->right = r2;
r1->val = 3;
r1->left = l3;
r1->right = r3;
l2->val = 4;
l2->left = NULL;
l2->right = NULL;
r2->val = 5;
r2->left = NULL;
r2->right = NULL;
l3->val = 6;
l3->left = NULL;
l3->right = NULL;
r3->val = 7;
r3->left = NULL;
r3->right = NULL;
postorder(root); // 输出:4 5 2 6 7 3 1
free(root);
free(l1);
free(r1);
free(l2);
free(r2);
free(l3);
free(r3);
return 0;
}
```
以上是输出二叉树的代码,其中 `Stack` 是我自己封装的栈,可替换为标准库中的栈。
阅读全文