2 qwezhaohaihong qwezhaohaihong 于 2016.03.13 20:51 提问

数据结构问题求解!一棵完全三叉树,下标为120的结点在第几层? 2C

一棵完全三叉树,下标为120的结点在第几层?一道作业题目就是不管怎么写,书本是没有找到定义

6个回答

caozhy
caozhy   Ds   Rxr 2016.03.14 12:19

第5层,C语言写程序验证

 #include <stdio.h>

int main()
{
    int n = 1;
    int level = 1;
    int levelcnt = 1;
    int leveli = 0;
    while (n != 120)
    {
        leveli++;
        n++;
        if (leveli == levelcnt)
        {
            levelcnt *= 3;
            leveli = 0;
            level++;            
        }
        printf("%d %d %d\n", n, level, leveli);
    }
}

http://codepad.org/ffhAOGVJ

2 2 0
3 2 1
4 2 2
5 3 0
6 3 1
7 3 2
8 3 3
9 3 4
10 3 5
11 3 6
12 3 7
13 3 8
14 4 0
15 4 1
16 4 2
17 4 3
18 4 4
19 4 5
20 4 6
21 4 7
22 4 8
23 4 9
24 4 10
25 4 11
26 4 12
27 4 13
28 4 14
29 4 15
30 4 16
31 4 17
32 4 18
33 4 19
34 4 20
35 4 21
36 4 22
37 4 23
38 4 24
39 4 25
40 4 26
41 5 0
42 5 1
43 5 2
44 5 3
45 5 4
46 5 5
47 5 6
48 5 7
49 5 8
50 5 9
51 5 10
52 5 11
53 5 12
54 5 13
55 5 14
56 5 15
57 5 16
58 5 17
59 5 18
60 5 19
61 5 20
62 5 21
63 5 22
64 5 23
65 5 24
66 5 25
67 5 26
68 5 27
69 5 28
70 5 29
71 5 30
72 5 31
73 5 32
74 5 33
75 5 34
76 5 35
77 5 36
78 5 37
79 5 38
80 5 39
81 5 40
82 5 41
83 5 42
84 5 43
85 5 44
86 5 45
87 5 46
88 5 47
89 5 48
90 5 49
91 5 50
92 5 51
93 5 52
94 5 53
95 5 54
96 5 55
97 5 56
98 5 57
99 5 58
100 5 59
101 5 60
102 5 61
103 5 62
104 5 63
105 5 64
106 5 65
107 5 66
108 5 67
109 5 68
110 5 69
111 5 70
112 5 71
113 5 72
114 5 73
115 5 74
116 5 75
117 5 76
118 5 77
119 5 78
120 5 79

可见是第5层的第79个节点。

zhelijun
zhelijun   2016.03.13 21:16

每层节点数为3的N-1次方,且1+3+9+27+81=121>120,所以在第五层

qq_34163821
qq_34163821   2016.03.14 08:57

同求,到底是五层还是七层呢

Royal_lr
Royal_lr   Ds   Rxr 2016.03.14 11:24

第五层,,2的6次方求和127

qq_31650261
qq_31650261   2016.03.13 21:05

每层结点数为2的k-1次方,所以在第七层

u014654707
u014654707   2016.03.13 21:12

3^0+3^1+...+3^(n-1)=(3^n-1)/2 (3^4-1)/2<120<(3^5-1)/2 在第4层

u014654707
u014654707 回复qwezhaohaihong: 推导没错,结果错了,是第5层。
一年多之前 回复
qwezhaohaihong
qwezhaohaihong 下标从0开始的第四层吗
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!