数据结构C语言版 二叉树的顺序存储表示和实现.doc
数据结构C语言版 二叉树的顺序存储表示和实现.txt丶喜欢的歌，静静的听，喜欢的人，远远的看我笑了当初你不挺傲的吗现在您这是又玩哪出呢？/*数据结构C语言版 二叉树的顺序存储表示和实现P126 编译环境：Dev-C+ 4.9.9.2日期：2011年2月13日 */#include <stdio.h>typedef char TElemType;/ 二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点 typedef structint level,/结点的层order;/本层序号(按满二叉树计算)position;typedef int QElemType;/ 队列的顺序存储结构(可用于循环队列和非循环队列) #define MAXQSIZE 5 / 最大队列长度(对于循环队列，最大队列长度要减1) typedef structQElemType *base; / 初始化的动态分配存储空间 相当于一个数组 int front; / 头指针,若队列不空,指向队列头元素，相当于一个数组下标int rear; / 尾指针,若队列不空,指向队列尾元素的下一个位置/ 相当于一个数组下标SqQueue;#define ClearBiTree InitBiTree / 在顺序存储结构中，两函数完全一样 TElemType Nil = ' ' / 设空为字符型的空格符 / 构造空二叉树T。因为T是固定数组，不会改变，故不需要& int InitBiTree(SqBiTree T)int i;for(i=0;i<MAX_TREE_SIZE;i+)Ti=Nil; / 初值为空 return 1;void DestroyBiTree() / 由于SqBiTree是定长类型,无法销毁 / 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T int CreateBiTree(SqBiTree T)int i = 0, l;char sMAX_TREE_SIZE;printf("请按层序输入结点的值(字符)，空格表示空结点，结点数%d:n",MAX_TREE_SIZE);printf("例如：abcefghn");gets(s);/ 输入字符串 l = strlen(s);/ 求字符串的长度 for(;i<l;i+)/ 将字符串赋值给T Ti=si;/ 此结点(不空)无双亲且不是根,T(i+1)/2-1 = Nil表示Ti无双亲 if(i!=0 && T(i+1)/2-1 = Nil && Ti != Nil)printf("出现无双亲的非根结点%cn",Ti);exit(0);for(i=l;i<MAX_TREE_SIZE;i+) / 将空赋值给T的后面的结点 Ti=Nil;return 1;/ 若T为空二叉树,则返回1,否则0 int BiTreeEmpty(SqBiTree T)if(T0=Nil) / 根结点为空,则树空 return 1;elsereturn 0;/ 返回T的深度int BiTreeDepth(SqBiTree T)int i,j=-1;for(i=MAX_TREE_SIZE-1;i>=0;i-) / 找到最后一个结点 if(Ti != Nil)break;i+; / 为了便于计算 doj+;while(i>=pow(2,j);/i > pow(2, depth-1) && i <= pow(2, depth)return j;/j = depth;/ 当T不空,用e返回T的根,返回1;否则返回0,e无定义 int Root(SqBiTree T,TElemType *e)if(BiTreeEmpty(T) / T空 return 0;else*e=T0;return 1;/ 返回处于位置e(层,本层序号)的结点的值 TElemType Value(SqBiTree T,position e)/ 将层、本层序号转为矩阵的序号return T(int)pow(2,e.level-1) - 1) + (e.order - 1); /(int)pow(2,e.level-1) - 1)为该e.level的结点个数，/ (e.order - 1)为本层的位置/ 给处于位置e(层,本层序号)的结点赋新值value int Assign(SqBiTree T,position e,TElemType value)/ 将层、本层序号转为矩阵的序号 int i = (int)pow(2,e.level-1) + e.order - 2;if(value != Nil && T(i+1)/2-1 = Nil) / 叶子非空值但双亲为空 return 0;else if(value = Nil && (Ti*2+1 != Nil | Ti*2+2 != Nil)/ 双亲空值但有叶子（不空） return 0;Ti=value;return 1;/ 若e是T的非根结点,则返回它的双亲,否则返回空TElemType Parent(SqBiTree T,TElemType e) int i;if(T0=Nil) / 空树 return Nil;for(i=1;i<=MAX_TREE_SIZE-1;i+)if(Ti=e) / 找到e return T(i+1)/2-1;return Nil; / 没找到e / 返回e的左孩子。若e无左孩子,则返回空TElemType LeftChild(SqBiTree T,TElemType e)int i;if(T0=Nil) / 空树 return Nil;for(i=0;i<=MAX_TREE_SIZE-1;i+)if(Ti=e) / 找到e return Ti*2+1;return Nil; / 没找到e / 返回e的右孩子。若e无右孩子,则返回空TElemType RightChild(SqBiTree T,TElemType e) int i;if(T0=Nil) / 空树 return Nil;for(i=0;i<=MAX_TREE_SIZE-1;i+)if(Ti=e) / 找到e return Ti*2+2;return Nil; / 没找到e / 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回空 TElemType LeftSibling(SqBiTree T,TElemType e)int i;if(T0=Nil) / 空树 return Nil;for(i=1;i<=MAX_TREE_SIZE-1;i+)if(Ti = e && i%2 = 0) / 找到e且其序号为偶数(是右孩子) return Ti-1;return Nil; / 没找到e / 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回空TElemType RightSibling(SqBiTree T,TElemType e) int i;if(T0=Nil) / 空树 return Nil;for(i=1;i<=MAX_TREE_SIZE-1;i+)if(Ti=e&&i%2) / 找到e且其序号为奇数(是左孩子) return Ti+1;return Nil; / 没找到e / 把从q的j结点开始的子树移为从T的i结点开始的子树/ InsertChild()用到 void Move(SqBiTree q,int j,SqBiTree T,int i)if(q2*j+1 != Nil) / q的左子树不空 Move(q,(2*j+1),T,(2*i+1); / 把q的j结点的左子树移为T的i结点的左子树 if(q2*j+2 != Nil) / q的右子树不空 Move(q,(2*j+2),T,(2*i+2); / 把q的j结点的右子树移为T的i结点的右子树 Ti=qj; / 把q的j结点移为T的i结点 qj=Nil; / 把q的j结点置空 / 根据LR为0或1,插入c为T中p结点的左或右子树。p结点的原有左或 / 右子树则成为c的右子树 int InsertChild(SqBiTree T,TElemType p,int LR,SqBiTree c)int j,k,i=0;for(j=0;j<(int)pow(2,BiTreeDepth(T)-1;j+) / 查找p的序号 if(Tj=p) / j为p的序号 break;k=2*j+1+LR; / k为p的左或右孩子的序号 if(Tk != Nil) / p原来的左或右孩子不空 Move(T,k,T,2*k+2); / 把从T的k结点开始的子树移为从k结点的右子树开始的子树 Move(c,i,T,k); / 把从c的i结点开始的子树移为从T的k结点开始的子树 return 1;/ 构造一个空队列Qint InitQueue(SqQueue *Q)(*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType);/分配定长的空间，相当于一个数组if(!(*Q).base) / 存储分配失败 exit(0);(*Q).front=(*Q).rear=0;/初始化下标return 1;/ 插入元素e为Q的新的队尾元素 int EnQueue(SqQueue *Q,QElemType e)if(*Q).rear>=MAXQSIZE) / 队列满，增加1个存储单元 (*Q).base=(QElemType *)realloc(*Q).base,(*Q).rear+1)*sizeof(QElemType);if(!(*Q).base) / 增加单元失败 return 0;*(*Q).base+(*Q).rear)=e;(*Q).rear+;return 1;/ 若队列不空,则删除Q的队头元素,用e返回其值,并返回1,否则返回0 int DeQueue(SqQueue *Q,QElemType *e)if(*Q).front=(*Q).rear) / 队列空 return 0;*e=(*Q).base(*Q).front;(*Q).front=(*Q).front+1;return 1;/ 根据LR为1或0,删除T中p所指结点的左或右子树 int DeleteChild(SqBiTree T,position p,int LR)int i;int k=1; / 队列不空的标志 SqQueue q;InitQueue(&q); / 初始化队列，用于存放待删除的结点 i=(int)pow(2,p.level-1)+p.order-2; / 将层、本层序号转为矩阵的序号 if(Ti=Nil) / 此结点空 return 0;i=i*2+1+LR; / 待删除子树的根结点在矩阵中的序号 while(k)if(T2*i+1!=Nil) / 左结点不空 EnQueue(&q,2*i+1); / 入队左结点的序号 if(T2*i+2!=Nil) / 右结点不空 EnQueue(&q,2*i+2); / 入队右结点的序号 Ti=Nil; / 删除此结点 k=DeQueue(&q,&i); / 队列不空 return 1;int(*VisitFunc)(TElemType); / 函数变量 void PreTraverse(SqBiTree T,int e) / PreOrderTraverse()调用 VisitFunc(Te);/先调用函数VisitFunc处理根if(T2*e+1!=Nil) / 左子树不空 PreTraverse(T,2*e+1);/然后处理左子树if(T2*e+2!=Nil) / 右子树不空 PreTraverse(T,2*e+2);/ 先序遍历T,对每个结点调用函数Visit一次且仅一次。int PreOrderTraverse(SqBiTree T,int(*Visit)(TElemType)VisitFunc=Visit;if(!BiTreeEmpty(T) / 树不空 PreTraverse(T,0);printf("n");return 1;/ InOrderTraverse()调用void InTraverse(SqBiTree T,int e) if(T2*e+1!=Nil) / 左子树不空 InTraverse(T,2*e+1);VisitFunc(Te);if(T2*e+2!=Nil) / 右子树不空 InTraverse(T,2*e+2);/ 中序遍历T,对每个结点调用函数Visit一次且仅一次。int InOrderTraverse(SqBiTree T,int(*Visit)(TElemType) VisitFunc=Visit;if(!BiTreeEmpty(T) / 树不空 InTraverse(T,0);printf("n");return 1;/ PostOrderTraverse()调用void PostTraverse(SqBiTree T,int e) if(T2*e+1!=Nil) / 左子树不空 PostTraverse(T,2*e+1);if(T2*e+2!=Nil) / 右子树不空 PostTraverse(T,2*e+2);VisitFunc(Te);/ 后序遍历T,对每个结点调用函数Visit一次且仅一次。 int PostOrderTraverse(SqBiTree T,int(*Visit)(TElemType)VisitFunc = Visit;if(!BiTreeEmpty(T) / 树不空 PostTraverse(T,0);printf("n");return 1;/ 层序遍历二叉树void LevelOrderTraverse(SqBiTree T,int(*Visit)(TElemType)int i=MAX_TREE_SIZE-1,j;while(Ti = Nil)i-; / 找到最后一个非空结点的序号 for(j=0;j<=i;j+) / 从根结点起,按层序遍历二叉树 if(Tj != Nil)Visit(Tj); / 只遍历非空的结点 printf("n");/ 逐层、按本层序号输出二叉树void Print(SqBiTree T)int j,k;position p;TElemType e;for(j=1;j<=BiTreeDepth(T);j+)printf("第%d层: ",j);for(k=1; k <= pow(2,j-1);k+)p.level=j;p.order=k;e=Value(T,p);if(e!=Nil)printf("%d:%c ",k,e);printf("n");int visit(TElemType e)printf("%c ",e);return 0;int main()int i,j;position p;TElemType e;SqBiTree T,s;InitBiTree(T);CreateBiTree(T);printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%dn",BiTreeEmpty(T),BiTreeDepth(T);i=Root(T,&e);if(i)printf("二叉树的根为：%cn",e);elseprintf("树空，无根n");printf("层序遍历二叉树:n");LevelOrderTraverse(T,visit);printf("中序遍历二叉树:n");InOrderTraverse(T,visit);printf("后序遍历二叉树:n");PostOrderTraverse(T,visit);printf("请输入待修改结点的层号 本层序号: ");scanf("%d%d%*c",&p.level,&p.order);e=Value(T,p);printf("待修改结点的原值为%c请输入新值: ",e);scanf("%c%*c",&e);Assign(T,p,e);printf("先序遍历二叉树:n");PreOrderTraverse(T,visit);printf("结点%c的双亲为%c,左右孩子分别为",e,Parent(T,e);printf("%c,%c,左右兄弟分别为",LeftChild(T,e),RightChild(T,e);printf("%c,%cn",LeftSibling(T,e),RightSibling(T,e);InitBiTree(s);printf("建立右子树为空的树s:n");CreateBiTree(s);printf("树s插到树T中,请输入树T中树s的双亲结点 s为左(0)或右(1)子树: ");scanf("%c%d%*c",&e,&j);InsertChild(T,e,j,s);Print(T);printf("删除子树,请输入待删除子树根结点的层号 本层序号 左(0)或右(1)子树: ");scanf("%d%d%d%*c",&p.level,&p.order,&j);DeleteChild(T,p,j);Print(T);ClearBiTree(T);printf("清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%dn",BiTreeEmpty(T),BiTreeDepth(T);i=Root(T,&e);if(i)printf("二叉树的根为：%cn",e);elseprintf("树空，无根n");system("pause");return 0;/*输出效果：请按层序输入结点的值(字符)，空格表示空结点，结点数100:例如：abcefghabcdefgh建立二叉树后,树空否？0(1:是 0:否) 树的深度=4二叉树的根为：a层序遍历二叉树:a b c d e f g h中序遍历二叉树:h d b e a f c g后序遍历二叉树:h d e b f g c a请输入待修改结点的层号 本层序号: 3 2待修改结点的原值为e请输入新值: i先序遍历二叉树:a b d h i c f g结点i的双亲为b,左右孩子分别为 , ,左右兄弟分别为d,建立右子树为空的树s:请按层序输入结点的值(字符)，空格表示空结点，结点数100:例如：abcefghjk l树s插到树T中,请输入树T中树s的双亲结点 s为左(0)或右(1)子树: i 0第1层: 1:a第2层: 1:b 2:c第3层: 1:d 2:i 3:f 4:g第4层: 1:h 3:j第5层: 5:k第6层: 9:l删除子树,请输入待删除子树根结点的层号 本层序号 左(0)或右(1)子树: 2 1 0第1层: 1:a第2层: 1:b 2:c第3层: 2:i 3:f 4:g第4层: 3:j第5层: 5:k第6层: 9:l清除二叉树后,树空否？1(1:是 0:否) 树的深度=0树空，无根请按任意键继续. . . */
