《数据结构c语言版 二叉树的顺序存储表示和实现》由会员分享，可在线阅读，更多相关《数据结构c语言版 二叉树的顺序存储表示和实现（12页珍藏版）》请在金锄头文库上搜索。
1、/* 数据结构 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 struct int level,/结点的层 order;/本层序号(按满二叉树计算)position;typedef int QElemType;/ 队列的顺序
2、存储结构(可用于循环队列和非循环队列) #define MAXQSIZE 5 / 最大队列长度(对于循环队列，最大队列长度要减 1) typedef struct QElemType *base; / 初始化的动态分配存储空间 相当于一个数组 int front; / 头指针,若队列不空,指向队列头元素，相当于一个数组下标 int rear; / 尾指针,若队列不空,指向队列尾元素的下一个位置 / 相当于一个数组下标SqQueue;#define ClearBiTree InitBiTree / 在顺序存储结构中，两函数完全一样 TElemType Nil = ; / 设空为字符型的空格符 /
3、 构造空二叉树 T。因为 T 是固定数组，不会改变，故不需要for(i=0;i=0;i-) / 找到最后一个结点 if(Ti != Nil) break; i+; / 为了便于计算 do j+; while(i=pow(2,j); /i pow(2, depth-1) 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
4、).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( / 初始化队列，用于存放待删除的结点 i=(int)pow(2,p.level-1)+p.order-2; / 将层、本层序号转为矩阵的序号 if(Ti
5、=Nil) / 此结点空 return 0; i=i*2+1+LR; / 待删除子树的根结点在矩阵中的序号 while(k) if(T2*i+1!=Nil) / 左结点不空 EnQueue( / 入队左结点的序号 if(T2*i+2!=Nil) / 右结点不空 EnQueue( / 入队右结点的序号 Ti=Nil; / 删除此结点 k=DeQueue( / 队列不空 return 1; int(*VisitFunc)(TElemType); / 函数变量 void PreTraverse(SqBiTree T,int e) / PreOrderTraverse()调用 VisitFunc(Te
6、);/先调用函数 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; / InOrd
7、erTraverse()调用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); pr
8、intf(“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(
9、!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(S
10、qBiTree 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; S
11、qBiTree T,s; InitBiTree(T);CreateBiTree(T);printf(“建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%dn“,BiTreeEmpty(T),BiTreeDepth(T); i=Root(T, if(i) printf(“二叉树的根为：%cn“,e);else printf(“树空，无根n“); printf(“层序遍历二叉树:n“);LevelOrderTraverse(T,visit); printf(“中序遍历二叉树:n“);InOrderTraverse(T,visit); printf(“后序遍历二叉树:n“);PostOrde
12、rTraverse(T,visit); printf(“请输入待修改结点的层号 本层序号: “);scanf(“%d%d%*c“, e=Value(T,p); printf(“待修改结点的原值为%c 请输入新值: “,e);scanf(“%c%*c“, 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,%c
13、n“,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“, InsertChild(T,e,j,s); Print(T); printf(“删除子树,请输入待删除子树根结点的层号 本层序号 左(0)或右(1)子树: “);scanf(“%d%d%d%*c“, DeleteChild(T,p,j); Print(T); C
14、learBiTree(T); printf(“清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%dn“,BiTreeEmpty(T),BiTreeDepth(T); i=Root(T, if(i) printf(“二叉树的根为：%cn“,e);else printf(“树空，无根n“);system(“pause“); return 0; /* 输出效果：请按层序输入结点的值(字符)，空格表示空结点，结点数100: 例如：abcefghabcdefgh 建立二叉树后,树空否？0(1:是 0:否) 树的深度=4 二叉树的根为：a 层序遍历二叉树:a b c d e f g h 中序遍历二
15、叉树: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 树空，无根请按任意键继续. . . */
