实现django评论树使用了三种方式
缺点：每次查找parent_id的时候都要在ret所有的元素里面找一遍，找不到再在元素的children中寻找，一直找到为止
comment_list = [ {‘id‘: 1, ‘content‘: ‘Python最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 2, ‘content‘: ‘Java最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 3, ‘content‘: ‘PHP最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 4, ‘content‘: ‘你最牛逼‘, ‘user‘: ‘大王‘, ‘parent_id‘: 1}, {‘id‘: 5, ‘content‘: ‘我最牛逼‘, ‘user‘: ‘张三‘, ‘parent_id‘: 1}, {‘id‘: 6, ‘content‘: ‘你最牛逼‘, ‘user‘: ‘李四‘, ‘parent_id‘: 4}, {‘id‘: 7, ‘content‘: ‘你们都是垃圾...‘, ‘user‘: ‘王老五‘, ‘parent_id‘: 2}, {‘id‘: 8, ‘content‘: ‘给我点赞哦...‘, ‘user‘: ‘赵老六‘, ‘parent_id‘: 3}, {‘id‘: 9, ‘content‘: ‘什么东西啊...‘, ‘user‘: ‘小李‘, ‘parent_id‘: 8}, {‘id‘: 10, ‘content‘: ‘见到你女友，交定你朋友...‘, ‘user‘: ‘张三‘, ‘parent_id‘: None}, {‘id‘: 11, ‘content‘: ‘大家好，我是大胖...‘, ‘user‘: ‘李四‘, ‘parent_id‘: 6}, ] #评论列表的生成 #第一种方式基本递归,缺点每次查找都需要在ret所有的元素都找一遍，找不到在从儿子里面找一遍 #在在不到在在孙子里面找一遍，知道找到为止。重复寻找。 class Node: comment_list = [ {‘id‘: 1, ‘content‘: ‘Python最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 2, ‘content‘: ‘Java最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 3, ‘content‘: ‘PHP最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 4, ‘content‘: ‘你最牛逼‘, ‘user‘: ‘大王‘, ‘parent_id‘: 1}, {‘id‘: 5, ‘content‘: ‘我最牛逼‘, ‘user‘: ‘张三‘, ‘parent_id‘: 1}, {‘id‘: 6, ‘content‘: ‘你最牛逼‘, ‘user‘: ‘李四‘, ‘parent_id‘: 4}, {‘id‘: 7, ‘content‘: ‘你们都是垃圾...‘, ‘user‘: ‘王老五‘, ‘parent_id‘: 2}, {‘id‘: 8, ‘content‘: ‘给我点赞哦...‘, ‘user‘: ‘赵老六‘, ‘parent_id‘: 3}, {‘id‘: 9, ‘content‘: ‘什么东西啊...‘, ‘user‘: ‘小李‘, ‘parent_id‘: 8}, {‘id‘: 10, ‘content‘: ‘见到你女友，交定你朋友...‘, ‘user‘: ‘张三‘, ‘parent_id‘: None}, {‘id‘: 11, ‘content‘: ‘大家好，我是大胖...‘, ‘user‘: ‘李四‘, ‘parent_id‘: 6}, ] #递归 def digui(ret,row): for rt in ret: if rt[‘id‘] == row[‘parent_id‘]: row[‘children‘] =[] rt[‘children‘].append(row) return #ret= [ # {‘id‘: 1, ‘content‘: ‘Python最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None,‘children‘;[ # {‘id‘: 4, ‘content‘: ‘你最牛逼‘, ‘user‘: ‘大王‘, ‘parent_id‘: 1}, # {‘id‘: 5, ‘content‘: ‘我最牛逼‘, ‘user‘: ‘张三‘, ‘parent_id‘: 1}, # ]}, # {‘id‘: 2, ‘content‘: ‘Java最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None,‘children‘;[]}, # {‘id‘: 3, ‘content‘: ‘PHP最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None,‘children‘;[]}, # ] # {‘id‘: 6, ‘content‘: ‘你最牛逼‘, ‘user‘: ‘李四‘, ‘parent_id‘: 4}, else: Node.digui(rt[‘children‘],row) # @property def create_tree(self,comment_list): ret = [] for row in comment_list: if not row[‘parent_id‘]: # None row[‘children‘] = [] ret.append(row) # [ # {‘id‘: 1, ‘content‘: ‘Python最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None,‘children‘;[]}, # {‘id‘: 2, ‘content‘: ‘Java最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None,‘children‘;[]}, # {‘id‘: 3, ‘content‘: ‘PHP最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None,‘children‘;[]}, # ] else:#是回复的某个评论 #for i in ret: # if row[‘parent_id‘] == i[‘id‘]: # i[‘children‘].append(row) #二级评论实现 # else: # 找三层 Node.digui(ret,row) return ret #第一种执行 # print(Node().create_tree(comment_list))
缺点是查找的复杂度没有第一种多，但是每次找parent_id还是需要comment_list中全部找一遍，并且还有在comment_list中添加元素，在ret中引用第一层的元素会增加内存的消耗。
#第二种查找方式，字典列表的引用方式 comment_list = [ {‘id‘: 1, ‘content‘: ‘Python最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 2, ‘content‘: ‘Java最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 3, ‘content‘: ‘PHP最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 4, ‘content‘: ‘你最牛逼‘, ‘user‘: ‘大王‘, ‘parent_id‘: 1}, {‘id‘: 5, ‘content‘: ‘我最牛逼‘, ‘user‘: ‘张三‘, ‘parent_id‘: 1}, {‘id‘: 6, ‘content‘: ‘你最牛逼‘, ‘user‘: ‘李四‘, ‘parent_id‘: 4}, {‘id‘: 7, ‘content‘: ‘你们都是垃圾...‘, ‘user‘: ‘王老五‘, ‘parent_id‘: 2}, {‘id‘: 8, ‘content‘: ‘给我点赞哦...‘, ‘user‘: ‘赵老六‘, ‘parent_id‘: 3}, {‘id‘: 9, ‘content‘: ‘什么东西啊...‘, ‘user‘: ‘小李‘, ‘parent_id‘: 8}, {‘id‘: 10, ‘content‘: ‘见到你女友，交定你朋友...‘, ‘user‘: ‘张三‘, ‘parent_id‘: None}, {‘id‘: 11, ‘content‘: ‘大家好，我是大胖...‘, ‘user‘: ‘李四‘, ‘parent_id‘: 6}, ] ret = [] for row in comment_list: row.update({‘children‘:[]}) for item in comment_list: current_row = item current_row_parent_id = current_row[‘parent_id‘] if not current_row_parent_id: ret.append(item) else: for r in comment_list: if r[‘id‘] == current_row_parent_id: r[‘children‘].append(item) #把有parent_id的数据加入到comment_list对应ID的chilren列表中 #而不是加入到rent中，因为是引用型ret中指向的内存地址是一致的 #缺点，当有不为空的parent_id的元素时，需要找comment_list中找一遍和parent_id相等的ID值，效率比递归的comment_list自身 #和子元素都找一遍的效率高，还有在comment_list中添加元素，在ret中引用第一层的元素会增加内存的消耗。 # print(ret) # print(comment_list)
基于字典的查找方式
#第三种基于哈希查找，字典存储时会调用Python内部散列函数，将键(Key)作为参数进行转换，得到一个唯一的一个地址，然后将值 #存入这个地址中，所字典的查找也是基于哈希的,所以查找很快速 comment_list = [ {‘id‘: 1, ‘content‘: ‘Python最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 2, ‘content‘: ‘Java最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 3, ‘content‘: ‘PHP最牛逼‘, ‘user‘: ‘小李‘, ‘parent_id‘: None}, {‘id‘: 4, ‘content‘: ‘你最牛逼‘, ‘user‘: ‘大王‘, ‘parent_id‘: 1}, {‘id‘: 5, ‘content‘: ‘我最牛逼‘, ‘user‘: ‘张三‘, ‘parent_id‘: 1}, {‘id‘: 6, ‘content‘: ‘你最牛逼‘, ‘user‘: ‘李四‘, ‘parent_id‘: 4}, {‘id‘: 7, ‘content‘: ‘你们都是垃圾...‘, ‘user‘: ‘王老五‘, ‘parent_id‘: 2}, {‘id‘: 8, ‘content‘: ‘给我点赞哦...‘, ‘user‘: ‘赵老六‘, ‘parent_id‘: 3}, {‘id‘: 9, ‘content‘: ‘什么东西啊...‘, ‘user‘: ‘小李‘, ‘parent_id‘: 8}, {‘id‘: 10, ‘content‘: ‘见到你女友，交定你朋友...‘, ‘user‘: ‘张三‘, ‘parent_id‘: None}, {‘id‘: 11, ‘content‘: ‘大家好，我是大胖...‘, ‘user‘: ‘李四‘, ‘parent_id‘: 6}, ] #创建字典 ret = [] comment_list_dict = {} for row in comment_list: row.update({‘children‘:[]}) comment_list_dict[row[‘id‘]] = row print(comment_list_dict) for item in comment_list: parent_row = comment_list_dict.get(item[‘parent_id‘]) if not parent_row: ret.append(item) else: parent_row[‘children‘].append(item) print(ret)
原文：https://www.cnblogs.com/wuzhibinsuib/p/12879879.html
