二叉树的遍历源代码(C语言)

二叉树就是每个结点最多有两个子树的树形存储结构，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被且只被访问一次。程序的流程图如下：程序代码如下：#include#include#include#includetypedef char ElemType;struct BTreeNodeElemType data; BTreeNode*left;BTreeNode*right;void InitBTree(BTreeNode*& BT) /初始化二叉树BT=NULL;void CreateBTree(BTreeNode*& BT,char*a) /根据广义表表示的二叉树建立对应的存储结构const int MaxSize=10;BTreeNode*sMaxSize;int top=-1;BT=NULL;BTreeNode*p;int k;int i=0;while(ai)switch(ai)case :break;case (:if(top=MaxSize-1)printf(栈的空间太小，请增加MaxSize的值n);exit(1);top+;stop=p;k=1;break;case ):if(top=-1)printf(二叉树广义表字符串错！n);exit(1);top-;break;case ,:k=2;break;default:p=new BTreeNode;p-data=ai;p-left=p-right=NULL;if(BT=NULL)BT=p;elseif(k=1)stop-left=p;elsestop-right=p;i+;bool EmptyBTree(BTreeNode*BT) /判断一棵二叉树是否为空，若是则返回ture，否则返回falsereturn BT=NULL;int DepthBTree(BTreeNode*BT)if(BT=NULL)return 0;elseint dep1=DepthBTree(BT-left);int dep2=DepthBTree(BT-right);if(dep1dep2)return dep1+1;elsereturn dep2+1;bool FindBTree(BTreeNode*BT,ElemType&x) /从二叉树中查找值为x的结点，若存在该结点则由x带回它的完整值if(BT=NULL)return false;elseif(BT-data=x)x=BT-data;return true;elseif(FindBTree(BT-left,x)return true; if(FindBTree(BT-right,x) return true; return false;void PrintBTree(BTreeNode*BT) /按照树的一种表示方法输出一棵二叉树if(BT!=NULL)coutdata;if(BT-left!=NULL|BT-right!=NULL)coutleft);if(BT-right!=NULL)coutright);coutleft);ClearBTree(BT-right);delete BT;BT=NULL;void PreOrder(BTreeNode*BT)if(BT!=NULL)coutdataleft);PreOrder(BT-right);void InOrder(BTreeNode*BT)if(BT!=NULL)InOrder(BT-left);coutdataright);void PostOrder(BTreeNode*BT)if(BT!=NULL)PostOrder(BT-left);PostOrder(BT-right);coutdata ;void LevelOrder(BTreeNode*BT) /按层遍历由BT指针所指向的二叉树const int MaxSize=30; /定义用于存储队列的数组长度BTreeNode*qMaxSize; /定义队列所使用的数组空间int front=0, rear=0; /定义队首指针和队尾指针，初始为空队BTreeNode*p;if(BT!=NULL) /将树根指针进队rear=(rear+1)%MaxSize;qrear=BT;while(front!=rear) /当队列非空时执行循环front=(front+1)%MaxSize; /使队首指针指向队首元素p=qfront; /删除队首元素coutdataleft!=NULL)rear=(rear+1)%MaxSize;qrear=p-left;if(p-right!=NULL)rear=(rear+1)%MaxSize;qrear=p-right; /while end/void main()system(color 75); /设置颜色以美观BTreeNode*bt;InitBTree(bt);char b999;printf(输入二叉树广义表字符串:n);cin.getline(b,sizeof(b);CreateBTree(bt,b);PrintBTree(bt);coutendl;printf(递归算法遍历：n);cout前序遍历为：;PreOrder(bt);coutendl; cout中序遍历为：;InOrder(bt);coutendl;cout后序遍历为：;PostOrder(bt);coutendl;printf(非递归算法遍历：n);cout按层遍历为：;LevelOrder(bt);coutendl;ElemType x;printf(请输入待查字符:);scanf(%c,&x);if(Find