#include <stdio.h>#include <iostream>#include <queue>#include <stack>#include <malloc.h>#define SIZE 100using namespace std;typedef struct BiTNode //定义二叉树节点结构{char data; //数据域struct BiTNode *lchild,*rchild; //左右孩子指针域}BiTNode,*BiTree;int visit(BiTree t);void CreateBiTree(BiTree &T); //生成一个二叉树void PreOrder(BiTree); //递归先序遍历二叉树void InOrder(BiTree); //递归中序遍历二叉树void PostOrder(BiTree); //递归后序遍历二叉树void InOrderTraverse(BiTree T); //非递归中序遍历二叉树void PreOrder_Nonrecursive(BiTree T);//非递归先序遍历二叉树void LeverTraverse(BiTree T);//非递归层序遍历二叉树//主函数void main(){BiTree T;char j;int flag=1;//---------------------程序解说-----------------------printf("本程序实现二叉树的操作。
\n");printf("叶子结点以空格表示。
\n");printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。
\n");//----------------------------------------------------printf("\n");printf("请建立二叉树。
\n");printf("建树将以三个空格后回车结束。
\n");printf("例如:1 2 3 4 5 6 (回车)\n"); CreateBiTree(T); //初始化队列getchar();while(flag){printf("请选择: \n");printf("1.递归先序遍历\n");printf("2.递归中序遍历\n");printf("3.递归后序遍历\n");printf("4.非递归中序遍历\n");printf("5.非递归先序遍历\n");printf("6.非递归层序遍历\n");printf("0.退出程序\n");scanf(" %c",&j);switch(j){case '1':if(T){printf("递归先序遍历二叉树:"); PreOrder(T);printf("\n");}else printf("二叉树为空!\n");break;case '2':if(T){printf("递归中序遍历二叉树:"); InOrder(T);printf("\n");}else printf("二叉树为空!\n");break;case '3':if(T){printf("递归后序遍历二叉树:"); PostOrder(T);printf("\n");}else printf("二叉树为空!\n");break;case '4':if(T){printf("非递归中序遍历二叉树:"); InOrderTraverse(T);printf("\n");}else printf("二叉树为空!\n");break;{printf("非递归先序遍历二叉树:");PreOrder_Nonrecursive(T);printf("\n");}else printf("二叉树为空!\n");break;case '6':if(T){printf("非递归层序遍历二叉树:");LeverTraverse(T);printf("\n");}else printf("二叉树为空!\n");break;default:flag=0;printf("程序运行结束，按任意键退出!\n"); }}}//建立二叉树void CreateBiTree(BiTree &T){char ch;scanf("%c",&ch); //读入一个字符if(ch==' ') T=NULL;else{T=(BiTNode *)malloc(sizeof(BiTNode)); //生成一个新结点 T->data=ch;CreateBiTree(T->lchild); //生成左子树CreateBiTree(T->rchild); //生成右子树}}//先序遍历的递归void PreOrder(BiTree T){if(T){printf("%c ",T->data); //访问结点PreOrder(T->lchild); //遍历左子树PreOrder(T->rchild); //遍历右子树 }}//中序遍历的递归void InOrder(BiTree T){if(T){InOrder(T->lchild); //遍历左子树 printf("%c ",T->data); //访问结点 InOrder(T->rchild); //遍历右子树 }}//后序遍历的递归void PostOrder(BiTree T){if(T){PostOrder(T->lchild); //遍历左子树 PostOrder(T->rchild); //访问结点 printf("%c ",T->data); //遍历右子树 }}//非递归中序遍历void InOrderTraverse(BiTree T) {stack<BiTree> S;BiTree p;S.push(T);//跟指针进栈while(!S.empty()){p=new BiTNode;while((p=S.top())&&p)S.push(p->lchild);//向左走到尽头 S.pop(); //空指针退栈if(!S.empty()){p=S.top();S.pop();cout<<p->data<<" ";S.push(p->rchild);}}}//先序遍历的非递归void PreOrder_Nonrecursive(BiTree T) {stack<BiTree> S;BiTree p;S.push(T);//根指针进栈while(!S.empty())//栈空时结束{while((p=S.top())&&p){cout<<p->data<<" ";S.push(p->lchild);}//向左走到尽头S.pop();//弹出堆栈if(!S.empty()){p=S.top();S.pop();S.push(p->rchild);//向右走一步}}}void LeverTraverse(BiTree T){//非递归层次遍历queue <BiTree> Q;BiTree p;p = T;if(visit(p)==1)Q.push(p);while(!Q.empty()){p = Q.front();Q.pop();if(visit(p->lchild) == 1)Q.push(p->lchild);if(visit(p->rchild) == 1)Q.push(p->rchild); }}int visit(BiTree T) {if(T){printf("%c ",T->data); return 1;}elsereturn 0;}。