数据结构——二叉树的操作(遍历及树形输出).doc

/*实验三：二叉树遍历操作验证*/ #includeiostream #includestdio.h #includestdlib.h #includestack #includemap #includequeue #includemath.h using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 int LeafNum;//叶子结点个数 //定义结构体 typedef struct BiTNode{ char data; //存放值 struct BiTNode *lchild,*rchild; //左右孩子 }BiTNode,*BiTree; //先序输入二叉树结点的值，空格表示空树 void createBiTree(BiTree T) { char ch; //输入结点时用 scanf(%c,ch); if(ch== ) //若输入空格，该值为空,且没有左右孩子 { T=NULL; }else{ T=(BiTNode *)malloc(sizeof(BiTNode)); //分配结点空间 if(!T) //分配失败 { exit(OVERFLOW); } T-data=ch; //生成根结点 createBiTree(T-lchild); //构造左子树 createBiTree(T-rchild); //构造右子树 } } //递归方法先序遍历二叉树 void preOrderTraverse(BiTree T) { if(T) //若非空 { if(T-data) { //输出 printf(%c,T-data); } preOrderTraverse(T-lchild); preOrderTraverse(T-rchild); } } //递归方法中序遍历二叉树 void inOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T-lchild); if(T-data) { //输出 printf(%c,T-data); } preOrderTraverse(T-rchild); } } //递归方法后序遍历二叉树 void postOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T-lchild); preOrderTraverse(T-rchild); if(T-data) { //输出 printf(%c,T-data); } } } //层序遍历二叉树 void LevelTraverse(BiTree T) { queueBiTree q;//建队 q.push(T);//根节点入队 BiTree p; while(!q.empty()) { p=q.front(); //获得队列的首元素 q.pop(); //首元素出队 coutp-data ; //输出结点的值 if(p-lchild!=NULL) //若结点的左孩子不空 { q.push(p-lchild); } if(p-rchild!=NULL)//若结点的右孩子不空 { q.push(p-rchild); } } } //非递归方法前序遍历二叉树 void stackPreOrderTraverse(BiTree T) { stackBiTree s; //建栈 s.push(T); //根结点入栈 BiTree p; //栈首元素 while(!s.empty()) { while((p=s.top())p) { printf(%c,p-data); s.push(p-lchild); //左孩子入栈,直到走到尽头 } s.pop(); //空指针出栈 if(!s.empty()) { p=s.top();//获得栈顶元素 s.pop(); //出栈 s.push(p-rchild); //右孩子入栈 } } } //非递归方法中序遍历二叉树 void stackInOrderTraverse(BiTree T) { stackBiTree s; //建栈 s.push(T); //入栈 BiTree p; //栈首元素 while(!s.empty()) { w