如何打印一个基于数组的完全二叉树

[amiwrong123]

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

想改一下，又不知道咋改了

[msg7086]

分而治之，先求出当前子树的总宽度，然后再吐空格。基本上是一个 DFS 加一个 BFS 的结构。
（吐字也可以直接在内存中构建字符串，这样应该可以 DFS 一遍过。）

[amiwrong123]

@msg7086
思路确实有问题，不过我感觉吐空格不是那么简单，层数一多起来（ 5,6 层）的时候，各个层数字之间的空格可能都不一样。有点费脑细胞了。。

[fuxiuyin]

基于数组的完全二叉树相当于已经知道层次遍历的结果和层数了，可以直接开始输出。所以最主要的输出格式，输出结果是一层数字一层 / \ / \，数字和数字之间三个空格。所以，应该是每一层，先打总层数-当前层数的空格，然后开始打当前层数字，再打一行 / \ / \进入下一层

[fuxiuyin]

@fuxiuyin 诶，想简单了，又想了想发现，如果一个数字特别大的话，会影响到宽度

[amiwrong123]

@fuxiuyin
我现在先考虑数字都是一位数的，能实现就行，两位数的话再优化😂

[msg7086]

@amiwrong123
从根节点做一次 DFS，然后每个节点保存宽度，类似
node.w = MAX(自身宽度, MIN(左枝宽度,2), MIN(右枝宽度,2))
然后根据左右宽度生成树枝和子树节点应该就可以了。

[msg7086]

https://gist.github.com/msg7086/339367f39431e0b6e40cf9e34a2c1d52

简单写了一版。

[amiwrong123]

@fuxiuyin
@msg7086

哈哈，我想到怎么实现了。大概就是这样 https://blog.csdn.net/anlian523/article/details/107732532
幸亏 @fuxiuyin 老哥提醒了我，数字和数字之间三个空格，我就直接让最后一层（也就是宽度最宽的那一层）的数字之间都间隔三个空格。