[已解决]关于二叉搜索树

18813034116

各位前辈好，我又来提问了，问题是将一个数组转为二叉搜索树，关于数据结构的概念我不是很熟，所以将我自认为的答案发上来，帮我看看我关于这个问题的理解以及我的答案是否正确

1. #coding=utf-8
   
2. def compare(num1,num2,dict_g):
   
3.     '''
   
4.     用于比较num1和num2的大小，如果num2大于num1，且num1的右子节点不存在(不为None)则将num2设定为num1的右子节点；如果num2大于
   
5.     num1,但是num1的左子节点存在，就以num1的左子节点作为新num1进行比较；如果num2小于num1与上边同理
   
6. 
   
7.     :param num1: 要比较的根节点
   
8.     :param num2: 要比较的子元素
   
9.     :param dict_g: 模拟二叉树的字典
   
10.     :return:
    
11.     '''
    
12.     temp_r=dict_g.setdefault(num1,[None,None])[1]#右分支
    
13.     temp_l=dict_g.setdefault(num1,[None,None])[0]#左分支
    
14.     if num2>num1 and temp_r == None:
    
15.         dict_g[num1][1]=num2
    
16.     elif num2<num1 and temp_l==None:
    
17.         dict_g[num1][0]=num2
    
18.     elif num2>num1 and temp_r !=None:
    
19.         compare(temp_r,num2,dict_g)
    
20.     else:
    
21.         compare(temp_l,num2,dict_g)
    
22.     return dict_g
    
23. def make_tree():
    
24.     '''
    
25.     用字典模拟二叉树，用数组里的元素作为字典的键(节点)，每个键映射一个有两个元素的列表，两个元素分别表示左节点和右节点,
    
26.     通过遍历数组元素和调用compare函数完成二叉树的模拟
    
27. 
    
28.     array:要转为二叉树的数组
    
29.     dict_result:模拟二叉树的字典
    
30.     :return:
    
31.     '''
    
32.     array=[3,5,67,8,2,23]
    
33.     dict_result={array[0]:[None,None]}
    
34.     for i in array[1:]:
    
35.         dict_result=compare(array[0],i,dict_result)
    
36.         #print dict_result
    
37.     for key in dict_result:#将结果输出
    
38.         print '%d-->%s'%(key,dict_result[key])
    
39. make_tree()
    
40. 
    

复制代码

最佳答案

月排行榜 / 总排行榜

SixPy

2017-8-7 23:35:18

http://www.cs.usfca.edu/~galles/visualization/BST.html

跳转到最佳答案楼层

SixPy

http://www.cs.usfca.edu/~galles/visualization/BST.html

18813034116

SixPy 发表于 2017-8-7 23:35

我知道了，谢谢你