二叉树遍历所有代码

#includestdio.h#includeiostream#includequeue#includestack#includemalloc.h#defineSIZE100usingnamespacestd;typedefstructBiTNode//定义二叉树节点结构{chardata;//数据域structBiTNode*lchild,*rchild;//左右孩子指针域}BiTNode,*BiTree;intvisit(BiTreet);voidCreateBiTree(BiTree&T);//生成一个二叉树voidPreOrder(BiTree);//递归先序遍历二叉树voidInOrder(BiTree);//递归中序遍历二叉树voidPostOrder(BiTree);//递归后序遍历二叉树voidInOrderTraverse(BiTreeT);//非递归中序遍历二叉树voidPreOrder_Nonrecursive(BiTreeT);//非递归先序遍历二叉树voidLeverTraverse(BiTreeT);//非递归层序遍历二叉树//主函数voidmain(){BiTreeT;charj;intflag=1;//---------------------程序解说-----------------------printf(本程序实现二叉树的操作。\n);printf(叶子结点以空格表示。\n);printf(可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。\n);//----------------------------------------------------printf(\n);printf(请建立二叉树。\n);printf(建树将以三个空格后回车结束。\n);printf(例如:123456(回车)\n);CreateBiTree(T);//初始化队列getchar();while(flag){printf(\n);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);}elseprintf(二叉树为空!\n);break;case'2':if(T){printf(递归中序遍历二叉树:);InOrder(T);printf(\n);}elseprintf(二叉树为空!\n);break;case'3':if(T){printf(递归后序遍历二叉树:);PostOrder(T);printf(\n);}elseprintf(二叉树为空!\n);break;case'4':if(T){printf(非递归中序遍历二叉树:);InOrderTraverse(T);printf(\n);}elseprintf(二叉树为空!\n);break;case'5':if(T){printf(非递归先序遍历二叉树:);PreOrder_Nonrecursive(T);printf(\n);}elseprintf(二叉树为空!\n);break;case'6':if(T){printf(非递归层序遍历二叉树:);LeverTraverse(T);printf(\n);}elseprintf(二叉树为空!\n);break;default:flag=0;printf(程序运行结束，按任意键退出!\n);}}}//建立二叉树voidCreateBiTree(BiTree&T){charch;scanf(%c,&ch);//读入一个字符if(ch=='')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));//生成一个新结点T-data=ch;CreateBiTree(T-lchild);//生成左子树CreateBiTree(T-rchild);//生成右子树}}//先序遍历的递归voidPreOrder(BiTreeT){if(T){printf(%c,T-data);//访问结点PreOrder(T-lchild);//遍历左子树PreOrder(T-rchild);//遍历右子树}}//中序遍历的递归voidInOrder(BiTreeT){if(T){InOrder(T-lchild);//遍历左子树printf(%c,T-data);//访问结点InOrder(T-rchild);//遍历右子树}}//后序遍历的递归voidPostOrder(BiTreeT){if(T){PostOrder(T-lchild);//遍历左子树PostOrder(T-rchild);//访问结点printf(%c,T-data);//遍历右子树}}//非递归中序遍历voidInOrderTraverse(BiTreeT){stackBiTreeS;BiTreep;S.push(T);//跟指针进栈while(!S.empty()){p=newBiTNode;while((p=S.top())&&p)S.push(p-lchild);//向左走到尽头S.pop();//空指针退栈if(!S.empty()){p=S.top();S.pop();coutp-data;S.push(p-rchild);}}}//先序遍历的非递归voidPreOrder_Nonrecursive(BiTreeT){stackBiTreeS;BiTreep;S.push(T);//根指针进栈while(!S.empty())//栈空时结束{while((p=S.top())&&p){coutp-data;S.push(p-lchild);}//向左走到尽头S.pop();//弹出堆栈if(!S.empty()){p=S.top();S.pop();S.push(p-rchild);//向右走一步}}}voidLeverTraverse(BiTreeT){//非递归层次遍历queueBiTreeQ;BiTreep;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);}}intvisit(BiTreeT){if(T){printf(%c,T-data);return1;}elsereturn0;}