数据结构c语言版 二叉树的顺序存储表示和实现

《数据结构c语言版 二叉树的顺序存储表示和实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、/*数据结构C语言版二叉树的顺序存储表示和实现P126编译环境：Dev-C++4.9.9.2日期：2011年2月13日*/#includetypedefcharTElemType;//二叉树的顺序存储表示#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点typedefstruct{intlevel,//结点的层order;//本层序号(按满二叉树计算)}position

2、;typedefintQElemType;//队列的顺序存储结构(可用于循环队列和非循环队列)#defineMAXQSIZE5//最大队列长度(对于循环队列，最大队列长度要减1)typedefstruct{QElemType*base;//初始化的动态分配存储空间相当于一个数组intfront;//头指针,若队列不空,指向队列头元素，相当于一个数组下标intrear;//尾指针,若队列不空,指向队列尾元素的下一个位置//相当于一个数组下标}SqQueue;#defineClearBiTreeInitBiT

3、ree//在顺序存储结构中，两函数完全一样TElemTypeNil='';//设空为字符型的空格符//构造空二叉树T。因为T是固定数组，不会改变，故不需要&intInitBiTree(SqBiTreeT){inti;for(i=0;i

4、(SqBiTreeT){inti=0,l;chars[MAX_TREE_SIZE];printf("请按层序输入结点的值(字符)，空格表示空结点，结点数≤%d:",MAX_TREE_SIZE);printf("例如：abcefgh");gets(s);//输入字符串l=strlen(s);//求字符串的长度for(;i

5、]==Nil&&T[i]!=Nil){printf("出现无双亲的非根结点%c",T[i]);exit(0);}}for(i=l;i

6、(i=MAX_TREE_SIZE-1;i>=0;i--)//找到最后一个结点if(T[i]!=Nil)break;i++;//为了便于计算doj++;while(i>=pow(2,j));//i>pow(2,depth-1)&&i<=pow(2,depth)returnj;//j=depth;}//当T不空,用e返回T的根,返回1;否则返回0,e无定义intRoot(SqBiTreeT,TElemType*e){if(BiTreeEmpty(T))//T空return0;else{*e=T[0];retu

7、rn1;}}//返回处于位置e(层,本层序号)的结点的值TElemTypeValue(SqBiTreeT,positione){//将层、本层序号转为矩阵的序号returnT[((int)pow(2,e.level-1)-1)+(e.order-1)];//((int)pow(2,e.level-1)-1)为该e.level的结点个数，//(e.order-1)为本层的位置}//给处于位置e(层,本层序号)的结点赋新值valueintAssign(SqBiTreeT,positione,TElemType

8、value){//将层、本层序号转为矩阵的序号inti=(int)pow(2,e.level-1)+e.order-2;if(value!=Nil&&T[(i+1)/2-1]==Nil)//叶子非空值但双亲为空return0;elseif(value==Nil&&(T[i*2+1]!=Nil

9、

10、T[i*2+2]!=Nil))//双亲空值但有叶子（不空）return0;T[i]=value;return1;}//若e是T的非根结