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

1、二叉树就是每个结点最多有两个子树的树形存储结构，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被且只被访问一次。程序的流程图如下：程序代码如下：#include<iostream.h>#include<stdlib.h>#include<stdio.h>#include<stdlib.h>typedef char ElemType;struct BTreeNodeElemType data; BTreeNode*left;BTreeNode*right;void InitBTree(BTreeNode*& BT

2、) /初始化二叉树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+;sto

3、p=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) /判断一棵二叉树是否为空，若是则返

4、回ture，否则返回falsereturn BT=NULL;int DepthBTree(BTreeNode*BT)if(BT=NULL)return 0;elseint dep1=DepthBTree(BT->left);int dep2=DepthBTree(BT->right);if(dep1>dep2)return dep1+1;elsereturn dep2+1;bool FindBTree(BTreeNode*BT,ElemType&x) /从二叉树中查找值为x的结点，若存在该结点则由x带回它的完整值if(BT=NULL)return false;else

5、if(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)cout<<BT->data;if(BT->left!=NULL|BT->right!=NULL)cout<<'('PrintBTree(

6、BT->left);if(BT->right!=NULL)cout<<','PrintBTree(BT->right);cout<<')'void ClearBTree(BTreeNode*&BT) /清除二叉树中的所有结点，使之变为一棵空树if(BT!=NULL)ClearBTree(BT->left);ClearBTree(BT->right);delete BT;BT=NULL;void PreOrder(BTreeNode*BT)if(BT!=NULL)cout<<BT->d

7、ata<<' 'PreOrder(BT->left);PreOrder(BT->right);void InOrder(BTreeNode*BT)if(BT!=NULL)InOrder(BT->left);cout<<BT->data<<' 'InOrder(BT->right);void PostOrder(BTreeNode*BT)if(BT!=NULL)PostOrder(BT->left);PostOrder(BT->right);cout<<BT->data

8、<<' '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; /使队首指针指

9、向队首元素p=qfront; /删除队首元素cout<<p->data<<' ' /输出队首元素所指结点的值if(p->left!=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;print

10、f("输入二叉树广义表字符串:n");cin.getline(b,sizeof(b);CreateBTree(bt,b);PrintBTree(bt);cout<<endl;printf("递归算法遍历：n");cout<<"前序遍历为："PreOrder(bt);cout<<endl; cout<<"中序遍历为："InOrder(bt);cout<<endl;cout<<"后序遍历为："PostOrder(bt);cout<<endl;printf("非递归算法遍历：n");cout<<"按层遍历为："LevelOrder(bt);cout<<endl;ElemType x;printf("请输入待查字符:");scanf("%c",&x);if(FindBTree(bt,x)printf("查找字