编写二叉树的前序(或中序)的非递+归遍历算法并进行测试用c语言代码实现
时间: 2024-02-16 10:59:53 浏览: 19
以下是二叉树前序遍历的非递归算法实现,以C语言为例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 //定义栈的最大容量
//定义二叉树结点结构体
typedef struct Node {
int data;
struct Node *lchild, *rchild;
} Node;
//定义栈结构体
typedef struct Stack {
Node *data[MAXSIZE];
int top;
} Stack;
//初始化栈
void initStack(Stack* s) {
s->top = -1;
}
//判断栈是否为空
int isEmpty(Stack* s) {
return s->top == -1;
}
//进栈
void push(Stack* s, Node* node) {
if (s->top == MAXSIZE - 1) {
printf("栈已满,无法入栈!\n");
return;
}
s->data[++s->top] = node;
}
//出栈
Node* pop(Stack* s) {
if (isEmpty(s)) {
printf("栈已空,无法出栈!\n");
return NULL;
}
return s->data[s->top--];
}
//前序遍历非递归实现
void preOrder(Node* root) {
if (root == NULL) {
printf("二叉树为空!\n");
return;
}
Stack s; //定义栈
initStack(&s); //初始化栈
push(&s, root); //根结点入栈
while (!isEmpty(&s)) {
Node* node = pop(&s); //栈顶结点出栈
printf("%d ", node->data); //输出结点的值
if (node->rchild != NULL) { //右子树非空,右子树入栈
push(&s, node->rchild);
}
if (node->lchild != NULL) { //左子树非空,左子树入栈
push(&s, node->lchild);
}
}
printf("\n");
}
//创建二叉树
Node* createTree() {
int data;
scanf("%d", &data);
if (data == -1) { //输入-1表示该结点为空
return NULL;
}
Node* node = (Node*) malloc(sizeof(Node)); //创建新结点
node->data = data;
node->lchild = createTree(); //递归创建左子树
node->rchild = createTree(); //递归创建右子树
return node;
}
int main() {
Node* root = createTree(); //创建二叉树
printf("前序遍历结果为:");
preOrder(root); //前序遍历二叉树
return 0;
}
```
运行程序后,输入二叉树的结点数据,以-1表示该结点为空,例如输入以下数据:
```
1 2 4 -1 -1 5 -1 -1 3 -1 6 -1 -1
```
则程序输出结果为:
```
前序遍历结果为:1 2 4 5 3 6
```