当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 将一个数组中的各节点按照层次遍历插入构成完全二叉树

将一个数组中的各节点按照层次遍历插入构成完全二叉树

2018年11月27日  | 移动技术网IT编程  | 我要评论

天价皇后 梨花妖,抚宁,铁皮石斛组培

按层次构建完全二叉树

（本人入门水平，这是我的第一篇博客，希望通过写写博客能增强自己的理解，同时也能给大家提供一些力所能及的帮助，通过这个平台共同进步，有错误的地方希望各位大佬指出来，我会努力改正的，谢谢大家！）

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 }

主函数就不写了。

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网