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

《二叉树的遍历源代码(C语言).docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二叉树就是每个结点最多有两个子树的树形存储结构，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被且只被访问一次。程序的流程图如下：程序代码如下：#include#include#include#includetypedefcharElemType;structBTreeNode{ElemTypedata;BTreeNode*left;BTreeNode*right;};voidInitBTree(BTreeNode*&BT){//初始化二叉树BT=NULL;}void

2、CreateBTree(BTreeNode*&BT,char*a){//根据广义表表示的二叉树建立对应的存储结构constintMaxSize=10;BTreeNode*s[MaxSize];inttop=-1;BT=NULL;BTreeNode*p;intk;inti=0;while(a[i]){switch(a[i]){case'':break;case'(':if(top==MaxSize-1){printf("栈的空间太小，请增加MaxSize的值");exit(1);}top++;s[top]=p;k=1;break;case')':if(top==-1){pr

3、intf("二叉树广义表字符串错！");exit(1);}top--;break;case',':k=2;break;default:p=newBTreeNode;p->data=a[i];p->left=p->right=NULL;if(BT==NULL)BT=p;else{if(k==1)s[top]->left=p;elses[top]->right=p;}}i++;}}boolEmptyBTree(BTreeNode*BT){//判断一棵二叉树是否为空，若是则返回ture，否则返回falsereturnBT==NULL;}intDepthBTree(BTreeNo

4、de*BT){if(BT==NULL)return0;else{intdep1=DepthBTree(BT->left);intdep2=DepthBTree(BT->right);if(dep1>dep2)returndep1+1;elsereturndep2+1;}}boolFindBTree(BTreeNode*BT,ElemType&x){//从二叉树中查找值为x的结点，若存在该结点则由x带回它的完整值if(BT==NULL)returnfalse;else{if(BT->data==x){x=BT->data;returntrue;}else{if(FindBTre

5、e(BT->left,x))returntrue;if(FindBTree(BT->right,x))returntrue;returnfalse;}}}voidPrintBTree(BTreeNode*BT){//按照树的一种表示方法输出一棵二叉树if(BT!=NULL){cout<data;if(BT->left!=NULL

6、

7、BT->right!=NULL){cout<<'(';PrintBTree(BT->left);if(BT->right!=NULL)cout<<',';PrintBTree(BT->right);cout<<')';}}}voidCle

8、arBTree(BTreeNode*&BT){//清除二叉树中的所有结点，使之变为一棵空树if(BT!=NULL){ClearBTree(BT->left);ClearBTree(BT->right);deleteBT;BT=NULL;}}voidPreOrder(BTreeNode*BT){if(BT!=NULL){cout<data<<'';PreOrder(BT->left);PreOrder(BT->right);}}voidInOrder(BTreeNode*BT){if(BT!=NULL){InOrder(BT->left);cout<data

9、<<'';InOrder(BT->right);}}voidPostOrder(BTreeNode*BT){if(BT!=NULL){PostOrder(BT->left);PostOrder(BT->right);cout<data<<'';}}voidLevelOrder(BTreeNode*BT){//按层遍历由BT指针所指向的二叉树constintMaxSize=30;//定义用于存储队列的数组长度BTreeNode*q[MaxSize];//定义队列所使用的数组空间intfront=