data = [3, 7, 5, 16, 13, 16, 24, 20]
def addBlankAndAppend(List,addStr):
for i in range(len(List)):
List[i] = " " + List[i] +" "
List.append(addStr)
def printHeap(List, limit): #limit can be len(List)
printLi = []
levelStart = 0
levelCount = 1 #每层节点的个数,2 的幂
levelLimit = 1 #每层节点索引的限制
while(levelStart < limit):
levelStr = ""
for levelItem in range(levelStart, min(levelLimit, limit)):
levelStr += str(List[levelItem])+" "
levelStr = levelStr[:-1]
if levelStart != 0:#只要不是第一层就加上指针
pointerStr = ""
for i in range(int(levelCount/2)):
pointerStr += "/ \ "
pointerStr = pointerStr[:-1]
addBlankAndAppend(printLi, pointerStr)
addBlankAndAppend(printLi, levelStr)
levelCount = levelCount << 1
levelStart = levelCount - 1
levelLimit += levelCount
for item in printLi:
print(item)
printHeap(data,len(data))
好像实现有点问题,不过将就也能方便看了。
3
/ \
7 5
/ \ / \
16 13 16 24
/ \ / \ / \ / \
20
想改一下,又不知道咋改了
1
msg7086 2020-08-01 12:49:59 +08:00
分而治之,先求出当前子树的总宽度,然后再吐空格。基本上是一个 DFS 加一个 BFS 的结构。
(吐字也可以直接在内存中构建字符串,这样应该可以 DFS 一遍过。) |
2
amiwrong123 OP @msg7086
思路确实有问题,不过我感觉吐空格不是那么简单,层数一多起来( 5,6 层)的时候,各个层数字之间的空格可能都不一样。有点费脑细胞了。。 |
3
fuxiuyin 2020-08-01 13:45:03 +08:00 via iPhone
基于数组的完全二叉树相当于已经知道层次遍历的结果和层数了,可以直接开始输出。所以最主要的输出格式,输出结果是一层数字一层 / \ / \,数字和数字之间三个空格。所以,应该是每一层,先打总层数-当前层数的空格,然后开始打当前层数字,再打一行 / \ / \进入下一层
|
5
amiwrong123 OP @fuxiuyin
我现在先考虑数字都是一位数的,能实现就行,两位数的话再优化😂 |
6
msg7086 2020-08-01 14:57:33 +08:00
@amiwrong123
从根节点做一次 DFS,然后每个节点保存宽度,类似 node.w = MAX(自身宽度, MIN(左枝宽度,2), MIN(右枝宽度,2)) 然后根据左右宽度生成树枝和子树节点应该就可以了。 |
7
msg7086 2020-08-01 15:51:22 +08:00
|
8
amiwrong123 OP @fuxiuyin
@msg7086 哈哈,我想到怎么实现了。大概就是这样 https://blog.csdn.net/anlian523/article/details/107732532 幸亏 @fuxiuyin 老哥提醒了我,数字和数字之间三个空格,我就直接让最后一层(也就是宽度最宽的那一层)的数字之间都间隔三个空格。 |