《数据结构C语言版 二叉树的顺序存储表示和实现.doc》由会员分享，可在线阅读，更多相关《数据结构C语言版 二叉树的顺序存储表示和实现.doc（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构C语言版 二叉树的顺序存储表示和实现.txt丶喜欢的歌，静静的听，喜欢的人，远远的看我笑了当初你不挺傲的吗现在您这是又玩哪出呢？/*数据结构C语言版 二叉树的顺序存储表示和实现P126 编译环境：Dev-C+ 4.9.9.2日期：2011年2月13日 */#include typedef char TElemType;/ 二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点 typedef structint level,/结点的层ord
2、er;/本层序号(按满二叉树计算)position;typedef int QElemType;/ 队列的顺序存储结构(可用于循环队列和非循环队列) #define MAXQSIZE 5 / 最大队列长度(对于循环队列，最大队列长度要减1) typedef structQElemType *base; / 初始化的动态分配存储空间 相当于一个数组 int front; / 头指针,若队列不空,指向队列头元素，相当于一个数组下标int rear; / 尾指针,若队列不空,指向队列尾元素的下一个位置/ 相当于一个数组下标SqQueue;#define ClearBiTree InitBiTree
3、/ 在顺序存储结构中，两函数完全一样 TElemType Nil = ; / 设空为字符型的空格符 / 构造空二叉树T。因为T是固定数组，不会改变，故不需要& int InitBiTree(SqBiTree T)int i;for(i=0;iMAX_TREE_SIZE;i+)Ti=Nil; / 初值为空 return 1;void DestroyBiTree() / 由于SqBiTree是定长类型,无法销毁 / 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T int CreateBiTree(SqBiTree T)int i = 0, l;char sMAX_TREE
4、_SIZE;printf(请按层序输入结点的值(字符)，空格表示空结点，结点数%d:n,MAX_TREE_SIZE);printf(例如：abcefghn);gets(s);/ 输入字符串 l = strlen(s);/ 求字符串的长度 for(;il;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=0;i-) / 找到最后一个结点 if(Ti != Nil)
5、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(i
6、nt)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
7、;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无左孩子,则返回空TEl
8、emType 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
9、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,TElem
10、Type 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结点的左子树
11、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=MAXQSIZE) / 队列满，增加1个存储单元 (*Q).base=(QElemType *)rea
12、lloc(*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,
13、删除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); / 入队左结点的序
14、号 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)
15、/ 右子树不空 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
16、);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
17、(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
18、)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=
19、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(树空
20、，无根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);PreOrderTr
21、averse(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);Prin
22、t(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;/*输出效果：请按层序输入结点的值
23、(字符)，空格表示空结点，结点数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树空，无根请按任意键继续. . . */