树形结构类似于数据结构中的二叉树，如果树形结构比较复杂的话，通过递归的方式查询并不是那么简介，多次 访问数据库查询，对于性能是一个很大的损耗，最近看别人的算法，也就想要写一篇自己总结下，本文主要是在django上面如果集成这个算法，实现无限级分类。
basic classify
上面的例子中，我们列举了一个分类树，这个树一共有三级分类，从网上学到一个前序遍历树模型（The Nesat Set Model），该模型中通过每一层建立水平区间来区分不通的分类，一般上层的区间范围包含下级的区间。
原理如下：
水平区间分布
我们假定上衣分类的水平区间是1-20，那么风衣和T恤的分类在1-20之间分布，同理着装的分类区间应该大于上分区间的宽度（比如0-30）。
下面我们就为各个分类划定一个区间：
水平区间编号
从图中我们可以看到各个分类区间的范围：
| 类型 | 范围 |
|---|---|
| 着装 | 1-12 |
| 上衣 | 2-7 |
| 风衣 | 3-4 |
| T恤 | 5-6 |
| 鞋子 | 8-11 |
| 运动鞋 | 9-10 |
添加一个新分类
假设我们需要添加一个裤子分类，那么裤子属于着装大分类下的二级分类，那么我们直接在区间的左边添加一类：
添加新区后的水平分布
接下来我们想办法来重新调整区间的范围，来为我们新的区间编号。
新区之后的编号变化
首先我们直接找到要添加的新区间的上级区间的最左边界m，然后找到所有的边界大于m的边界，进行统一的+2计算，接着以m+1, m+2作为边界插入新的区间。
删除一个分类
如果要删除一个分类，那么删除的可能是一个大的区间，区间后的所有区间都需要前移等量的一段：
删除一个区间
重排区间边界后：
删除区间后重排
从重排编号后，我们发现如果删除的区间对应的边界是m，n，那么所有大于n的边界都向前移动了n-m+1。
如何遍历一个分类
先来看看鞋子这个分类，鞋子本身是一个二级分类，鞋子下面还有一个三级分类运动鞋，那我们如何根据遍历鞋子这个分类。
- 先得到根结点的左右值（默认根节点的title为”顶级目录”）。
- 查询左右值在根节点的左右值范围内的记录，并且根据左值排序。
- 如果本次记录右值大于前次记录的右值则为平级分类
正常情况下，如果是一个只有两级的树，那么所有的第二季都是平级的，那么向栈中压入一个节点，在下一个节点的时候栈顶会被弹出，继续后面的节点扫描。
比如查询并排序的结果是：
[{'child': u'A', u'id': 14L, 'lft': 1L, 'parent': u'', 'rgt': 14L},
{'child': u'D', u'id': 17L, 'lft': 2L, 'parent': u'A', 'rgt': 5L},
{'child': u'H', u'id': 21L, 'lft': 3L, 'parent': u'D', 'rgt': 4L},
{'child': u'B', u'id': 16L, 'lft': 6L, 'parent': u'A', 'rgt': 13L},
{'child': u'F', u'id': 19L, 'lft': 7L, 'parent': u'B', 'rgt': 8L},
{'child': u'E', u'id': 18L, 'lft': 9L, 'parent': u'B', 'rgt': 12L},
{'child': u'G', u'id': 20L, 'lft': 10L, 'parent': u'E', 'rgt': 11L}]
这种情况下，堆栈的情况如下：
[[u'A', u'D'],
[u'A', u'D', u'H'],
[u'A', u'B'],
[u'A', u'B', u'F'],
[u'A', u'B', u'E'],
[u'A', u'B', u'E', u'G']]
具体是如何弄的，详细的可以参考下面的代码。
Django实例
########################################### signals.py
# -*- coding: utf-8 -*-
from django.db.models import F
from django.db.models.signals import pre_save, post_delete
from django.dispatch import receiver
from core.models import ClosesClass
@receiver(pre_save, sender=ClosesClass)
def handle_save_closes_instance(sender, instance, **kwargs):
"""
make other operation when insert new instance
:param sender:
:param instance:
:param kwargs:
:return:
"""
if not instance.id:
parent = sender.objects.filter(child=instance.parent)
if not parent.exists():
instance.lft = 1
instance.rgt = 2
else:
lft = parent.first().lft
sender.objects.filter(lft__gt=lft).update(lft=F("lft") + 2)
sender.objects.filter(rgt__gt=lft).update(rgt=F("rgt") + 2)
instance.lft = lft + 1
instance.rgt = lft + 2
@receiver(post_delete, sender=ClosesClass)
def handler_delete_instance(sender, instance, **kwargs):
"""
delete redundancy data
:param sender:
:param instance:
:param kwargs:
:return:
"""
lft, rgt = instance.lft, instance.rgt
width = rgt - lft + 1
sender.objects.filter(lft__gt=rgt).update(lft=F("lft") - width)
sender.objects.filter(rgt__gt=rgt).update(rgt=F("rgt") - width)
######################################## models.py
class ClosesClassManager(models.Manager):
def get_queryset(self):
return super(ClosesClassManager, self).get_queryset()
def get_all_leaves_class(self):
"""
获取所有的叶子节点
:return:
"""
return self.get_queryset() \
.filter(rgt=F("lft") + 1) \
.values_list("child", flat=True)
def get_direct_children_of_class(self, parent):
"""
获取直属的二级分类
:param parent: parent class
:return:
"""
return self.get_queryset() \
.filter(parent=parent) \
.order_by("lft") \
.values_list("child", flat=True)
def get_all_class(self):
"""
获取分类树
:return:
"""
# tree
def convert_2_tree(paths):
root = {}
for path in paths:
current_level = root
for part in path:
if part not in current_level:
current_level[part] = {}
current_level = current_level[part]
return root
root_node = self.get_queryset().filter(lft=1).first()
lft, rgt = root_node.lft, root_node.rgt
closes = self.get_queryset().filter(lft__range=[lft, rgt]).order_by("lft").values()
right = path_li = []
for close in closes:
if len(right):
while right[-1]["rgt"] < close["rgt"]:
right = right[:-1]
if len(right):
title_li = [e["child"] for e in right]
path_li.append(title_li + [close["child"]])
right.append(close)
return convert_2_tree(path_li)
class ClosesClass(models.Model):
class Meta:
db_table = "close_class"
verbose_name_plural = u"衣服分类"
# override bulk delete operation
objects = ClosesClassManager()
parent = models.CharField(max_length=128, blank=True, null=True, verbose_name=u"父级分类")
child = models.CharField(max_length=128, blank=False, null=False, verbose_name=u"子级分类")
lft = models.IntegerField(verbose_name=u"左边界")
rgt = models.IntegerField(verbose_name=u"右边界")
# avoid circular import
from core.signals import *
第二种mptt
安装 django-mptt
pip install django-mptt
新建 area 应用
startapp area
在 models.py 里添加如下代码：
#coding:utf-8
from django.db import models
from mptt.models import MPTTModel
class Area(MPTTModel):
name = models.CharField('名称', max_length=50, unique=True)
parent = models.ForeignKey('self', verbose_name='上级区域', null=True, blank=True, related_name='children')
class Meta:
db_table = 'area'
verbose_name = verbose_name_plural = '省/市/地区(县)'
def __unicode__(self):
return self.name
在这里只需让 Area 继承 MPTTModel。
需要说明的是，实际上 MPTTModel 隐藏了四个变量：level，lft，rght 和 tree_id。大多数时候我们是用不到这几个变量的。另外，如果你的 Model 中 parent 变量名字不是 "parent" 时，应当在 Model 中MPTT 元类中指明：
#coding:utf-8
from django.db import models
from mptt.models import MPTTModel
class Area(MPTTModel):
name = models.CharField('名称', max_length=50, unique=True)
parent_area = models.ForeignKey('self', verbose_name='上级区域', null=True, blank=True, related_name='children')
class Meta:
db_table = 'area'
verbose_name = verbose_name_plural = '省/市/地区(县)'
class MPTTMeta:
parent_attr = 'parent_area'
def __unicode__(self):
return self.name
在 admin.py 里添加如下代码：
from django.contrib import admin
from .models import Area
class AreaAdmin(admin.ModelAdmin):
list_display = ('id', 'name', 'parent', 'level')
admin.site.register(Area, AreaAdmin)
在项目的 settings.py 里 INSTALLED_APPS 里添加 mptt 和 area，之后执行数据库操作。之后在 admin 后台中按照层级关系添加省/市/区(县)数据。
[图片上传失败...(image-fd628e-1521187090684)]
在 views.py 里添加如下代码：
from django.shortcuts import render_to_response
from .models import Area
def tree(request):
nodes = Area.objects.all()
return render_to_response('tree.html', {'nodes': nodes})
在 templates 文件夹下添加模版文件 tree.html：
{% load staticfiles %}
{% load mptt_tags %}
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Django 树形结构</title>
<link rel="stylesheet" href="{% static "css/css.css" %}"/>
<script src="{% static "js/jquery-1.11.2.min.js" %}"></script>
<script src="{% static "js/SimpleTree.js" %}"></script>
<script type="text/javascript">
$(function(){
$(".framework_nav").SimpleTree({
});
});
</script>
</head>
<body>
<div class="framework_nav">
<ul>
<li class="all">
<a href="#">省/市/地区(县)</a>
</li>
<ul show="true">
{% recursetree nodes %}
<li>
{% if node.is_leaf_node %}
<li><a href="#">{{ node.name }}</a></li>
{% else %}
<li><a href="#">{{ node.name }}</a></li>
<ul>
<li><a href="#">{{ children }}</a></li>
</ul>
{% endif %}
</li>
{% endrecursetree %}
</ul>
</ul>
</div>
</body>
</html>
别忘了在 settings.py 里添加如下代码：
STATIC_ROOT = os.path.join(BASE_DIR, 'static')
STATICFILES_DIRS = [
('css', os.path.join(STATIC_ROOT, 'css')),
('js', os.path.join(STATIC_ROOT, 'js')),
('img', os.path.join(STATIC_ROOT, 'img')),
]
否则获取不到静态资源！
最后在项目的 urls.py 里添加如下代码：
from area.views import tree
urlpatterns = [
...
url(r'^tree/', tree),
...
]
这样，就可以通过访问 http://127.0.0.1:8000/tree/ 看到树形结构了。
[图片上传失败...(image-13c3e5-1521187090683)]
