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

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

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


    简单写了一版。
    amiwrong123
        8
    amiwrong123   7 天前
    @fuxiuyin
    @msg7086

    哈哈,5分钟快3我 想到怎么实现了。大概就是这样 http://blog.csdn.net/anlian523/article/details/107732532
    幸亏 @fuxiuyin 老哥提醒了5分钟快3我 ,数字和数字之间三个空格,5分钟快3我 就直接让最后一层(也就是宽度最宽的那一层)的数字之间都间隔三个空格。
    5分钟快3关于   ·   FAQ   ·   API   ·   5分钟快35分钟快3我 们 的愿景   ·   广告投放   ·   感谢   ·   实用小5分钟快3工具   ·   2289 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 02:12 · PVG 10:12 · LAX 19:12 · JFK 22:12
    ♥ Do have faith in what you're doing.