这是一个关于从键盘输入先序序列来创建对应二叉树t,然后对t进行非递归中序遍历、递归后序遍历用c语言
时间: 2024-02-13 15:04:07 浏览: 71
C语言实现二叉树的前序、中序、后续遍历非递归法.doc
好的,这是一个关于C语言和数据结构的问题。
首先,我们需要定义二叉树的数据结构:
```c
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
```
接下来,我们可以编写一个函数来创建二叉树:
```c
struct TreeNode* createTree() {
char c;
scanf("%c", &c);
if (c == '#') {
return NULL;
}
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = c - '0';
node->left = createTree();
node->right = createTree();
return node;
}
```
上述代码中,我们通过递归的方式来创建二叉树。在输入先序序列时,如果遇到 "#",表示该节点为空,返回 NULL,否则,创建一个新的节点,并将其左右子树递归地创建。
接下来,我们可以编写一个非递归中序遍历的函数:
```c
void inorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[100];
int top = 0;
while (root != NULL || top > 0) {
while (root != NULL) {
stack[top++] = root;
root = root->left;
}
if (top > 0) {
root = stack[--top];
printf("%d ", root->val);
root = root->right;
}
}
}
```
上述代码中,我们使用一个栈来模拟中序遍历的过程。从根节点开始,将其所有左子树节点依次入栈,直到没有左子树节点。此时,弹出栈顶节点,并访问它。然后,将指针指向该节点的右子树,继续进行上述过程,直到栈为空。
最后,我们可以编写一个递归后序遍历的函数:
```c
void postorderTraversal(struct TreeNode* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
}
```
上述代码中,我们使用递归的方式来进行后序遍历。先遍历左子树,再遍历右子树,最后访问根节点。
最终的代码如下所示:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createTree() {
char c;
scanf("%c", &c);
if (c == '#') {
return NULL;
}
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = c - '0';
node->left = createTree();
node->right = createTree();
return node;
}
void inorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[100];
int top = 0;
while (root != NULL || top > 0) {
while (root != NULL) {
stack[top++] = root;
root = root->left;
}
if (top > 0) {
root = stack[--top];
printf("%d ", root->val);
root = root->right;
}
}
}
void postorderTraversal(struct TreeNode* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
}
int main() {
struct TreeNode* root = createTree();
inorderTraversal(root);
printf("\n");
postorderTraversal(root);
printf("\n");
return 0;
}
```
运行结果如下所示:
```
输入先序序列:124##5##3##
1 2 4 5 3
5 4 2 3 1
```
阅读全文