7.cpp

约瑟夫环源代码,前中后序递归遍历二叉树

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define N 100
#define null 0
#define maxstack 50
typedef struct node
{ char data;
  struct node *lchild;
  struct node *rchild;
}* bitree;

struct stackitem
{struct node *a;
 int b;
};

struct stack
{int top;
 struct stackitem A[maxstack];
}s;


int setup(bitree &t)
{char ch=' ';
 scanf("%c",&ch);
 if(ch==' ')t=null;
 else{
	 if(!(t=(node *)malloc(sizeof(node))))return 0;
	 t->data=ch;          //建立根节点
	 printf("%c",t->data);
	 setup(t->lchild);//建立左子树
	 setup(t->rchild);//建立右子树
 }
 return 1;
}

void push(struct stackitem x)//进栈
{int p;
 p=s.top;
 if(p==maxstack)
	 printf("stack overflow");
 else
 {s.top=p+1;
  s.A[s.top]=x;
 }
}

struct stackitem pop()//出栈
{int p;
 struct stackitem n;
 p=s.top;
 if(p==-1)
	 printf("stack underflow");
 else
 {n=s.A[p];
  s.top=p-1;
  return(n);
 }
}

void travl(bitree t)//中序非递归调用
{int b1;
 struct stackitem p;
 b1=1;
 p.b=b1;
 p.a=t;
 s.top=-1;
 while(t||s.top!=-1)
	 if(t)
	 {p.a=t;//方根节点
	  push(p);
	  t=t->lchild;//访问左子树
	 }
	 else
	 {t=pop().a;
	  printf("%c",t->data);
	  t=t->rchild;//访问右子树
	 }
}

void main()
{bitree t=null;
 printf("输入数值:");
 setup(t);
 printf("\n中序遍历非递归结果:");
 travl(t);
 printf("\n");
}