c语言实现非递归方式先序遍历二叉树
时间: 2023-10-15 12:08:30 浏览: 70
好的,这是一个关于编程的问题。非递归方式的先序遍历二叉树可以使用栈来实现。具体实现方式可以参考下面的代码:
```c
void preorder_stack(BinaryTree *root) {
Stack *stack = create_stack();
BinaryTree *p = root;
while (p || !is_stack_empty(stack)) {
while (p) {
printf("%d ", p->data); // 先访问根节点
push_stack(stack, p);
p = p->left; // 进入左子树
}
if (!is_stack_empty(stack)) {
p = pop_stack(stack);
p = p->right; // 进入右子树
}
}
destroy_stack(stack);
}
```
其中,Stack是栈的定义,create_stack()、push_stack()、pop_stack()、is_stack_empty()和destroy_stack()是栈的基本操作函数。
希望能够帮助到您。
相关问题
c语言实现非递归先序遍历二叉树
非递归先序遍历二叉树可以使用栈来实现。具体实现思路如下:
1. 创建一个栈,并将根节点入栈。
2. 当栈不为空时,执行以下操作:
- 弹出栈顶节点,并输出其值。
- 如果该节点有右子树,则将右子树入栈。
- 如果该节点有左子树,则将左子树入栈。
3. 当栈为空时,遍历完成。
以下是示例代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct Stack {
int top;
int size;
TreeNode **data;
} Stack;
Stack *createStack(int size) {
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->top = -1;
stack->size = size;
stack->data = (TreeNode **)malloc(size * sizeof(TreeNode *));
return stack;
}
void push(Stack *stack, TreeNode *node) {
if (stack->top == stack->size - 1) {
printf("Stack overflow!\n");
return;
}
stack->data[++stack->top] = node;
}
TreeNode *pop(Stack *stack) {
if (stack->top == -1) {
printf("Stack underflow!\n");
return NULL;
}
return stack->data[stack->top--];
}
void preorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
Stack *stack = createStack(100);
push(stack, root);
while (stack->top != -1) {
TreeNode *node = pop(stack);
printf("%d ", node->val);
if (node->right != NULL) {
push(stack, node->right);
}
if (node->left != NULL) {
push(stack, node->left);
}
}
free(stack->data);
free(stack);
}
int main() {
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode *)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
preorderTraversal(root);
free(root->left);
free(root->right->left);
free(root->right->right);
free(root->right);
free(root);
return 0;
}
```
用C语言实现非递归二叉树先序遍历、中序遍历和后序遍历
下面是用C语言实现非递归二叉树先序遍历、中序遍历和后序遍历的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct Stack {
TreeNode *data[MAX_STACK_SIZE];
int top;
} Stack;
void push(Stack *stack, TreeNode *node) {
if (stack->top == MAX_STACK_SIZE - 1) {
printf("Stack overflow.\n");
return;
}
stack->data[++stack->top] = node;
}
TreeNode *pop(Stack *stack) {
if (stack->top == -1) {
printf("Stack underflow.\n");
exit(1);
}
return stack->data[stack->top--];
}
int is_empty(Stack *stack) {
return stack->top == -1;
}
void preorder_traversal(TreeNode *root) {
if (!root) {
return;
}
Stack stack = { .top = -1 };
push(&stack, root);
while (!is_empty(&stack)) {
TreeNode *node = pop(&stack);
printf("%d ", node->val);
if (node->right) {
push(&stack, node->right);
}
if (node->left) {
push(&stack, node->left);
}
}
printf("\n");
}
void inorder_traversal(TreeNode *root) {
if (!root) {
return;
}
Stack stack = { .top = -1 };
TreeNode *node = root;
while (node || !is_empty(&stack)) {
if (node) {
push(&stack, node);
node = node->left;
} else {
node = pop(&stack);
printf("%d ", node->val);
node = node->right;
}
}
printf("\n");
}
void postorder_traversal(TreeNode *root) {
if (!root) {
return;
}
Stack stack = { .top = -1 };
TreeNode *node = root, *prev = NULL;
while (node || !is_empty(&stack)) {
if (node) {
push(&stack, node);
node = node->left;
} else {
node = stack.data[stack.top];
if (node->right && node->right != prev) {
node = node->right;
} else {
printf("%d ", node->val);
prev = node;
node = NULL;
pop(&stack);
}
}
}
printf("\n");
}
int main() {
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode *)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
printf("Preorder traversal: ");
preorder_traversal(root);
printf("Inorder traversal: ");
inorder_traversal(root);
printf("Postorder traversal: ");
postorder_traversal(root);
return 0;
}
```
这个代码示例中,我们使用了栈来实现非递归遍历二叉树。对于先序遍历,我们先将根节点入栈,然后弹出栈顶元素,先访问该节点,再将其右子节点和左子节点依次入栈。对于中序遍历,我们从根节点开始,先将所有左子节点入栈,然后弹出栈顶元素,访问该节点,再将其右子节点入栈。对于后序遍历,我们需要记录上一个访问的节点,以便在访问完右子节点后,再访问父节点。具体实现可以参考代码示例。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)