我有一些代码可以从数据点生成四叉树。我知道如何用斜杠打印出二叉树，但我甚至不知道从哪里开始打印/绘制一个有4个孩子而不是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行的函数？或者可以将它打印出来？
当你用GIS和空间分类你的问题时，这个问题让我想到了每个角落里有东北，西北，东南和西南的地图。
单节点四叉树只是：
(0,0)
双节点四叉树将是：
.|( 1, 1)
----( 0, 0)----
.|.
有3个节点深度可用于：
| .|( 2, 2)
|----( 1, 1)----
.| .|.
------------( 0, 0)------------
.|.
|
|
我已经实现了这个想法，对代码进行了一些更改以使其更容易：
__repr__方法进行数字格式化get_depth方法，但它没有用...我也认为search和insert函数应该是类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)
|
|
|
|
|
|
告诉我你是否觉得有用！