二叉树非递归遍历 - 先序 中序 后序
2018-08-16 本文已影响2人
Co_zy
(数字建立二叉树)
#include <stdio.h>
#include <stdlib.h>
#define maxsize 100
typedef struct BTNode
{
int data;
struct BTNode *left;
struct BTNode *right;
}BTNode;
//逐个输入先序遍历建立二叉树
void CreateBiTree(BTNode *&T)
{
int c;
scanf("%d",&c);
if(c == -1)
T = NULL;
else
{
T = (BTNode *)malloc(sizeof(BTNode));
CreateBiTree(T->left);
T->data = c;
CreateBiTree(T->right);
}
}
int visit(int c)
{
printf("%d ",c);
return 1;
}
//非递归先序遍历
void preorderNonrecursion(BTNode *bt)
{
if(bt!=NULL)
{
BTNode *stack[maxsize];
int top = -1;
BTNode *p;
stack[++top] = bt;
while(top!=-1)
{
p = stack[top--];
visit(p->data);
if(p->right!=NULL)
stack[++top] = p->right;
if(p->left != NULL)
stack[++top] = p->left;
}
}
}
//非递归中序遍历
void inorderNonrecursion(BTNode *bt)
{
if(bt!=NULL)
{
BTNode *stack[maxsize];
int top = -1;
BTNode *p;
p = bt;
while(top!=-1 || p!=NULL)
{
while(p!=NULL)
{
stack[++top] = p;
p = p->left;
}
if(top!=-1)
{
p = stack[top--];
visit(p->data);
p = p->right;
}
}
}
}
//非递归后序遍历
void postorderNonrecursion(BTNode *bt)
{
if(bt!=NULL)
{
BTNode *stack1[maxsize];
BTNode *stack2[maxsize];
int top1 = -1;
int top2 = -1;
BTNode *p = NULL;
stack1[++top1] = bt;
while(top1 != -1)
{
p = stack1[top1--];
stack2[++top2] = p;
if(p->left != NULL)
stack1[++top1] = p->left;
if(p->right != NULL)
stack1[++top1] = p->right;
}
while(top2 != -1)
{
p = stack2[top2--];
visit(p->data);
}
}
}
int main()
{
BTNode *T;
CreateBiTree(T);
preorderNonrecursion(T);
printf("\n");
inorderNonrecursion(T);
printf("\n");
postorderNonrecursion(T);
printf("\n");
return 0;
}
输入
1 2 3 -1 -1 5 -1 -1 4 -1 -1
输出 (分别是先序,中序,后序)
1 2 3 5 4
3 2 5 1 4
3 5 2 4 1