#include <string.h>
#include <stdlib.h>
#define TElemType int
int top=-1;
//top变量时刻表示栈顶元素所在位置
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
*T=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->data=1;
(*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->data=2;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=6;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=4;
(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=7;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;
(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->rchild->data=8;
(*T)->rchild->rchild->lchild=NULL;
(*T)->rchild->rchild->rchild=NULL;
(*T)->lchild->lchild->data=5;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;
}
//前序和中序遍历使用的进栈函数
void push(BiTNode** a,BiTNode* elem){
a[++top]=elem;
}
//弹栈函数
void pop( ){
if (top==-1) {
return ;
}
top--;
}
void displayElem(BiTNode* elem){
printf("%d ",elem->data);
}
//拿到栈顶元素
BiTNode* getTop(BiTNode**a){
return a[top];
}
//中序遍历非递归算法
void InOrderTraverse1(BiTree Tree){
BiTNode* a[20];//定义一个顺序栈
BiTNode * p;//临时指针
push(a, Tree);//根结点进栈
while (top!=-1) {//top!=-1说明栈内不为空，程序继续运行
while ((p=getTop(a)) &&p){//取栈顶元素，且不能为NULL
push(a, p->lchild);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈
}
pop();//跳出循环，栈顶元素肯定为NULL，将NULL弹栈
if (top!=-1) {
p=getTop(a);
pop();
displayElem(p);
push(a, p->rchild);
}
}
}
int main(){
BiTree Tree;
CreateBiTree(&Tree);
printf("中序遍历算法: \n");
InOrderTraverse1(Tree);
}
#include<stdio.h>
#include<malloc.h>
typedef struct st{
char data;
struct st *r;
struct st *l;
}*link,ll;
char s[20]="ABC##DE##F##G##";//二叉树序列
int i=0;
void create_tree(link &tree)//先序递归建树
{
if(s[i]=='#')
tree=NULL,i++;
else
{
tree=(link)malloc(sizeof(ll));
tree->data=s[i],i++;
create_tree(tree->l);
create_tree(tree->r);
}
}
void in_1(link tree)//递归中序遍历
{
if(tree)
{
in_1(tree->l);
printf("%c ",tree->data);
in_1(tree->r);
}
}
void in_2(link tree)//非递归中序遍历
{
link s[20];//储存指针结点
int top =-1;
link p = tree;
while(p!=NULL||top!=-1){
if(p!=NULL){
s[++ top] = p;
p = p->l;
}else{
p = s[top --];
printf("%c ",p->data); //出栈时，访问输出
p = p->r;
}
}
}
int main()
{
link T=NULL;
create_tree(T);//建树
printf("递归中序遍历\n");
in_1(T);//递归中序遍历
printf("\n非递归中序遍历\n");
in_2(T);//非递归中序遍历
return 0;
}
