Layout a binary tree

题目

Given a binary tree as the usual Prolog term t(X,L,R) (or nil). As a preparation for drawing the tree, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable, one of them is shown in the illustration below.

layout binary tree

In this layout strategy, the position of a node v is obtained by the following two rules:

  • x(v) is equal to the position of the node v in the inorder
  • y(v) is equal to the depth of the node v in the tree sequence

In order to store the position of the nodes, we extend the Prolog term representing a node (and its successors) as follows:

% nil represents the empty tree (as usual) % t(W,X,Y,L,R) represents a (non-empty) binary tree with root W "positioned" at (X,Y), and subtrees L and R Write a predicate layout_binary_tree/2 with the following specification:

% layout_binary_tree(T,PT) :- PT is the "positioned" binary tree obtained from the binary tree T. (+,?)

Test your predicate in an appropriate way.

题目很清楚，为二叉树中的每一个节点标记X，Y。X等于中序遍历二叉树时该节点的序号；Y等于该节点所处的深度。

用单元测试描述为：

from python99.btree.p413 import layout_binary_tree def test_layout_binary_tree(): E = 'E' assert layout_binary_tree([E, [E, None, None], [E, None, None]]) == [ ('E', 2, 1), [('E', 1, 2), None, None], [('E', 3, 2), None, None] ]

解题思路

先中序遍历二叉树，标记X。因为节点在X轴上不能重叠，所以需要在遍历过程中共享一个增长序列。即在每一次子树遍历时，传入增长序列，若使用了序列则增长该序列，并将增长后的序列返回，以便传给下一个子树遍历过程。

然后再遍历二叉树一次，标记Y。Y等于节点的深度，根节点深度记为1。从根节点可始遍历时，深度为1。递归遍历左右子树时，深度加1，依此类推。

代码实现：

def layout_binary_tree(t): tree, _ = markX(t, 0) return markY(tree, 1) def markX(t, p): if t is None: return (t, p) left, p = markX(t[1], p) p = p+1 e = (t[0], p) right, p = markX(t[2], p) return [e, left, right],p def markY(t, h): if t is None: return None return [(t[0][0], t[0][1], h), markY(t[1], h+1), markY(t[2], h+1)]

results matching ""

    No results matching ""