如何在 python 中漂亮地打印四叉树？

Question

我有一些代码可以根据数据点生成四叉树。我知道如何用斜杠打印出二叉树，但我什至不知道从哪里开始 print/draw 用 4 个 children 而不是每个 2 个来显示我的树。

我一直在使用我的 search_pqtreee 函数对其进行测试。例如，要列出东北象限中的所有点，我可以通过制作如下列表来测试它：[search_pqtree(q.ne,p) for p in points]

#The point import is a class for points in Cartesian coordinate systems
from point import *

class PQuadTreeNode():
    def __init__(self,point,nw=None,ne=None,se=None,sw=None):
        self.point = point
        self.nw = nw
        self.ne = ne
        self.se = se
        self.sw = sw
    def __repr__(self):
        return str(self.point)
    def is_leaf(self):
        return self.nw==None and self.ne==None and \
            self.se==None and self.sw==None

def search_pqtree(q, p, is_find_only=True):
    if q is None:
        return
    if q.point == p:
        if is_find_only:
            return q
        else:
            return
    dx,dy = 0,0
    if p.x >= q.point.x:
        dx = 1
    if p.y >= q.point.y:
        dy = 1
    qnum = dx+dy*2
    child = [q.sw, q.se, q.nw, q.ne][qnum]
    if child is None and not is_find_only:
        return q
    return search_pqtree(child, p, is_find_only)

def insert_pqtree(q, p):
    n = search_pqtree(q, p, False)
    node = PQuadTreeNode(point=p)
    if p.x < n.point.x and p.y < n.point.y:
        n.sw = node
    elif p.x < n.point.x and p.y >= n.point.y:
        n.nw = node
    elif p.x >= n.point.x and p.y < n.point.y:
        n.se = node
    else:
        n.ne = node

def pointquadtree(data):
    root = PQuadTreeNode(point = data[0])
    for p in data[1:]:
        insert_pqtree(root, p)
    return root

#Test
data1 = [ (2,2), (0,5), (8,0), (9,8), (7,14), (13,12), (14,13) ]

points = [Point(d[0], d[1]) for d in data1]
q = pointquadtree(points)
print([search_pqtree(q.ne, p) for p in points])

我想说的是，如果我正在打印一个二叉树，它可能看起来像这样：

       (2, 2)                          
      /      \                         
   (0, 5)  (8, 0)                      
   /    \ /      \

有没有办法编写一个函数，每行打印 4 行？或者横着打印出来？

Answer 1

当你class用 GIS 和空间解决你的问题时，这个问题让我想到了一张地图，每个角落都有东北、西北、东南和西南。

单节点四叉树就是：

(0,0)

两个节点的四叉树将是：

      .|( 1, 1)
----( 0, 0)----
      .|.

如果深度为 3 个节点，将转到：

               |      .|( 2, 2)
               |----( 1, 1)----
              .|      .|.
------------( 0, 0)------------
              .|.
               |
               |

我已经实现了这个想法，对您的代码进行了一些更改以使其更容易：

我添加了一个小点 class，使用我需要的 __repr__ 方法来格式化数字
我将象限制作成字典以便能够在它们上循环
我以为我需要 get_depth 方法，但没有用到...

我也认为 search 和 insert 函数应该是 class PQuadTreeNode 的方法，但我把它留给你作为练习:)

实施工作包括以下步骤：

如果四叉树是一片叶子，它的地图就是中心点
获取4个象限的地图（如果为空，则为一个点）
使用最大的尺寸将它们归一化，并将它们放在父级的中心附近
以四叉树点为中心合并4个象限

这当然是高度递归的，我没有做任何优化尝试。如果数字的长度大于 2（例如 100 或 -10），您可以调整 num_length 变量。

num_length = 2
num_fmt = '%' + str(num_length) + 'd'

class Point():
    def __init__(self,x=None,y=None):
        self.x = x
        self.y = y
    def __repr__(self):
        return '(' + (num_fmt % self.x) + ',' + (num_fmt % self.y) + ')'

