Binary search trees
Use the predicate add/3, developed in chapter 4 of the course, to write a predicate to construct a binary search tree from a list of integer numbers. Example: ?- construct([3,2,5,7,1],T). T = t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))
Then use this predicate to test the solution of the problem P56. Example: ?- test_symmetric([5,3,18,1,4,12,21]). Yes ?- test_symmetric([3,2,5,7,4]). No
用单元测试描述为：
from python99.btree.p404 import construct
def test_construct():
assert construct([3, 2, 5, 7, 1]) == [
3, [2, [1, None, None], None], [5, None, [7, None, None]]
]
二分搜索树的定义是：
- 对于树中任意节点﹐若存在左子节点则左子节点的值必小于节点本身的值
- 若存在右子节点，则右子节点的值必大于节点本身的值。
二分搜索树的构造成空树开始。当插入一个新值时，与根节点值比较：
- 若根节点为空，则插入为根节点
- 若新值小于根节点的值，则插入左子树
- 若新值大于根节点的值，则插入右子树
代码实现：
def construct(nums):
tree = None
for num in nums:
tree = add(tree, num)
return tree
def add(tree, e):
if tree is None:
return [e, None, None]
if e < tree[0]:
return[tree[0], add(tree[1], e), tree[2]]
else:
return [tree[0], tree[1], add(tree[2], e)]