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;
  node *lchild;
  node *rchild;
}* bitree;

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

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

char e[N+1];

int CreateBiTree(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);
	 CreateBiTree(t->lchild);//建立左子树
	 CreateBiTree(t->rchild);//建立右子树
 }
 return 1;
}


void push(struct stackitem e)//插入元素e为新的栈顶元素,入栈
{int p;
 p=s.top;
 if(p==maxstack)
	 printf("stack overflow");
 else
 {s.top=p+1;
  s.A[s.top]=e;
 }
}
 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 PreOrderTraverse(bitree t)//先序非递归调用
{int b1;
 struct stackitem p;
 b1=0;
 p.b=b1;
 p.a=t;
 s.top=-1;
 while(t!=null||s.top!=-1)
	 if(t!=null)
	 {printf("%c",t->data);    //访问根节点
          p.a=t;               
	  push(p);
	  t=t->lchild;        //访问左子树    
	 }
	 else
	 {t=pop().a;
          t=t->rchild;        //访问右子树
         }
}

void main()
{bitree t=null;
 printf("输入二叉树中结点的值:");
 CreateBiTree(t);
 printf("\n先序遍历非递归遍历结果为:");
 PreOrderTraverse(t);
}