def normalize(corner, quadmap, width, height):
    old_height = len(quadmap)
    old_width = len(quadmap[0])
    if old_height == height and old_width == width:
        return quadmap
    else:
        blank_width = width - old_width
        if corner == 'nw':
            new = [' '*width for i in range(height - old_height)]
            for line in quadmap:
                new.append(' '*blank_width + line)
        elif corner == 'ne':
            new = [' '*width for i in range(height - old_height)]
            for line in quadmap:
                new.append(line + ' '*blank_width)
        elif corner == 'sw':
            new = []
            for line in quadmap:
                new.append(' '*blank_width + line)
            for i in range(height - old_height):
                new.append(' '*width)
        elif corner == 'se':
            new = []
            for line in quadmap:
                new.append(line + ' '*blank_width)
            for i in range(height - old_height):
                new.append(' '*width)
        return new

class PQuadTreeNode():
    def __init__(self,point,nw=None,ne=None,se=None,sw=None):
        self.point = point
        self.quadrants = {'nw':nw, 'ne':ne, 'se':se, 'sw':sw}

    def __repr__(self):
        return '\n'.join(self.get_map())

    def is_leaf(self):
        return all(q == None for q in self.quadrants.values())

    def get_depth(self):
        if self.is_leaf():
            return 1
        else:
            return 1 + max(q.get_depth() if q else 0 for q in self.quadrants.values())

    def get_map(self):
        if self.is_leaf():
            return [str(self.point)]
        else:
            subquadmaps = {
                sqn:sq.get_map() if sq else ['.']
                for sqn, sq
                in self.quadrants.items()
            }
            subheight = max(len(map) for map in subquadmaps.values())
            subwidth = max(len(mapline) for map in subquadmaps.values() for mapline in map)
            subquadmapsnorm = {
                sqn:normalize(sqn, sq, subwidth, subheight)
                for sqn, sq
                in subquadmaps.items()
            }
            map = []
            for n in range(subheight):
                map.append(subquadmapsnorm['nw'][n] + '|' + subquadmapsnorm['ne'][n])
            map.append('-' * (subwidth-num_length-1) + str(self.point) + '-' * (subwidth-num_length-1))
            for n in range(subheight):
                map.append(subquadmapsnorm['sw'][n] + '|' + subquadmapsnorm['se'][n])
            return map

def search_pqtree(q, p, is_find_only=True):
    if q is None:
        return
    if q.point == p:
        if is_find_only:
            return q
        else:
            return
    dx,dy = 0,0
    if p.x >= q.point.x:
        dx = 1
    if p.y >= q.point.y:
        dy = 1
    qnum = dx+dy*2
    child = [q.quadrants['sw'], q.quadrants['se'], q.quadrants['nw'], q.quadrants['ne']][qnum]
    if child is None and not is_find_only:
        return q
    return search_pqtree(child, p, is_find_only)

def insert_pqtree(q, p):
    n = search_pqtree(q, p, False)
    node = PQuadTreeNode(point=p)
    if p.x < n.point.x and p.y < n.point.y:
        n.quadrants['sw'] = node
    elif p.x < n.point.x and p.y >= n.point.y:
        n.quadrants['nw'] = node
    elif p.x >= n.point.x and p.y < n.point.y:
        n.quadrants['se'] = node
    else:
        n.quadrants['ne'] = node

def pointquadtree(data):
    root = PQuadTreeNode(point = data[0])
    for p in data[1:]:
        insert_pqtree(root, p)
    return root

#Test
data1 = [ (2,2), (0,5), (8,0), (9,8), (7,14), (13,12), (14,13) ]

points = [Point(d[0], d[1]) for d in data1]
q = pointquadtree(points)
print(q)

使用您的示例数据：

                               |               |      .|(14,13)
                               |               |----(13,12)----
                               |        ( 7,14)|      .|.
                               |------------( 9, 8)------------
                               |              .|.
                               |               |
                        ( 0, 5)|               |
----------------------------( 2, 2)----------------------------
                              .|( 8, 0)
                               |
                               |
                               |
                               |
                               |
                               |

如果觉得有用请告诉我！

如何在 python 中漂亮地打印四叉树？

How to pretty print a quadtree in python?

python

gis

tree

spatial

quadtree