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

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

二叉树就是每个结点最多有两个子树的树形存储结构，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被且只被访问一次。程序的流程图如下：程序代码如下：#include#include#include#includetypedef char ElemType;struct BTreeNode{ElemType data; BTreeNode*left;BTreeNode*right;};void InitBTree(BTreeNode*& BT){ //初始化二叉树BT=NULL;}void CreateBTree(BTreeNode*& BT,char*a){ //根据广义表表示的二叉树建立对应的存储结构const int MaxSize=10;BTreeNode*s[MaxSize];int top=-1;BT=NULL;BTreeNode*p;int k;int i=0;while(a[i]){switch(a[i]){case ' ':break;case '(':if(top==MaxSize-1){printf("栈的空间太小，请增加MaxSize的值n");exit(1);}top++;s[top]=p;k=1;break;case ')':if(top==-1){printf("二叉树广义表字符串错！n");exit(1);}top--;break;case ',':k=2;break;default:p=new BTreeNode;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++;}}bool EmptyBTree(BTreeNode*BT){ //判断一棵二叉树是否为空，若是则返回ture，否则返回falsereturn BT==NULL;}int DepthBTree(BTreeNode*BT){if(BT==NULL)return 0;else{int 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{if(BT->data==x){x=BT->data;return true;}else{if(FindBTree(BT->left,x))return true; if(FindBTree(BT->right,x)) return true; return false;}}}void PrintBTree(BTreeNode*BT){ //按照树的一种表示方法输出一棵二叉树if(BT!=NULL){cout<data;if(BT->left!=NULL||BT->right!=NULL){cout<left);if(BT->right!=NULL)cout<right);cout<left);ClearBTree(BT->right);delete BT;BT=NULL;}}void PreOrder(BTreeNode*BT){if(BT!=NULL){cout<data<left);PreOrder(BT->right);}}void InOrder(BTreeNode*BT){if(BT!=NULL){InOrder(BT->left);cout<data<right);}}void PostOrder(BTreeNode*BT){if(BT!=NULL){PostOrder(BT->left);PostOrder(BT->right);cout<data<