算法与数据结构(一)将一个数组中的各节点按照…
2018-12-04 07:15:29来源:博客园 阅读 ()
按层次构建完全二叉树
(本人入门水平,这是我的第一篇博客,希望通过写写博客能增强自己的理解,同时也能给大家提供一些力所能及的帮助,通过这个平台共同进步,有错误的地方希望各位大佬指出来,我会努力改正的,谢谢大家!)
1.主要思想:
由于是层次遍历,必须保证一行(也就是一层)构建完成才能继续添加下一层的节点,这就使对于树的来讲,操作比较方便的“递归算法”会在这个问题上操作困难。
为了达到按照层次遍历的需求,我们需要另外寻求方法,那就是用迭代(也就是循环)。
从根节点开始循环,每次创建两个结点,分别作父亲节点的左孩子和右孩子,通过(层数-1)(log2[节点数]来确定)来控制循环次数,并通过条件判断来防止超出节点个数。
2.代码部分:
1 typedef int Elementtype; // 定义数据类型,可根据需要自行定制
2 typedef struct TreeNode * Node; // Node相当于struct treeNode *
3 // 定义数节点结构
4 typedef struct TreeNode {
5 Elementtype value;
6 Node left; // 树节点的左子节点
7 Node right; // 树节点的右子节点
8 }TREE,*PTREE;
9
10
11 //初始化
12 void initBtree(PTREE &bTree){
13 bTree= new TREE;
14 bTree->left=NULL;
15 bTree->right=NULL;
16 bTree->value=0;
17 }
18
19
20
21 // 层次遍历构造完全二叉树定义
22 void bTreetobTree(PTREE bTree1,int *val,int length) {//数组和数组的长度
23 PTREE p = bTree1;
24 PTREE q = bTree1;
25 for(int i=length;i>=0;i--){
26 val[i+1]=val[i];
27 }
28 length++;
29 val[0]=0;
30 int m=log2(length);
31 int max= pow(2,m)-1;
32 for(int i=0;i<max;i++){
33 p->value = val[i];
34 if(length>2*i+1){
35 PTREE pArr2 = (PTREE)malloc(sizeof(TREE));
36 p->left = pArr2;
37 p->left->value = val[2*i+1];
38 p->left->left=NULL;
39 p->left->right=NULL;
40 }
41 if(length>2*i+2){
42 PTREE pArr3 = (PTREE)malloc(sizeof(TREE));
43 p->right = pArr3;
44 p->right->value = val[2*i+2];
45 p->right->left=NULL;
46 p->right->right=NULL;
47 }
48 if(i%2==0){
49 q=p;
50 p=p->left;
51 }
52 else{
53 p=q->right;
54 }
55 }
56 printf("\n*************************************************************************************\n");
57 printf("\n最终得到的完全二叉树经过中序输出为:\n");
58 InOrderTree(bTree1);
59 }
主函数就不写了。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ rand函数 2020-06-10
- 一个工业级、跨平台、轻量级的 tcp 网络服务框架:gevent 2020-06-05
- 数据结构—链表 2020-05-29
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 分享一个自己项目中用到的c++版的日志类(对初学者十分有用的 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash