算法的威力:利用python引用赋值原理实现递归建树

在程序开发过程中，经常涉及到数据的传递，在数据传递使用过程中，可能会发生数据被修改的问题。为了防止数据被修改，就需要在传递一个副本，即使副本被修改，也不会影响原数据的使用。为了生成这个副本，就产生了拷贝。

在 python 中一切皆对像，所有数据都被当成对像处理。

而对像又分为可变对像和不可变对像。

在 Python 中，int, str, tuple 等类型的数据都是不可变对象，不可变对象的特性是数字不可被修改。比如你不能把1赋值给2:

2=1

而可变对像是相对于不可变对像而言的，可变对像的数据可以被修改，比如list, set, dict等类型。

在 Python 中，如果你想拷贝一个变量时，如果你拷贝的是一个可变对像的话，本质上你只是拷贝了一份数据对像的引用而已。

利用这个原理我们可以利用列表这个可变对像，建立它各个元素之间的上下级引用关系，从而最终实现递归效果。

说再多不看一行代码直观，上图：

原码如下:

import time

def build_tree_c(data):

"""建树:找儿子算法

1万层节点耗时(秒):7.0288989543914795

"""

for index, i in enumerate(data):

for j in data:

if i["id"]==j["parentId"]:

if "children" not in data[index].keys():

data[index]["children"] = []

data[index]["children"].append(j)

res = [i for i in data if i["parentId"]==0]

return res

def build_tree_p(data):

"""建树:找爸爸算法

1万层节点耗时(秒):0.005019187927246094

"""

# 建立一个 id 对 index 的字典

res = []

c_dict ={}

for index, i in enumerate(data):

c_dict[i["id"]] = index

# 用本节点的 parentId 通过字典找到父节点的index

for i in data:

if i['parentId'] == 0:

res.append(i)

else:

papa = data[c_dict[i["parentId"]]]

if "children" not in papa.keys():

papa["children"] = []

papa["children"].append(i)

return res

# 创建一个1万个节点: [{'id': 0, 'parentId': 1},

# {'id': 1, 'parentId': 2},

# {'id': 2, 'parentId': 3}, ...{'id': 9999, 'parentId': 10000}]

data = [{"id": i+1,"parentId": i} for i in range(10000)]

data.append({"id": 10,"parentId": 0})

data.append({"id": 11,"parentId": 0})

# 将这1万个节点建树:

t1 = time.time()

# res = build_tree_c(data)

res = build_tree_p(data)

t2 = time.time()

st = t2-t1

print("Start time:\t%s\nStop time:\t%s\nElapsed time:\t%s" % (t1, t2, st))