(完整word版)二叉树的遍历源代码(C语言).doc

二叉树就是每个结点最多有两个子树的树形存储结构，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被且只被访问一次。程序的流程图如下：程序代码如下：#include<iostream.h>#include<stdlib.h>#include<stdio.h>#include<stdlib.h>typedefcharElemType;structBTreeNode{ElemTypedata;BTreeNode*left;BTreeNode*right;};voidInitBTree(BTreeNode*&BT){//初始化二叉树BT=NULL;}voidCreateBTree(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的值\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=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(BTreeNode*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(FindBTree(BT->left,x))returntrue;if(FindBTree(BT->right,x))returntrue;returnfalse;}}}voidPrintBTree(BTreeNode*BT){//按照树的一种表示方法输出一棵二叉树if(BT!=NULL){cout<<BT->data;if(BT->left!=NULL||BT->right!=NULL){cout<<'(';PrintBTree(BT->left);if(BT->right!=NULL)cout<<',';PrintBTree(BT->right);cout<<')';}}}voidClearBTree(BTreeNode*&BT){//清除二叉树中的所有结点，使之变为一棵空树if(BT!=NULL){ClearBTree(BT->left);ClearBTree(BT->right);deleteBT;BT=NULL