树形结构类似于数据结构中的二叉树,如果树形结构比较复杂的话,通过递归的方式查询并不是那么简介,多次 访问数据库查询,对于性能是一个很大的损耗,最近看别人的算法,也就想要写一篇自己总结下,本文主要是在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。

如何遍历一个分类

先来看看鞋子这个分类,鞋子本身是一个二级分类,鞋子下面还有一个三级分类运动鞋,那我们如何根据遍历鞋子这个分类。

  1. 先得到根结点的左右值(默认根节点的title为”顶级目录”)。
  2. 查询左右值在根节点的左右值范围内的记录,并且根据左值排序。
  3. 如果本次记录右值大于前次记录的右值则为平级分类

正常情况下,如果是一个只有两级的树,那么所有的第二季都是平级的,那么向栈中压入一个节点,在下一个节点的时候栈顶会被弹出,继续后面的节点扫描。

比如查询并排序的结果是:


[{'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 *

本节完。