用c语言尽量详细地告诉我括号表示法不用递归输出二叉树的代码
时间: 2023-06-07 18:07:19 浏览: 96
建立二叉树链表(非递归)C语言
好的,请看以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 二叉树的结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 创建一个新的节点
struct TreeNode* newNode(int val) {
struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
node->val = val;
node->left = node->right = NULL;
return node;
}
// 执行二叉树的中序遍历
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
struct TreeNode* curr = root;
struct TreeNode* stack[INT_MAX]; // 定义一个栈
int top = -1;
while (curr != NULL || top != -1) {
while (curr != NULL) {
stack[++top] = curr;
curr = curr->left; // 将左子树节点加入栈中
}
// 弹出栈顶元素,然后遍历其右子树
struct TreeNode* node = stack[top--];
printf("%d ", node->val); // 输出节点的值
curr = node->right;
}
}
int main() {
// 创建二叉树
struct TreeNode* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// 以括号表示法输出二叉树
printf("二叉树的括号表示法:\n");
inorderTraversal(root);
printf("\n");
return 0;
}
```
以上代码定义了一个 `TreeNode` 结构体,其包含一个整数值 `val`、左子树节点指针 `left` 和右子树节点指针 `right`,以及一个创建新节点的函数 `newNode`。
在 `inorderTraversal` 函数中,使用循环和栈来执行二叉树的中序遍历,其中循环条件是当前节点指针 `curr` 不为空或者栈不为空,首先将所有左子树节点加入栈中,然后弹出栈顶元素并遍历其右子树。每次遍历一个节点时,输出其值即可。最后在 `main` 函数中调用 `inorderTraversal` 函数,即可输出二叉树的值。
需要注意的是,此处的二叉树以链式存储方式实现,而非数组。
阅读全文