算法与数据结构(一)将一个数组中的各节点按照…

2018-12-04 07:15:29来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

按层次构建完全二叉树

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

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语言数据结构与算法之深度、广度优先搜索

下一篇:算法与数据结构(二)三元组矩阵行列式的计算(用递归)