我有一些代码可以根据数据点制作四叉树。我知道如何用斜杠打印出二叉树,但我什至不知道从哪里开始打印/绘制有4个子代(而不是每个2个)的树来可视化我的树。

我一直在使用我的search_pqtreee函数进行测试。例如,要列出东北象限中的所有点,我可以通过像这样的列表进行测试:[search_pqtree(q.ne,p)in point in p]

#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行的函数?还是横向打印?

最佳答案

当您使用GIS和空间对您的问题进行分类时,这个问题使我想到了每个角落都有东北,西北,东南和西南的地图。

单节点四叉树将简单地是:

(0,0)


两节点四叉树将是:

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


如果深入3个节点,将可以:

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


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


我使用数字格式所需的__repr__方法添加了一个琐碎的点类
我将象限制成字典,以便可以在其上循环
我以为我需要get_depth方法,但是没有使用...


我也认为searchinsert函数应该是类PQuadTreeNode的方法,但我将它作为练习留给您:)

该实现通过以下步骤工作:


如果四叉树是叶子,则其地图为中心点
获取四个象限的地图(如果为空,则为一个点)
使用最大尺寸对它们进行归一化,然后将其放在父级的中心附近
将四个象限与位于中心的四叉树点合并。


这当然是高递归的,我没有进行任何优化的尝试。
如果数字的长度大于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 - 如何在python中漂亮地打印四叉树?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/55832474/

10-11 21:11