设为首页 加入收藏

TOP

将一个数组中的各节点按照层次遍历插入构成完全二叉树
2018-11-26 18:10:46 】 浏览:32
Tags:一个数 节点 按照 层次 插入 构成 完全

按层次构建完全二叉树

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

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 }

主函数就不写了。


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇二分法查找 下一篇用变a给出下面的定义

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }