Dotstring representation of binary tree
题目
We consider again binary trees with nodes that are identified by single lower-case letters, as in the example of problem 4.16. Such a tree can be represented by the preorder sequence of its nodes in which dots (.) are inserted where an empty subtree (nil) is encountered during the tree traversal. For example, the tree shown in problem 4.16 is represented as 'abd..e..c.fg...'. First, try to establish a syntax (BNF or syntax diagrams) and then write a predicate tree_dotstring/2 which does the conversion in both directions. Use difference lists.
用单元测试描述为：
from python99.btree.p418 import tree_dotstring
def test_tree_dotstring():
assert tree_dotstring(['a', ['b', ['d', None, None], ['e', None, None]], [
'c', None, ['f', ['g', None, None], None]]]) == 'abd..e..c.fg...'
解题思路
先建立dotstring的BNF。
<tree> ::= . | <letter> <tree> <tree>
一棵树可能是空树也可能不是空树。当为空树时表示为.。当不为空树时，由根节点<letter>和左右子树组成。
Dotstring的编码很简单。前序遍历二叉树，遇到节点即输出节点字符，遇到空树则输出.。
代码实现：
def tree_dotstring(t):
if t is None:
return '.'
return t[0] + tree_dotstring(t[1]) + tree_dotstring(t[2])