非递归方式建树并按任一种非递归遍历次序输出二叉树中

1、/非递归方式建树，并按任一种非递归遍历次序输出二叉树中的所有结点；#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define MaxSize 50typedef char ElemType;typedef struct TNodeElemType 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)&

2、quot;/-void CreateBTree(BTree *T,ElemType *Str); /非递归建树；void TraverseBTree(BTree *T); / 选择非递归算法的遍历方式;void PreOrderUnrec(BTree *T); / 先序遍历非递归算法;void InOrderUnrec(BTree *T); /中序遍历非递归算法;void PostOrderUnrec(BTree *T); / 后序遍历非递归算法;/-int main(void)BTree *T = NULL; printf("n二叉树的广义表格式为：nt"); puts(

3、str);CreateBTree(&T,str);TraverseBTree(T);system("pause"); return 0;/-void CreateBTree(BTree *T,ElemType *Str) / 按二叉树广义表建立对应的二叉树存储结构;BTree *p = NULL,*StackMaxSize;/数组为存储树根结点指针的栈int top = -1; /top 为 Stack 栈的栈顶指针 ;char flag; /flag 为处理结点的左子树(L) 和右子树 (R) 的标记 ;*T = NULL;while(*Str)if (*Str

4、= '(') Stack+top = p;flag = 'L' /入栈 ;else if(*Str = ')') -top; /出栈 ;,p 为指向树结点的指针;else if(*Str = ',') flag = 'R'elseif(!(p = (BTree *)malloc(sizeof(BTree) exit (1);p->data = *Str;p->lchild = p->rchild = NULL; /初始化新结点 ;if(*T = NULL) *T = p; /根结点 ;elseif

5、(flag = 'L') Stacktop->lchild = p;if(flag = 'R') Stacktop->rchild = p;+Str;/-void TraverseBTree(BTree *T) / 选择非递归算法的遍历方式int mark;printf("n 非递归算法遍历方式：nt1 -前序遍历 nt2 -printf("nt3 -后序遍历 nt4 -退 出n 请选择： n");中序遍历");if(T = NULL) printf("该树为空！ n");while(T !

6、= 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);elsesystem("cls"); printf("n二叉树的广义表格式为：nt"); puts(

7、str);printf("n 非递归算法遍历方式：printf("nt3 -后序遍历 nt4 -nt1 - 退 出n前序遍历请选择：nt2 - n");中序遍历");printf(" 数据非法，重新输入！n");printf("n");printf("n 请多多指教！by Haroldi.");/-void PreOrderUnrec(BTree *T) / 先序遍历非递归算法;BTree *p = T,*StackMaxSize;int top = -1;while (p != NULL |

8、top != -1)while (p!=NULL) /遍历左子树 ;printf("%c ",p->data);Stack+top = p;p=p->lchild;if (top != -1) / 下次 while 内循环中实现右子树遍历；p = Stacktop-;p=p->rchild;/-void InOrderUnrec(BTree *T) /中序遍历非递归算法；BTree *p = T,*StackMaxSize;int top = -1;while (p != NULL | top != -1)while (p!=NULL)Stack+top

9、= p;p=p->lchild;if (top != -1)p = Stacktop-;printf("%c ",p->data);p=p->rchild;/-void PostOrderUnrec(BTree *T) / 后序遍历非递归算法;BTree *p = T,*StackMaxSize;int top = -1;char flagMaxSize;/ 标识，若为 'R'则说明左右孩子均已遍历while(p != NULL | top != -1)while(p != NULL)Stack+top = p;flagtop = 'L'p = p->lchild;while(top != -1 && flagtop = 'R'),