//非递归方式建树，并按任一种非递归遍历次序输出二叉树中的所有结点；
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MaxSize 50
typedef char ElemType;
typedef struct TNode{
ElemType data;
struct TNode *lchild,*rchild;
}BTree;
//------------------------------------------------------------------------------
ElemType str[]="A(B(C(D,E(F,G(,H))),I(J,K(L))),M)"; //"A(B(D,E(G,H(I))),C(F))";
//------------------------------------------------------------------------------
void CreateBTree(BTree **T,ElemType *Str); //非递归建树；
void TraverseBTree(BTree *T); //选择非递归算法的遍历方式;
void PreOrderUnrec(BTree *T); //先序遍历非递归算法;
void InOrderUnrec(BTree *T); //中序遍历非递归算法;
void PostOrderUnrec(BTree *T); //后序遍历非递归算法;
void LevelOrderUnrec(BTree *T); //层次遍历非递归算法;
//------------------------------------------------------------------------------
int main(void)
{
BTree *T = NULL; printf("\n二叉树的广义表格式为：\n\t"); puts(str);
CreateBTree(&T,str);
TraverseBTree(T);
system("pause"); return 0;
}
//------------------------------------------------------------------------------
void CreateBTree(BTree **T,ElemType *Str)
{ //按二叉树广义表建立对应的二叉树存储结构;
BTree *p = NULL,*Stack[MaxSize];//数组为存储树根结点指针的栈,p为指向树结点的指针;
int top = -1; //top为Stack栈的栈顶指针;
char flag; //flag为处理结点的左子树(L)和右子树(R)的标记;
*T = NULL;
while(*Str)
{
if (*Str == '(') {Stack[++top] = p;flag = 'L';} //入栈;
else if(*Str == ')') --top; //出栈;
else if(*Str == ',') flag = 'R';
else
{
if(!(p = (BTree *)malloc(sizeof(BTree)))) exit (1);
p->data = *Str;
p->lchild = p->rchild = NULL; //初始化新结点;
if(*T == NULL) *T = p; //根结点;
else
{
if(flag == 'L') Stack[top]->lchild = p;
if(flag == 'R') Stack[top]->rchild = p;
}
}
++Str;
}
}
//------------------------------------------------------------------------------
void TraverseBTree(BTree *T) //选择非递归算法的遍历方式;
{
int mark;
printf("\n非递归算法遍历方式：\n\t1 --- 前序遍历\n\t2 --- 中序遍历");
printf("\n\t3 --- 后序遍历\n\t4 --- 按层遍历\n\tq --- 退 出\n请选择：\n");
if(T == NULL) printf("该树为空！\n");
while(T != NULL && scanf("%d",&mark)==1)
{
if(mark==1) {printf("先序遍历:\t");PreOrderUnrec(T);}
else if(mark==2) {printf("中序遍历:\t");InOrderUnrec(T);}
else if(mark==3) {printf("后序遍历:\t");PostOrderUnrec(T);}
else if(mark==4) {printf("层次遍历:\t");LevelOrderUnrec(T);}
else
{
system("cls"); printf("\n二叉树的广义表格式为：\n\t"); puts(str);
printf("\n非递归算法遍历方式：\n\t1 --- 前序遍历\n\t2 --- 中序遍历");
printf("\n\t3 --- 后序遍历\n\t4 --- 按层遍历\n\tq --- 退 出\n请选择：\n");
printf("数据非法，重新输入！\n");
}
printf("\n");
}
printf("\n请多多指教！ by Haroldi.");
}
//------------------------------------------------------------------------------
void PreOrderUnrec(BTree *T) //先序遍历非递归算法;
{
BTree *p = T,*Stack[MaxSize];
int top = -1;
while (p != NULL || top != -1)
{
while (p!=NULL) //遍历左子树;
{
printf("%c ",p->data);
Stack[++top] = p;
p=p->lchild;
}
if (top != -1) //下次while内循环中实现右子树遍历；
{
p = Stack[top--];
p=p->rchild;
}
}
}
//------------------------------------------------------------------------------
void InOrderUnrec(BTree *T) //中序遍历非递归算法；
{
BTree *p = T,*Stack[MaxSize];
int top = -1;
while (p != NULL || top != -1)
{
while (p!=NULL)
{
Stack[++top] = p;
p=p->lchild;
}
if (top != -1)
{
p = Stack[top--];
printf("%c ",p->data);
p=p->rchild;
}
}
}
//------------------------------------------------------------------------------
void PostOrderUnrec(BTree *T) //后序遍历非递归算法;
{
BTree *p = T,*Stack[MaxSize];
int top = -1;
char flag[MaxSize];//标识，若为'R'则说明左右孩子均已遍历,防止再次走过,形成死循环；
while(p != NULL || top != -1)
{
while(p != NULL)
{
Stack[++top] = p;
flag[top] = 'L';
p = p->lchild;
}
while(top != -1 && flag[top] == 'R')
{
printf("%c ",Stack[top--]->data); //flag='R',在此退栈；
}
if(top != -1) {flag[top] = 'R'; p = Stack[top]->rchild;}
}
}
//------------------------------------------------------------------------------
void LevelOrderUnrec(BTree *T) //层次遍历非递归算法;
{
BTree *p,*Queue[MaxSize]; //定义队列,存储树结点指针;
int front,rear; //定义队首和队尾指针;
front = rear = 0; //初始化置0,空队列;
if(T != NULL)
{
rear = (rear+1)%MaxSize; //队尾指针后移;
Queue[rear] = T; //树根结点入队;
}
while (front != rear) //队列非空时;
{
front = (front+1)%MaxSize; //队首指针后移;
p = Queue[front]; //删除队首结点;
printf("%c ",p->data); //输出队首结点的值;
if(p->lchild != NULL) //若存在左孩子，则左孩子指针入队;
{
rear = (rear+1)%MaxSize;
Queue[rear] = p->lchild;
}
if(p->rchild != NULL) //若存在右孩子，则右孩子指针入队;
{
rear = (rear+1)%MaxSize;
Queue[rear] = p->rchild;
}
}
}
//------------------------------------------------------------------------------
