前序遍历创建表达式树
时间: 2023-12-13 20:30:50 浏览: 34
前序遍历创建表达式树的步骤如下:
1. 从前往后扫描表达式,遇到数字则创建一个节点,将该数字作为节点的值,将该节点入栈。
2. 遇到运算符,则创建一个节点,将该运算符作为节点的值,将该节点入栈。
3. 重复步骤1和2,直到扫描完整个表达式。
4. 从栈中弹出两个节点作为当前节点的左右子节点,当前节点为上一步入栈的运算符节点。
5. 将当前节点入栈。
6. 重复步骤4和5,直到栈中只剩下一个节点,即为根节点。
前序遍历表达式树的步骤如下:
1. 访问当前节点。
2. 如果当前节点有左子节点,则递归遍历左子树。
3. 如果当前节点有右子节点,则递归遍历右子树。
下面是一个示例代码,用于创建一个表达式树并进行前序遍历:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct Stack {
int top;
int capacity;
TreeNode **array;
} Stack;
Stack *createStack(int capacity) {
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->top = -1;
stack->capacity = capacity;
stack->array = (TreeNode **)malloc(capacity * sizeof(TreeNode *));
return stack;
}
int isFull(Stack *stack) {
return stack->top == stack->capacity - 1;
}
int isEmpty(Stack *stack) {
return stack->top == -1;
}
void push(Stack *stack, TreeNode *node) {
if (isFull(stack)) {
return;
}
stack->array[++stack->top] = node;
}
TreeNode *pop(Stack *stack) {
if (isEmpty(stack)) {
return NULL;
}
return stack->array[stack->top--];
}
TreeNode *createNode(char val) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;}
TreeNode *buildExpressionTree(char *expression) {
Stack *stack = createStack(strlen(expression));
for (int i = strlen(expression) - 1; i >= 0; i--) {
if (isdigit(expression[i])) {
push(stack, createNode(expression[i]));
} else {
TreeNode *node = createNode(expression[i]);
node->left = pop(stack);
node->right = pop(stack);
push(stack, node);
}
}
return pop(stack);
}
void preorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%c ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int main() {
char expression[] = "+9*26";
TreeNode *root = buildExpressionTree(expression);
printf("前序遍历表达式树: ");
preorderTraversal(root);
return 0;
}
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)