1200字范文 > 数据结构(C语言版)——二叉树的顺序存储结构(代码版)

数据结构(C语言版)——二叉树的顺序存储结构(代码版)

时间：2024-05-08 11:50:18

一、代码

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define OK 1#define ERROR 0#define MAXSIZE 30typedef int Status;typedef struct biTree{char data[MAXSIZE];}BITREE,*BITREEPOINTER;int printMenu(void); Status PleaseInit(void);Status initBitree(BITREEPOINTER* T);Status createBiTree(BITREEPOINTER* T,int SIZE);Status floorTraversing(const BITREEPOINTER* T);Status returnRootNode(const BITREEPOINTER* T);Status isEmpty(const BITREEPOINTER* T);Status biTreeDepth(const BITREEPOINTER* T);Status clearBiTree(BITREEPOINTER* T);Status destoryBiTree(BITREEPOINTER* T);Status searchFatherNode(const BITREEPOINTER* T);Status searchBorther(const BITREEPOINTER* T);int main(int argc, char *argv[]) {int menuChoice;BITREEPOINTER biTreePointer;//声明指向二叉树结构的指针变量 biTreePointer=NULL;//变量设为NULLwhile(menuChoice=printMenu()){switch(menuChoice){case 1:initBitree(&biTreePointer);break;case 2:destoryBiTree(&biTreePointer);break;case 3:createBiTree(&biTreePointer,MAXSIZE);break;case 4:clearBiTree(&biTreePointer);break;case 5:biTreeDepth(&biTreePointer);break;case 6:searchFatherNode(&biTreePointer);break;case 7:searchBorther(&biTreePointer);break;case 8:isEmpty(&biTreePointer);break;case 9:floorTraversing(&biTreePointer);break;case 10:returnRootNode(&biTreePointer);break;}}return 0;}//打印菜单int printMenu(void){int choice;printf("****************二叉树的顺序存储结构练习******************\n");printf("1:初始化二叉树\n");printf("2:销毁二叉树\n");printf("3:创建二叉树\n");printf("4:清空二叉树\n");printf("5:返回二叉树的深度\n");printf("6:寻找元素父节点\n");printf("7:查找兄弟元素\n"); printf("8:判断是否为空树\n");printf("9:层序遍历二叉树\n");printf("10:返回根结点\n");printf("11:前序遍历\n");printf("按下0退出程序\n"); printf("*******************************************\n");printf("请选择:");scanf("%d",&choice);return choice;}//1:初始化二叉树Status initBitree(BITREEPOINTER* T){system("cls");//清屏printf("当前选的为--1:初始化二叉树--\n");if((*T)!=NULL){//检查(*T)是否初始化过 printf("请勿重复初始化!\n");return ERROR;}*T=(BITREEPOINTER)malloc(sizeof(BITREE));//申请空间 if((*T)==NULL){//申请空间失败时 printf("初始化失败!\n");return ERROR;}(*T)->data[0]=0;//表示没有二叉树结点 printf("初始化成功!\n");return OK;}//2:销毁二叉树Status destoryBiTree(BITREEPOINTER* T){system("cls");//清屏printf("当前选的为--2:销毁二叉树--\n");if((*T)==NULL){//检查(*T)是否初始化过 PleaseInit();return ERROR;}char inputValue;printf("是否要清空二叉树?(Y/N)");if(scanf("%c",&inputValue)==0){printf("输入有误\n");fflush(stdin);return ERROR;}if(inputValue=='Y'||inputValue=='y'){free((*T));*T=NULL;printf("销毁成功!\n");return OK;}if(inputValue=='N'||inputValue=='n'){return OK;}return OK;}//3:创建二叉树Status createBiTree(BITREEPOINTER* T,int SIZE){system("cls");//清屏printf("当前选的为--3:创建二叉树--\n");if((*T)==NULL){//检查(*T)是否初始化过 PleaseInit();return ERROR;}if((*T)->data[0]!=0){printf("请先清空二叉树再来创建新的二叉树吧\n");return ERROR;}char getChar[SIZE];int inputLength,i;printf("'#'表示空结点,请输入你要初始化的二叉树元素字符串(注意范围(1-%d)):",SIZE-2);fflush(stdin);//清除缓冲区的换行符 fgets(getChar,SIZE,stdin);if(getChar[strlen(getChar)-1]!='\n'){//判断是否超过范围 printf("输入超过范围!\n");fflush(stdin);return ERROR;}getChar[strlen(getChar)-1]='\0'; //如果没有超过范围,去掉其中的换行符 inputLength=strlen(getChar);(*T)->data[0]=inputLength;//存储二叉树链表的元素个数 for(i=1;i<=inputLength;i++){(*T)->data[i]=getChar[i-1]; }fflush(stdin);//清除缓冲区 printf("创建成功!\n");return OK;}//4:清空二叉树Status clearBiTree(BITREEPOINTER* T){system("cls");//清屏printf("当前选的为--4:清空二叉树--\n");if((*T)==NULL){//检查(*T)是否初始化过 PleaseInit();return ERROR;}if((*T)->data[0]==0){printf("当前二叉树已经为空了\n");return ERROR;}char inputValue;printf("是否要清空二叉树?(Y/N)");if(scanf("%c",&inputValue)==0){printf("输入有误\n");fflush(stdin);return ERROR;}if(inputValue=='Y'||inputValue=='y'){(*T)->data[0]=0;printf("清空成功!\n");return OK;}if(inputValue=='N'||inputValue=='n'){return OK;}return OK;}//5:返回二叉树的深度Status biTreeDepth(const BITREEPOINTER* T){system("cls");//清屏printf("当前选的为--5:返回二叉树的深度--\n");if((*T)==NULL){//检查(*T)是否初始化过 PleaseInit();return ERROR;}if((*T)->data[0]==0){printf("请先创建元素吧\n");return ERROR;}double depthPre;int depth;depthPre=log10((*T)->data[0])/log10(2);depth=(int)ceil(depthPre);if(depth==0)depth=1;printf("当前二叉树的深度为:%d\n",depth);return OK;}//6:寻找元素父节点Status searchFatherNode(const BITREEPOINTER* T){system("cls");//清屏printf("当前选的为--6:寻找元素父节点--\n");if((*T)==NULL){//检查(*T)是否初始化过 PleaseInit();return ERROR;}if((*T)->data[0]==0){printf("请先创建元素吧\n");return ERROR;}char value;int i;printf("请输入你要寻找父元素的元素值:");scanf("%c",&value);fflush(stdin);for(i=1;i<=(*T)->data[0];i++){if(value==(*T)->data[i]&&i!=1){printf("元素%c的父元素为:%c\n",(*T)->data[i],(*T)->data[(int)floor(i/2)]);return OK;}if(value==(*T)->data[i]&&i==1){printf("根元素无父元素!\n");return OK;}}printf("你输入的元素不在该二叉树中\n");return OK;}//7:查找兄弟元素Status searchBorther(const BITREEPOINTER* T){system("cls");//清屏printf("当前选的为--7:查找兄弟元素--\n");if((*T)==NULL){//检查(*T)是否初始化过 PleaseInit();return ERROR;}if((*T)->data[0]==0){printf("请先创建元素吧\n");return ERROR;}char value;int i;printf("请输入你要寻找兄弟元素的元素值:");scanf("%c",&value);fflush(stdin);for(i=1;i<=(*T)->data[0];i++){if(value==(*T)->data[i]&&i!=1){int fatherIndex=(int)floor(i/2);if(2*fatherIndex==i&&(2*fatherIndex+1)<(*T)->data[0]&&(*T)->data[2*fatherIndex+1]!='#'){printf("元素%c的兄弟元素为:%c\n",(*T)->data[i],(*T)->data[2*fatherIndex+1]);return OK;}if((2*fatherIndex+1)==i&&(*T)->data[2*fatherIndex]!='#'){printf("元素%c的兄弟元素为:%c\n",(*T)->data[i],(*T)->data[2*fatherIndex]);return OK;}if(2*fatherIndex==i&&(2*fatherIndex+1)>(*T)->data[0]||(*T)->data[2*fatherIndex]=='#'||(*T)->data[2*fatherIndex+1]=='#'){printf("元素%c无兄弟元素\n",(*T)->data[i]);return OK;}}if(value==(*T)->data[i]&&i==1){printf("根元素无兄弟元素!\n");return OK;}}printf("你输入的元素不在该二叉树中\n");return OK;}//8:判断是否为空树Status isEmpty(const BITREEPOINTER* T){system("cls");//清屏printf("当前选的为--8:判断是否为空树--\n");if((*T)==NULL){//检查(*T)是否初始化过 PleaseInit();return ERROR;}if((*T)->data[0]==0){printf("当前二叉树为空\n");return ERROR;}printf("当前二叉树为不空\n");return OK;}//9:层序遍历二叉树Status floorTraversing(const BITREEPOINTER* T){system("cls");//清屏printf("当前选的为--9:层序遍历二叉树--\n");if((*T)==NULL){//检查(*T)是否初始化过 PleaseInit();return ERROR;}if((*T)->data[0]==0){printf("请先创建元素吧\n");return ERROR;}int i,length;length=(*T)->data[0];printf("层序遍历结果为:");for(i=1;i<=length;i++){if((*T)->data[i]=='#')continue;printf("%2c",(*T)->data[i]);}printf("\n");return OK; }//10:返回根结点Status returnRootNode(const BITREEPOINTER* T){system("cls");//清屏printf("当前选的为--10:返回根结点--\n");if((*T)==NULL){//检查(*T)是否初始化过 PleaseInit();return ERROR;}if((*T)->data[0]==0){printf("请先创建元素吧\n");return ERROR;}printf("当前二叉树的根节点元素为:%c\n",(*T)->data[1]);return OK;}//请先初始化样式Status PleaseInit(void){printf("**************\n");printf("*请先初始化 *\n");printf("**************\n\n");}

