第十周——项目一（2）—二叉树的构造

/*
* Copyright (c) 2017,烟台大学计算机学院
* All right reserved.
* 文件名称：btree
* 作者：潘亚楠
* 完成日期：2017年12月10日
* 版本号：v1.0
*
* 问题描述：二叉树遍历的递归算法
* 输入描述：标准函数输入
* 程序输出：二叉树序列
*/
（btreee.h见算法库）

1.由先序序列和中序序列构造二叉树
[cpp] view plain copy
1. #include <stdio.h>
2. #include <malloc.h>
3. #include "btree.h"
5. BTNode *CreateBT1(char *pre,char *in,int n)
6. /*pre存放先序序列,in存放中序序列,n为二叉树结点个数,
7. 本算法执行后返回构造的二叉链的根结点指针*/
8. {
9. BTNode *s;
10. char *p;
11. int k;
12. if (n<=0) return NULL;
13. s=(BTNode *)malloc(sizeof(BTNode)); //创建二叉树结点*s
14. s->data=*pre;
15. for (p=in; p<in+n; p++) //在中序序列中找等于*ppos的位置k
16. if (*p==*pre) //pre指向根结点
17. break; //在in中找到后退出循环
18. k=p-in; //确定根结点在in中的位置
19. s->lchild=CreateBT1(pre+1,in,k); //递归构造左子树
20. s->rchild=CreateBT1(pre+k+1,p+1,n-k-1); //递归构造右子树
21. return s;
22. }
24. int main()
25. {
26. ElemType pre[]="ABDGCEF",in[]="DGBAECF";
27. BTNode *b1;
28. b1=CreateBT1(pre,in,7);
29. printf("b1:");
30. DispBTNode(b1);
31. printf("\n");
32. return 0;
33. }
运算结果：
2.由后序序列和中序序列构造二叉树
[cpp] view plain copy
1. #include <stdio.h>
2. #include <malloc.h>
3. #include "btree.h"
5. BTNode *CreateBT2(char *post,char *in,int n)
6. /*post存放后序序列,in存放中序序列,n为二叉树结点个数,
7. 本算法执行后返回构造的二叉链的根结点指针*/
8. {
9. BTNode *s;
10. char r,*p;
11. int k;
12. if (n<=0) return NULL;
13. r=*(post+n-1); //根结点值
14. s=(BTNode *)malloc(sizeof(BTNode)); //创建二叉树结点*s
15. s->data=r;
16. for (p=in; p<in+n; p++) //在in中查找根结点
17. if (*p==r)
18. break;
19. k=p-in; //k为根结点在in中的下标
20. s->lchild=CreateBT2(post,in,k); //递归构造左子树
21. s->rchild=CreateBT2(post+k,p+1,n-k-1); //递归构造右子树
22. return s;
23. }
25. int main()
26. {
27. ElemType in[]="DGBAECF",post[]="GDBEFCA";
28. BTNode *b2;
29. b2=CreateBT2(post,in,7);
30. printf("b2:");
31. DispBTNode(b2);
32. printf("\n");
33. return 0;
34. }
运行结果：

3.由顺序存储结构转为二叉链存储结构
[cpp] view plain copy
1. #include <stdio.h>
2. #include <malloc.h>
3. #include "btree.h"
4. #define N 30
5. typedef ElemType SqBTree[N];
6. BTNode *trans(SqBTree a,int i)
7. {
8. BTNode *b;
9. if (i>N)
10. return(NULL);
11. if (a[i]=='#')
12. return(NULL); //当节点不存在时返回NULL
13. b=(BTNode *)malloc(sizeof(BTNode)); //创建根节点
14. b->data=a[i];
15. b->lchild=trans(a,2*i); //递归创建左子树
16. b->rchild=trans(a,2*i+1); //递归创建右子树
17. return(b); //返回根节点
18. }
19. int main()
20. {
21. BTNode *b;
22. ElemType s[]="0ABCD#EF#G####################";
23. b=trans(s,1);
24. printf("b:");
25. DispBTNode(b);
26. printf("\n");
27. return 0;
28. }
运算结果：

第十周——项目一（2）—二叉树的构造

相关推荐