《二叉树的遍历源代码(C语言)》由会员分享,可在线阅读,更多相关《二叉树的遍历源代码(C语言)(6页珍藏版)》请在金锄头文库上搜索。
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;default:p=new BTre
3、eNode;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)ret
4、urn 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 PostOrder(B
6、TreeNode*BT)if(BT!=NULL)PostOrder(BT-left);PostOrder(BT-right);coutdatadataleft!=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,size
7、of(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,if(FindBTree(bt,x)printf(查找字符%c 成功,x);elseprintf(查找字符%c 失败,x);printf(n);cout 树的深度为:;coutDepthBTree(bt)endl;ClearBTree(bt);程序的运行结果如右图: