以特定格式打印二叉树
问题描述:
def str_tree(atree,indent_char ='.',indent_delta=2):
def str_tree_1(indent,atree):
if atree == None:
return ''
else:
answer = ''
answer += str_tree_1(indent+indent_delta,atree.right)
answer += indent*indent_char+str(atree.value)+'\n'
answer += str_tree_1(indent+indent_delta,atree.left)
return answer
return str_tree_1(0,atree)
def build_balanced_bst(l):
d = []
if len(l) == 0:
return None
else:
mid = (len(l)-1)//2
if mid >= 1:
d.append(build_balanced_bst(l[:mid]))
d.append(build_balanced_bst(l[mid:]))
else:
return d
build_balanced_bst(l)接收按升序排序的唯一值列表。它返回一个对平衡二叉搜索树根的引用。例如,调用build_ballanced_bst(名单(irange(1,10))返回高度为3的二叉搜索树,将打印为:以特定格式打印二叉树
......10
....9
..8
......7
....6
5
......4
....3
..2
....1
的str_tree函数打印什么build_balanced_bst函数返回
我在build_balanced_bst(L)功能配合使用,使其适用于str_tree功能我在列表中为根的价值所使用的中间值 但是当我调用该函数如下的方式:。
l = list(irange(1,10))
t = build_balanced_bst(l)
print('Tree is\n',str_tree(t),sep='')
它不打印任何东西。有人可以帮我修复我的build_balanced_bst(l)函数吗?
答
保持原来的str_tree
方法,下面是其余的代码。
class Node:
"""Represents a single node in the tree"""
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def build_balanced_bst(lt):
"""
Find the middle element in the sorted list
and make it root.
Do same for left half and right half recursively.
"""
if len(lt) == 1:
return Node(lt[0])
if len(lt) == 0:
return None
mid = (len(lt)-1)//2
left = build_balanced_bst(lt[:mid])
right = build_balanced_bst(lt[mid+1:])
root = Node(lt[mid], left, right)
return root
ordered_list = list(range(1,11))
bst=build_balanced_bst(ordered_list)
bst_repr = str_tree(bst)
print(bst_repr)
输出出来,如下所示:
......10
....9
..8
......7
....6
5
......4
....3
..2
....1