二、代码中重要的函数或语句

(一)、

typedef struct biTree{char data[MAXSIZE];}BITREE,*BITREEPOINTER;

上面定义了一个用于存取二叉树顺序结构的数组

(二)、创建二叉树

char getChar[SIZE];int inputLength,i;printf("'#'表示空结点,请输入你要初始化的二叉树元素字符串(注意范围(1-%d)):",SIZE-2);fflush(stdin);//清除缓冲区的换行符 fgets(getChar,SIZE,stdin);if(getChar[strlen(getChar)-1]!='\n'){//判断是否超过范围 printf("输入超过范围!\n");fflush(stdin);return ERROR;}getChar[strlen(getChar)-1]='\0'; //如果没有超过范围,去掉其中的换行符 inputLength=strlen(getChar);(*T)->data[0]=inputLength;//存储二叉树链表的元素个数 for(i=1;i<=inputLength;i++){(*T)->data[i]=getChar[i-1]; }fflush(stdin);//清除缓冲区 printf("创建成功!\n");

在创建二叉树的时候，要注意fgets函数的特性，它会在输入一行结束后加上\n\0，在一个超过范围的输入时它会在一行中加入\0不加\n，所以你可以通过该特性判断输入的元素是否超过范围。

(*T)->data[0]在0的位置存入的是输入字符串的大小

(三)、返回二叉树的深度

int depth;depthPre=log10((*T)->data[0])/log10(2);depth=(int)ceil(depthPre);

在计算二叉树深度的时候，选用了log函数进行计算。计算的结果再向上取整，最后转换为int类型。因为二叉树的特殊性，在0号位置存储着二叉树元素的最大值。所以计算树的深度就可以log2((*T)->data[0])来计算。

注:#符号代表空元素(空树)