Python已知后序遍历和中序遍历，求先序遍历

步调一：树的构建

字典

1. def createTree(arr1,arr2,tree):
2.     if len(arr1)==0 and len(arr2)==0 :return
3.     root = len(arr1)-1
4.     # print(arr1[root],root)
5.     flag = arr2.index(arr1[root])
6.     # print(flag)
7.     len_right = len(arr2)-flag-1
8.     len_left = flag
9.     if len(arr2[:flag])>=1:
10.         lchild = arr1[flag-1]
11.     else:
12.         lchild = None
14.     if len(arr2[flag+1:])>=1:
15.         rchild = arr1[root-1]
16.     else:
17.         rchild = None
18.    
19.     tree[arr1[root]] = {'lchild':None,'rchild':None}
20.     tree[arr1[root]]['lchild'] = lchild
21.     tree[arr1[root]]['rchild'] = rchild
22.    
23.     # print(tree)
24.     # print(arr1[:flag],arr1[len_left:len_left+len_right])
25.     # print(arr2[:flag],arr2[flag+1:])
26.     createTree(arr1[:flag],arr2[:flag],tree) # 左子树
27.     createTree(arr1[len_left:len_left+len_right],arr2[flag+1:],tree) #右子树
29. tree = dict()
30. back = [3,4,2,6,5,1]
31. mid = [3,2,4,1,6,5]
32. createTree(back,mid,tree)

复制代码

1. {1: {'lchild': 2, 'rchild': 5},
2. 2: {'lchild': 3, 'rchild': 4},
3. 3: {'lchild': None, 'rchild': None},
4. 4: {'lchild': None, 'rchild': None},
5. 5: {'lchild': 6, 'rchild': None},
6. 6: {'lchild': None, 'rchild': None}}

复制代码

多级嵌套字典

1. def set_nested_dict_value(d, keys, value):
2.     """
3.     根据键列表设置嵌套字典的值
4.     :param d: 原始字典
5.     :param keys: 键列表
6.     :param value: 要设置的值
7.     """
8.     # 从第一个键开始，逐层深入
9.     for key in keys[:-1]:
10.         # 如果当前键不存在，则创建一个空字典
11.         if key not in d:
12.             d[key] = {}
13.         # 下一层字典
14.         d = d[key]
15.     # 设置最后一个键的值
16.     d[keys[-1]] = value
18. def createTree(arr1,arr2,tree,step):
19.     print('------------------------------------------')
20.     # if len(arr1)==0 and len(arr2)==0 :
21.     #     print('结束')
22.     #     return
24.     root = len(arr1)-1
25.     print(arr1[root],root)
27.     flag = arr2.index(arr1[root])
28.     print(flag)
30.     len_right = len(arr2)-flag-1
31.     len_left = flag
32.     if len(arr2[:flag])>=1:
33.         lchild = arr1[flag-1]
34.     else:
35.         lchild = None
37.     if len(arr2[flag+1:])>=1:
38.         rchild = arr1[root-1]
39.     else:
40.         rchild = None
41.         
42.     tmp = dict()
43.     tmp['root'] = arr1[root]
44.     if tmp['root']!= None:
45.         tmp['lchild'] = {'root':lchild,'lchild':None,'rchild':None} if lchild != None else None
46.         tmp['rchild'] = {'root':rchild,'lchild':None,'rchild':None} if rchild != None else None
47.     print('tree',tree)
48.     print('step',step)
50.     if tree==dict():
51.         tree.update(tmp)
52.     else:
53.         set_nested_dict_value(tree, step, tmp)
54.    
56.     # print(tree)
57.     # print(arr1[:flag],arr1[len_left:len_left+len_right])
58.     # print(arr2[:flag],arr2[flag+1:])
59.     # if len(arr1[:flag])>0 and len(arr2[:flag])>0:
60.     #     createTree(arr1[:flag],arr2[:flag],tree,step+['lchild']) # 左子树
61.     # if len(arr1[len_left:len_left+len_right])>0 and len(arr2[flag+1:])>0:
62.     #     createTree(arr1[len_left:len_left+len_right],arr2[flag+1:],tree,step+['rchild']) #右子树
63.     # 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:
64.     #     print('chu')
65.     #     print(tree)
67.     left_mid = arr2[:flag]
68.     right_mid = arr2[flag+1:]
70.     left_back = arr1[:flag]
71.     right_back = arr1[len_left:len_left+len_right]
72.    
73.     print(tree)
74.     print(left_back,right_back)
75.     print(left_mid,right_mid)
76.     if len(left_back)>0 and len(left_mid)>0:
77.         createTree(left_back,left_mid,tree,step+['lchild']) # 左子树
78.     if len(right_back)>0 and len(right_mid)>0:
79.         createTree(right_back,right_mid,tree,step+['rchild']) #右子树
80.     if len(left_back)==0 and len(left_mid)==0 and len(right_back)==0 and len(right_mid)==0:
81.         print('chu')
82.         print(tree)
85. tree = dict()
87. back = [3,4,2,6,5,1]
88. mid = [3,2,4,1,6,5]
90. createTree(back,mid,tree,[])
91. tree

复制代码

简化

1. def set_nested_dict_value(d, keys, value):
2.     """
3.     根据键列表设置嵌套字典的值
4.     :param d: 原始字典
5.     :param keys: 键列表
6.     :param value: 要设置的值
7.     """
8.     # 从第一个键开始，逐层深入
9.     for key in keys[:-1]:
10.         # 如果当前键不存在，则创建一个空字典
11.         if key not in d:
12.             d[key] = {}
13.         # 下一层字典
14.         d = d[key]
15.     # 设置最后一个键的值
16.     d[keys[-1]] = value
18. def createTree(arr1,arr2,tree,step):
20.     root = len(arr1)-1
22.     flag = arr2.index(arr1[root])
24.     len_right = len(arr2)-flag-1
25.     len_left = flag
27.     tmp = {'root':arr1[root],'lchild':None,'rchild':None}
29.     if tree==dict():
30.         tree.update(tmp)
31.     else:
32.         set_nested_dict_value(tree, step, tmp)
33.    
35.     left_mid = arr2[:flag]
36.     right_mid = arr2[flag+1:]
38.     left_back = arr1[:flag]
39.     right_back = arr1[len_left:len_left+len_right]
40.    
42.     if len(left_back)>0 and len(left_mid)>0:
43.         createTree(left_back,left_mid,tree,step+['lchild']) # 左子树
44.     if len(right_back)>0 and len(right_mid)>0:
45.         createTree(right_back,right_mid,tree,step+['rchild']) #右子树
48. tree = dict()
50. back = [3,4,2,6,5,1]
51. mid = [3,2,4,1,6,5]
53. createTree(back,mid,tree,[])
54. tree

复制代码

1. {
2.         'root': 1,
3.         'lchild': {
4.                 'root': 2,
5.                  'lchild': {'root': 3, 'lchild': None, 'rchild': None},
6.                  'rchild': {'root': 4, 'lchild': None, 'rchild': None}},
7.         'rchild': {
8.                 'root': 5,
9.                 'lchild': {'root': 6, 'lchild': None, 'rchild': None},
10.                 'rchild': None}
11.   }

复制代码

步调二：先序遍历

1. def preOrder(tree):
2.    
3.     print(tree['root'])
4.     if tree['lchild']:
5.         preOrder(tree['lchild'])
6.     if tree['rchild']:
7.         preOrder(tree['rchild'])
8. preOrder(tree)

复制代码

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。