按层次构建完全二叉树
（本人入门水平，这是我的第一篇博客，希望通过写写博客能增强自己的理解，同时也能给大家提供一些力所能及的帮助，通过这个平台共同进步，有错误的地方希望各位大佬指出来，我会努力改正的，谢谢大家！）
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 }
主函数就不写了。
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/606165.html