Preorder and inorder sequences of binary trees

题目

We consider binary trees with nodes that are identified by single lower-case letters, as in the example of problem 4.16.

a) Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a given binary tree, respectively. The results should be atoms, e.g. 'abdecfg' for the preorder sequence of the example in problem 4.16.

b) Can you use preorder/2 from problem part a) in the reverse direction; i.e. given a preorder sequence, construct a corresponding tree? If not, make the necessary arrangements.

c) If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given, then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job.

d) Solve problems a) to c) using difference lists. Cool! Use the predefined predicate time/1 to compare the solutions.

What happens if the same character appears in more than one node. Try for instance pre_in_tree(aba,baa,T).

解题思路

这个题目包含四个问题：

  • 前序遍历和中序遍历二叉树并按遍历顺序输出节点值
  • 从前序和中序遍历得来的节点序列分别重构二叉树
  • 从前序和中序遍历序列重构唯一的二叉树
  • 使用difference list解决第三个问题

前序遍历和中序遍历二叉树并按遍历顺序输出节点值

前序遍历

前序遍历的规则是：

  • 先访问自身节点
  • 再访问左子树
  • 再访问右子树

举个例子，给定二叉树[a,[b,None,None],[c,None,None]]：

  • 先访问根节点a
  • 再访问左子树[b,None,None]
  • 再访问右子树[c,None,None]

结果得到遍历序列abc。

代码实现：

def preorder(t): if t is None: return '' return t[0]+preorder(t[1])+preorder(t[2])

单元测试：

def test_preorder(): assert preorder(['a', ['b', None, None], ['c', None, None]]) == 'abc'

中序遍历

中序遍历的规则是：

  • 先访问左子树
  • 再访问自身节点
  • 再访问右子树

举个例子，给定二叉树[a,[b,None,None],[c,None,None]]：

  • 先访问左子树[b,None,None]
  • 再访问自身节点a
  • 再访问右子树[c,None,None]

结果得到遍历序列bac。

代码实现：

def inorder(t): if t is None: return '' return inorder(t[1])+t[0]+inorder(t[2])

单元测试：

def test_inorder(): assert inorder(['a', ['b', None, None], ['c', None, None]]) == 'bac'

从前序和中序遍历得来的节点序列分别重构二叉树

从前序遍历字符序列重构二叉树

从前序遍历序列无法重构唯一的二叉树。对于一个前序遍历序列，其左右子树有多种可能。比如，前序遍历序列abc，其左右子树序列的组合有：

  • `和bc`
  • b和c
  • bc和``

对于同一子树序列，也可能由多个不同子树生成。縂之，对长度大于1的序列，可重构出多个二叉树。

重构过程先把序列拆成自身节点、左子树序列和右子树序列。自身节点拆分法是唯一的，而左右子树序列的拆分法却不是唯一。且每一种子树序列拆分法重构出来的子树也不是唯一的。 这𥚃有两个「不唯一」，字符序列拆分和从字符序列重构二叉树。结果数量就在这两个地方进行了扩展，扩展方式就是完全组合。

代码实现：

def preorder_to_tree(s): if len(s) == 0: return [None] e = s[0] s = s[1:] leftAndRights = [] for i in range(0, len(s)+1): leftAndRights.append([s[:i], s[i:]]) result = [] for leftAndRight in leftAndRights: result = result+[[e, left, right] for left in preorder_to_tree( leftAndRight[0]) for right in preorder_to_tree(leftAndRight[1])] return result

拆分字符序列的时候罗列了所有组合。

for i in range(0, len(s)+1):
    leftAndRights.append([s[:i], s[i:]])

再针对每一组拆分组合，构造所有可能的左右子树，再罗列所有的左右子树组合，得到所有可能的重构二叉树。 二叉树是递归结构，所以重构过程也是递归的。每一层都要拆分字符序列、构造左右子树、罗列所有左右子树组合。

从中序遍历字符序列重构二叉树

从中序遍历字符序列无法重构出唯一的二叉树。对于一个序列，其左子树、自身节点和右子树有多种拆分方法。比如，序列abc，其可以有以下拆分：

  • 左子树`，自身节点a，右子树bc`
  • 左子树a，自身节点b，右子树c
  • 左子树ab，自身节点c，右子树``

对于同一子树序列，也可能由多个不同子树生成。縂之，对长度大于1的序列，可重构出多个二叉树。

重构过程是先把序列拆分为左子树序列、自身节点和右子树序列，再分别构造左右子树。左右子树也是二叉树，所以套用对整树相同的方法。序列拆分会生成多个结果，针对同一个序列构造子树也会生成多个结果。这两个结果集再组合就得到了最终结果，所有符合中序遍历序的的二叉树。

代码实现：

def inorder_to_tree(s): if len(s) == 0: return [None] leftAndEAndRights = [] for i in range(0, len(s)): leftAndEAndRights.append([s[:i], s[i], s[i+1:]]) result = [] for (l, e, r) in leftAndEAndRights: result = result+[[e, left, right] for left in inorder_to_tree(l) for right in inorder_to_tree(r)] return result

拆分序的方法有多种，这𥚃就罗列了所有的：

for i in range(0, len(s)):
    leftAndEAndRights.append([s[:i], s[i], s[i+1:]])

针对每一种序列，重构的二叉树也有多种。且左右子树的组合方式也有多种。

for (l, e, r) in leftAndEAndRights:
    result = result+[[e, left, right]
                         for left in inorder_to_tree(l) for right in inorder_to_tree(r)]

从前序和中序遍历序列重构唯一的二叉树

当同时给定前序遍历和中序遍历序列时，可以重构出唯一的二叉树。

先从前序遍历序列中重构出所有的二叉树‧再从中序遍历序列中重构出所有的二叉树。最后最两个结果集的交集即唯一的二叉树。

代码实现：

def pre_in_tree(p, i): ptree = preorder_to_tree(p) itree = inorder_to_tree(i) trees = [(pt, it) for pt in ptree for it in itree if pt == it] return trees[0][0]

使用difference list解决第三个问题

difference list是Prolog的语言特性，Python不支持

results matching ""

    No results matching ""