二叉树（C语言实现）——顺序存储结构

/*二叉树顺序存储结构一般仅适合于存储完全二叉树*/#include<stdio.h>#include<stdlib.h>#include<math.h>#include<stdbool.h>#define MaxSize 100typedef char DataType;typedef struct{DataType data[MaxSize];//存储树结点的数组 int BiTreeNum;//二叉树的结点个数 }SqBiTree;void Init_BiTree(SqBiTree * T); //初始化 void Creat_BiTree(SqBiTree * T, int n); //创建树 DataType Root_BiTree(SqBiTree * T); //获取根结点 int Count_BiTree(SqBiTree * T); //获取树的结点数 int Depth_BiTree(SqBiTree * T); //获取树的深度 void Print_BiTree(SqBiTree * T); //打印二叉树的结点void PreOrder_Traverse(SqBiTree * T,int n); //先序遍历二叉树 void InOrder_Traverse(SqBiTree * T, int n); //中序遍历二叉树 void PostOrder_Traverse(SqBiTree * T, int n);//后序遍历二叉树void Level_Traverse(SqBiTree * T, int n); //层序遍历二叉树 bool Destroy_BiTree(SqBiTree * T); //销毁二叉树 int main(){SqBiTree T;Init_BiTree(&T);printf("请输入根结点(输入#表示该结点为空)："); Creat_BiTree(&T,1);printf("打印二叉树:");Print_BiTree(&T);printf("\n");printf("根结点:%c\n",Root_BiTree(&T));printf("结点数:%d\n", Count_BiTree(&T));printf("深度:%d\n",Depth_BiTree(&T));printf("打印二叉树:");Print_BiTree(&T);printf("\n");printf("先序遍历：");PreOrder_Traverse(&T,1);printf("\n");printf("中序遍历：");InOrder_Traverse(&T,1);printf("\n");printf("后序遍历：");PostOrder_Traverse(&T,1);printf("\n");printf("层序遍历：");Level_Traverse(&T, 1);printf("\n");if(Destroy_BiTree(&T))printf("销毁成功！\n");elseprintf("销毁失败！\n");printf("打印二叉树:");Print_BiTree(&T);printf("\n");return 0;} void Init_BiTree(SqBiTree * T){int i;for(i=0; i<MaxSize; ++i) // 清除所用内存空间的杂乱数据 {T->data[i] = '\0';}T->BiTreeNum = 0; return; }void Creat_BiTree(SqBiTree* T, int n){char ch;fflush(stdin);scanf("%c",&ch);if(ch == '#'){return;}else{T->data[n] = ch;T->BiTreeNum++;printf("%c的左子树：",ch);Creat_BiTree(T, 2*n);printf("%c的右子树：",ch);Creat_BiTree(T,(2*n+1));}}DataType Root_BiTree(SqBiTree * T){return T->data[1];}int Count_BiTree(SqBiTree * T){if(T->BiTreeNum == 0)return 0;elsereturn T->BiTreeNum;}int Depth_BiTree(SqBiTree * T){if(!T)return 0;int k;pow(2,k) - 1 == T->BiTreeNum;return k;}void Print_BiTree(SqBiTree * T){int i;for(i=1; i<=T->BiTreeNum; ++i){if(T->data[i] != '\0') printf("%3c",T->data[i]);}printf("\n");}void PreOrder_Traverse(SqBiTree * T, int n){if(T->data[n] == '\0')return;else{printf("%3c",T->data[n]);PreOrder_Traverse(T, 2*n);PreOrder_Traverse(T, (2*n+1));}} void InOrder_Traverse(SqBiTree * T, int n){if(T->data[n] == '\0')return;else{InOrder_Traverse(T, 2*n);printf("%3c",T->data[n]);InOrder_Traverse(T, (2*n+1));}}void PostOrder_Traverse(SqBiTree * T, int n){if(T->data[n] == '\0')return;else{PostOrder_Traverse(T, 2*n);PostOrder_Traverse(T, (2*n+1));printf("%3c",T->data[n]);}}void Level_Traverse(SqBiTree * T, int n){int i;for(i=n; i<=T->BiTreeNum; ++i)printf("%3c",T->data[i]);}bool Destroy_BiTree(SqBiTree * T){T->BiTreeNum = 0;return true;}