Layout a binary tree (2)
题目
An alternative layout method is depicted in the above illustration. Find out the rules and write the corresponding Prolog predicate. Hint: On a given level, the horizontal distance between neighboring nodes is constant.
Use the same conventions as in problem 4.13 and test your predicate in an appropriate way.
用单元测试描述为：
from python99.btree.p414 import layout_binary_tree
def test_layout_binary_tree():
E = 'E'
assert layout_binary_tree([E, [E, None, [E, None, None]], [E, [E, None, None], None]]) == [('E', 3, 1),
[('E', 1, 2), None, [
('E', 2, 3), None, None]],
[('E', 5, 2), [('E', 4, 3), None, None], None]]
解题思路
分析示例图，得出以下规则：
- Y轴坐标等于节点深度，根节点深度记为1
- 整树的深度记为D，节点的深度记为i，则某一层节点之间X轴相距
2^(D-i+1) - 最左的节点X轴坐标为1
- 左子节点X轴坐标记为
xl，则其父节点X轴坐标为xl+2^(D-i-1)。D为整树深度，i为父节点深度 - 父节点X轴坐标记为
xp，则其左子节点X轴坐标为xp-2^(D-i-1)。D为整树深度，i为父节点深度 - 父节点X轴坐标记为
xp，则其右子节点X轴坐标为xp+2^(D-i-1)。D为整树深度，i为父节点深度
通过中序遍历二叉树，先找到最左的节点，将其X轴记为1。再按照上述规则4，5，6，向右标记所有节点。在标记X轴的同时，标记Y轴。
代码实现：
def layout_binary_tree(t):
markedTree,_ = markXY(t, depth(t), 0, 1)
return markedTree
def markXY(t, d, x, y):
selfX = x
e = ()
if t is None:
return (None, x)
if t[1] is None and x == 0:
# this node is the most left one
selfX = 1
e = (t[0], selfX, y)
if selfX == 0:
leftX = selfX
else:
leftX = selfX - int(2**(d-y-1))
left, leftX = markXY(t[1], d, leftX, y+1)
selfX = leftX + int(2**(d-y-1))
e = (t[0], selfX, y)
rightX = selfX + int(2**(d-y-1))
right, _ = markXY(t[2], d, rightX, y+1)
return [e, left, right], selfX
def depth(t):
if t is None:
return 0
return max(depth(t[1]), depth(t[2])) + 1