Python已知后序遍历和中序遍历，求先序遍历
步调一：树的构建字典
def createTree(arr1,arr2,tree):
if len(arr1)==0 and len(arr2)==0 :return
root = len(arr1)-1
# print(arr1,root)
flag = arr2.index(arr1)
# print(flag)
len_right = len(arr2)-flag-1
len_left = flag
if len(arr2[:flag])>=1:
lchild = arr1
else:
lchild = None
if len(arr2)>=1:
rchild = arr1
else:
rchild = None
tree] = {'lchild':None,'rchild':None}
tree]['lchild'] = lchild
tree]['rchild'] = rchild
# print(tree)
# print(arr1[:flag],arr1)
# print(arr2[:flag],arr2)
createTree(arr1[:flag],arr2[:flag],tree) # 左子树
createTree(arr1,arr2,tree) #右子树
tree = dict()
back =
mid =
createTree(back,mid,tree)
{1: {'lchild': 2, 'rchild': 5},
2: {'lchild': 3, 'rchild': 4},
3: {'lchild': None, 'rchild': None},
4: {'lchild': None, 'rchild': None},
5: {'lchild': 6, 'rchild': None},
6: {'lchild': None, 'rchild': None}}
多级嵌套字典
def set_nested_dict_value(d, keys, value):
"""
根据键列表设置嵌套字典的值
:param d: 原始字典
:param keys: 键列表
:param value: 要设置的值
"""
# 从第一个键开始，逐层深入
for key in keys[:-1]:
# 如果当前键不存在，则创建一个空字典
if key not in d:
d = {}
# 下一层字典
d = d
# 设置最后一个键的值
d] = value
def createTree(arr1,arr2,tree,step):
print('------------------------------------------')
# if len(arr1)==0 and len(arr2)==0 :
# print('结束')
# return
root = len(arr1)-1
print(arr1,root)
flag = arr2.index(arr1)
print(flag)
len_right = len(arr2)-flag-1
len_left = flag
if len(arr2[:flag])>=1:
lchild = arr1
else:
lchild = None
if len(arr2)>=1:
rchild = arr1
else:
rchild = None
tmp = dict()
tmp['root'] = arr1
if tmp['root']!= None:
tmp['lchild'] = {'root':lchild,'lchild':None,'rchild':None} if lchild != None else None
tmp['rchild'] = {'root':rchild,'lchild':None,'rchild':None} if rchild != None else None
print('tree',tree)
print('step',step)
if tree==dict():
tree.update(tmp)
else:
set_nested_dict_value(tree, step, tmp)
# print(tree)
# print(arr1[:flag],arr1)
# print(arr2[:flag],arr2)
# if len(arr1[:flag])>0 and len(arr2[:flag])>0:
# createTree(arr1[:flag],arr2[:flag],tree,step+['lchild']) # 左子树
# if len(arr1)>0 and len(arr2)>0:
# createTree(arr1,arr2,tree,step+['rchild']) #右子树
# if len(arr1[:flag])==0 and len(arr2[:flag])==0 and len(arr1)==0 and len(arr2)==0:
# print('chu')
# print(tree)
left_mid = arr2[:flag]
right_mid = arr2
left_back = arr1[:flag]
right_back = arr1
print(tree)
print(left_back,right_back)
print(left_mid,right_mid)
if len(left_back)>0 and len(left_mid)>0:
createTree(left_back,left_mid,tree,step+['lchild']) # 左子树
if len(right_back)>0 and len(right_mid)>0:
createTree(right_back,right_mid,tree,step+['rchild']) #右子树
if len(left_back)==0 and len(left_mid)==0 and len(right_back)==0 and len(right_mid)==0:
print('chu')
print(tree)
tree = dict()
back =
mid =
createTree(back,mid,tree,[])
tree
简化
def set_nested_dict_value(d, keys, value):
"""
根据键列表设置嵌套字典的值
:param d: 原始字典
:param keys: 键列表
:param value: 要设置的值
"""
# 从第一个键开始，逐层深入
for key in keys[:-1]:
# 如果当前键不存在，则创建一个空字典
if key not in d:
d = {}
# 下一层字典
d = d
# 设置最后一个键的值
d] = value
def createTree(arr1,arr2,tree,step):
root = len(arr1)-1
flag = arr2.index(arr1)
len_right = len(arr2)-flag-1
len_left = flag
tmp = {'root':arr1,'lchild':None,'rchild':None}
if tree==dict():
tree.update(tmp)
else:
set_nested_dict_value(tree, step, tmp)
left_mid = arr2[:flag]
right_mid = arr2
left_back = arr1[:flag]
right_back = arr1
if len(left_back)>0 and len(left_mid)>0:
createTree(left_back,left_mid,tree,step+['lchild']) # 左子树
if len(right_back)>0 and len(right_mid)>0:
createTree(right_back,right_mid,tree,step+['rchild']) #右子树
tree = dict()
back =
mid =
createTree(back,mid,tree,[])
tree
{
'root': 1,
'lchild': {
'root': 2,
'lchild': {'root': 3, 'lchild': None, 'rchild': None},
'rchild': {'root': 4, 'lchild': None, 'rchild': None}},
'rchild': {
'root': 5,
'lchild': {'root': 6, 'lchild': None, 'rchild': None},
'rchild': None}
}
步调二：先序遍历
def preOrder(tree):
print(tree['root'])
if tree['lchild']:
preOrder(tree['lchild'])
if tree['rchild']:
preOrder(tree['rchild'])
preOrder(tree)
1
2
3
4
5
6
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]