A string representation of binary trees
题目
Somebody represents binary trees as strings of the following type (see example):
a(b(d,e),c(,f(g,)))
a Write a Prolog predicate which generates this string representation, if the tree is given as usual (as nil or t(X,L,R) term). Then write a predicate which does this inverse; i.e. given the string representation, construct the tree in the usual form. Finally, combine the two predicates in a single predicate tree_string/2 which can be used in both directions.
b) Write the same predicate tree_string/2 using difference lists and a single predicate tree_dlist/2 which does the conversion between a tree and a difference list in both directions.
For simplicity, suppose the information in the nodes is a single letter and there are no spaces in the string.
用单元测试描述为：
from python99.btree.p416 import tree_to_string, string_to_tree, tree_string
def test_tree_string():
E = 'E'
assert tree_string(
[E, [E, None, None], [E, [E, None, None], None]]) == 'E(E,E(E,))'
r, _ = tree_string('E(E,E(E,))')
assert r == [E, [E, None, None], [E, [E, None, None], None]]
def test_tree_to_string():
E = 'E'
assert tree_to_string(
[E, [E, None, None], [E, [E, None, None], None]]) == 'E(E,E(E,))'
def test_string_to_tree():
E = 'E'
r, _ = string_to_tree('E(E,E(E,))')
assert r == [E, [E, None, None], [E, [E, None, None], None]]
r2, _ = string_to_tree('E(E(E,E),E)')
assert r2 == [E, [E, [E, None, None], [E, None, None]], [E, None, None]]
解题思路
本题分为两部份:
- 实现二叉树在形式
[E,left,right]和字符串形式e(left,right)之门的转换。本题可分为两步：
- 将形为
[X, L, R]的二叉树转换为形为a(b(d,e),c)的字符串；
- 将形为
a(b(d,e),c)的字符串转换为形为[X, L, R]的二叉树。
- 使用字符替换实现二叉树在形式
[E,left,right]和字符串形式e(left,right)之门的转换。Python是数据程序分离的，不像Prolog。所以此方法在Python中无法实现
二叉树转换为字符串
递归遍历二叉树，
- 空树转换为空字符串
- 叶子节点转换为形如
a的字符串，a为叶子节点本身的值。叶子节点是不拥有任何子节点的节点
- 内部节点转换为形如
a(l,r)的字符串，a为节点本身的值，l为左子树转换后的字符串，r为右子树转换后的字符串。内部节点是拥有一个或两个子节点的节点
代码实现：
def tree_to_string(t):
if t is None:
return ''
if t[1] is None and t[2] is None:
return t[0]
return t[0]+'('+tree_to_string(t[1])+','+tree_to_string(t[2])+')'
字符串转换为二叉树
假定输入的字符串包含一个完整的二叉树。一棵完整的二叉树有以下形式：
- 只有一个节点，字符串形式为
a
- 只拥有一个子树，字符串形式为
a(<left>,)。<left>是二叉树
- 拥有两棵子树，字符串形式为
a(<left>,<right>)。<left>和<right>都是二叉树
从字符串中解出一棵二叉树，对子树递归套用了相同规则。
代码实现：
def string_to_tree(s):
e = s[0]
s = s[1:]
if e == ')':
return None, s
if len(s) == 0:
return [e, None, None], s
if s[0] == ',':
return [e, None, None], s
if s[0] == ')':
return [e, None, None], s
s = s[1:]
left, s = string_to_tree(s)
s = s[1:]
right, s = string_to_tree(s)
s = s[1:]
return [e, left, right], s
完整代码
def tree_string(ts):
if type(ts) is str:
return string_to_tree(ts)
else:
return tree_to_string(ts)
def tree_to_string(t):
if t is None:
return ''
if t[1] is None and t[2] is None:
return t[0]
return t[0]+'('+tree_to_string(t[1])+','+tree_to_string(t[2])+')'
def string_to_tree(s):
e = s[0]
s = s[1:]
if e == ')':
return None, s
if len(s) == 0:
return [e, None, None], s
if s[0] == ',':
return [e, None, None], s
if s[0] == ')':
return [e, None, None], s
s = s[1:]
left, s = string_to_tree(s)
s = s[1:]
right, s = string_to_tree(s)
s = s[1:]
return [e, left, right], s