V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
amiwrong123
V2EX  ›  程序员

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

  •  
  •   amiwrong123 · 2020-08-01 12:38:31 +08:00 · 1741 次点击
    这是一个创建于 1574 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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
    

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

    8 条回复    2020-08-02 00:21:14 +08:00
    msg7086
        1
    msg7086  
       2020-08-01 12:49:59 +08:00
    分而治之,先求出当前子树的总宽度,然后再吐空格。基本上是一个 DFS 加一个 BFS 的结构。
    (吐字也可以直接在内存中构建字符串,这样应该可以 DFS 一遍过。)
    amiwrong123
        2
    amiwrong123  
    OP
       2020-08-01 13:36:00 +08:00
    @msg7086
    思路确实有问题,不过我感觉吐空格不是那么简单,层数一多起来( 5,6 层)的时候,各个层数字之间的空格可能都不一样。有点费脑细胞了。。
    fuxiuyin
        3
    fuxiuyin  
       2020-08-01 13:45:03 +08:00 via iPhone
    基于数组的完全二叉树相当于已经知道层次遍历的结果和层数了,可以直接开始输出。所以最主要的输出格式,输出结果是一层数字一层 / \ / \,数字和数字之间三个空格。所以,应该是每一层,先打总层数-当前层数的空格,然后开始打当前层数字,再打一行 / \ / \进入下一层
    fuxiuyin
        4
    fuxiuyin  
       2020-08-01 14:14:42 +08:00 via iPhone
    @fuxiuyin 诶,想简单了,又想了想发现,如果一个数字特别大的话,会影响到宽度
    amiwrong123
        5
    amiwrong123  
    OP
       2020-08-01 14:39:17 +08:00 via Android
    @fuxiuyin
    我现在先考虑数字都是一位数的,能实现就行,两位数的话再优化😂
    msg7086
        6
    msg7086  
       2020-08-01 14:57:33 +08:00
    @amiwrong123
    从根节点做一次 DFS,然后每个节点保存宽度,类似
    node.w = MAX(自身宽度, MIN(左枝宽度,2), MIN(右枝宽度,2))
    然后根据左右宽度生成树枝和子树节点应该就可以了。
    msg7086
        7
    msg7086  
       2020-08-01 15:51:22 +08:00
    amiwrong123
        8
    amiwrong123  
    OP
       2020-08-02 00:21:14 +08:00
    @fuxiuyin
    @msg7086

    哈哈,我想到怎么实现了。大概就是这样 https://blog.csdn.net/anlian523/article/details/107732532
    幸亏 @fuxiuyin 老哥提醒了我,数字和数字之间三个空格,我就直接让最后一层(也就是宽度最宽的那一层)的数字之间都间隔三个空格。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1054 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 19:16 · PVG 03:16 · LAX 11:16 · JFK 14:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.