步骤一：树的构建
字典
def createTree(arr1,arr2,tree):if len(arr1)==0 and len(arr2)==0 :returnroot = len(arr1)-1# print(arr1[root],root)flag = arr2.index(arr1[root])# print(flag)len_right = len(arr2)-flag-1len_left = flagif len(arr2[:flag])>=1:lchild = arr1[flag-1]else:lchild = Noneif len(arr2[flag+1:])>=1:rchild = arr1[root-1]else:rchild = Nonetree[arr1[root]] = {'lchild':None,'rchild':None}tree[arr1[root]]['lchild'] = lchildtree[arr1[root]]['rchild'] = rchild# print(tree)# print(arr1[:flag],arr1[len_left:len_left+len_right])# print(arr2[:flag],arr2[flag+1:])createTree(arr1[:flag],arr2[:flag],tree) # 左子树createTree(arr1[len_left:len_left+len_right],arr2[flag+1:],tree) #右子树tree = dict()
back = [3,4,2,6,5,1]
mid = [3,2,4,1,6,5]
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[key] = {}# 下一层字典d = d[key]# 设置最后一个键的值d[keys[-1]] = valuedef createTree(arr1,arr2,tree,step):print('------------------------------------------')# if len(arr1)==0 and len(arr2)==0 :# print('结束')# returnroot = len(arr1)-1print(arr1[root],root)flag = arr2.index(arr1[root])print(flag)len_right = len(arr2)-flag-1len_left = flagif len(arr2[:flag])>=1:lchild = arr1[flag-1]else:lchild = Noneif len(arr2[flag+1:])>=1:rchild = arr1[root-1]else:rchild = Nonetmp = dict()tmp['root'] = arr1[root]if tmp['root']!= None:tmp['lchild'] = {'root':lchild,'lchild':None,'rchild':None} if lchild != None else Nonetmp['rchild'] = {'root':rchild,'lchild':None,'rchild':None} if rchild != None else Noneprint('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[len_left:len_left+len_right])# print(arr2[:flag],arr2[flag+1:])# if len(arr1[:flag])>0 and len(arr2[:flag])>0:# createTree(arr1[:flag],arr2[:flag],tree,step+['lchild']) # 左子树# if len(arr1[len_left:len_left+len_right])>0 and len(arr2[flag+1:])>0:# createTree(arr1[len_left:len_left+len_right],arr2[flag+1:],tree,step+['rchild']) #右子树# if len(arr1[:flag])==0 and len(arr2[:flag])==0 and len(arr1[len_left:len_left+len_right])==0 and len(arr2[flag+1:])==0:# print('chu')# print(tree)left_mid = arr2[:flag]right_mid = arr2[flag+1:]left_back = arr1[:flag]right_back = arr1[len_left:len_left+len_right]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 = [3,4,2,6,5,1]
mid = [3,2,4,1,6,5]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[key] = {}# 下一层字典d = d[key]# 设置最后一个键的值d[keys[-1]] = valuedef createTree(arr1,arr2,tree,step):root = len(arr1)-1flag = arr2.index(arr1[root])len_right = len(arr2)-flag-1len_left = flagtmp = {'root':arr1[root],'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[flag+1:]left_back = arr1[:flag]right_back = arr1[len_left:len_left+len_right]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 = [3,4,2,6,5,1]
mid = [3,2,4,1,6,5]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
