#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
typedef struct lNode
{
char data;
struct lNode *lchild;
struct lNode *rchild;
}LNODE,*Tree;
typedef struct Node
{
Tree data;
struct Node * Next;
}NODE, * PNODE;
typedef struct Stack
{
PNODE pBottom;
PNODE pTop;
}STACK, * PSTACK;
//函数声明
PSTACK initStack(void);//创建栈
void push(PSTACK S,Tree val);//压栈
void pop(PSTACK S);//出栈
bool stackEmpty(PSTACK pS);
Tree CreateBiTree();//建树
void pretraverse(Tree T);//先序递归遍历
void Intraverse(Tree T);//中序递归遍历
void posttraverse(Tree T);//后序递归遍历
void NoIntraverse(Tree T);//中序非递归遍历
int main()
{
Tree T;
T=CreateBiTree();
pretraverse(T);printf("\n");
Intraverse(T);
printf("\n");
posttraverse(T);printf("\n");
NoIntraverse(T);printf("\n");
return 0;
}
//建树
Tree CreateBiTree()
{
char ch;
Tree T;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
T = (Tree)malloc(sizeof(LNODE));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根节点
}
//先序递归遍历(遍历顺序:根左右)
void pretraverse(Tree T)
{
if(T!=NULL)
{
printf("%c",T->data);//输出根节点数据
pretraverse(T->lchild);//遍历左子树
pretraverse(T->rchild);//遍历右子树
}
}
//中序递归遍历(遍历顺序:左根右)
void Intraverse(Tree T)
{
if(T!=NULL)
{
Intraverse(T->lchild);//遍历左子树
printf("%c",T->data);//输出根节点数据
Intraverse(T->rchild);//遍历右子树
}
}
//后序递归遍历(遍历顺序:左右根)
void posttraverse(Tree T)
{
if(T!=NULL)
{
posttraverse(T->lchild);//遍历左子树
posttraverse(T->rchild);//遍历右子树
printf("%c",T->data);//输出根节点数据
}
}
//中序遍历(非递归遍历)
void NoIntraverse(Tree T)
{
PSTACK s;
s=initStack();
Tree p=T;
while(p!=NULL||!stackEmpty(s))
{
while(p)
{
push(s,p);
p=p->lchild;
}
if(!stackEmpty(s))
{
pop(s);
p=p->rchild;
}
}
}
PSTACK initStack(void)
{
PSTACK pS;
pS->pTop=(PNODE)malloc(sizeof(NODE));
if(pS->pTop==NULL)
{
printf("动态内存分配失败!");
exit(-1);
}
else
{
pS->pBottom=pS->pTop;
pS->pBottom->Next=NULL;
}
return pS;
}
void push(PSTACK pS,Tree val)
{
PNODE q;
q=(PNODE)malloc(sizeof(NODE));
if(q==NULL)
{
printf("动态内存分配失败!");
exit(-1);
}
else
{
q->data=val;
q->Next=pS->pTop;
pS->pTop=q;
}
}
void pop(PSTACK pS)
{
PNODE q;
if(pS->pTop==NULL)
{
printf("动态内存分配失败!");
exit(-1);
}
else
{
q=pS->pTop;
printf("%c",q->data);
pS->pTop=q->Next;
free(q);
}
}
bool stackEmpty(PSTACK pS)
{
if(pS->pTop==pS->pBottom)
{
return true;
}
return false;
}
相关文章
- 第4章第1节练习题2 二叉树的基本操作(非递归实现)
- 二叉树的前中后序非递归遍历算法实现
- 算法导论 习题10.4-5 二叉树的遍历(非递归,O(1)存储)
- [数据结构]二叉树的前中后序遍历(递归+迭代实现)
- 二叉树的创建(先序)先序中序后序遍历(递归算法),求叶子结点个数,求树的高度,树中结点的个数,值为data的结点所在的层数
- 数据结构(一)——二叉树 前序、中序、后序、层次遍历及非递归实现 查找、统计个数、比较、求深度的递归实现
- 【IT笔试面试题整理】给定二叉树先序中序,建立二叉树的递归算法
- java栈实现二叉树的非递归遍历的示例代码
- 数据结构初阶--二叉树(前中后序遍历递归+非递归实现+相关求算结点实现)
- C语言数据结构之二叉树的非递归后序遍历算法