《二叉树的遍历源代码(C语言)(共6页).docx》由会员分享，可在线阅读，更多相关《二叉树的遍历源代码(C语言)(共6页).docx（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上二叉树就是每个结点最多有两个子树的树形存储结构，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被且只被访问一次。程序的流程图如下：程序代码如下：#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)
2、 /根据广义表表示的二叉树建立对应的存储结构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;defau
3、lt: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(d
4、ep1dep2)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) /按照树的
5、一种表示方法输出一棵二叉树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
6、 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
7、=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(输入二叉树广义表字符串:
8、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(FindBTree(bt,x)printf(查找字符%c成功,x);elseprintf(查找字符%c失败,x);printf(n);cout 树的深度为:;coutDepthBTree(bt)endl;ClearBTree(bt);程序的运行结果如右图：专心-专注-专业