用c语言实现如下要求:根据给定的二叉树,先人工对其进行先序遍历,根据先序遍历的结果编写程序创建该二叉树;然后用非递归中序遍历算法,输出中序遍历的结果。
时间: 2023-11-22 15:53:13 浏览: 96
以下是用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点的结构体
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
// 先序遍历创建二叉树
Node* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
Node *root = (Node*) malloc(sizeof(Node));
root->data = val;
root->left = createTree();
root->right = createTree();
return root;
}
// 非递归中序遍历
void inorderTraversal(Node *root) {
Node *stack[100];
int top = -1;
Node *p = root;
while (p || top > -1) {
while (p) {
stack[++top] = p;
p = p->left;
}
if (top > -1) {
p = stack[top--];
printf("%d ", p->data);
p = p->right;
}
}
}
int main() {
printf("请输入先序遍历结果,-1表示空结点:\n");
Node *root = createTree();
printf("中序遍历结果为:\n");
inorderTraversal(root);
return 0;
}
```
其中,createTree()函数实现了先序遍历创建二叉树的功能,inorderTraversal()函数实现了非递归中序遍历的功能。程序先让用户输入先序遍历的结果,然后根据这个结果创建二叉树,最后输出中序遍历的结果。
阅读全文