树状数据结构建立

树状数据结构建立

很多时候我们会需要一个树状结构来管理我们的数据, 比如以下等等.

• 档案结构: 电脑 - 目录 - 档案
• 房子结构: 建筑 - 区域 - 设施
• 书库结构: 书库 - 类别 - 书籍

树状结构由各节点所组成, 有几项基本的属性是必要的.

• 父节点, 用来连结父项, 可以从树状结构的下层找到上层, 设置只有一项.
• 子节点, 用来连结子项, 可以从树状结构的上层找到下层, 设置可以有多项.
• 节点名, 用来代表节点, 以人类可识别的文字来代表, 因此可以重复, 不能在数据结构上用来代表节点
• 节点值, 用来储存节点本身的各项资讯
• 节点键, 用来代表节点, 这个键值不需人人类可识别, 但为了代表各个节点, 此键值必须唯一, 不可重复.

除了各节点的各自讯息外, 另外需要有一个字典, 用来记录所有的节点.

树状结构节点的类定义

所以我们现在要进行的就是建立一个节点的类.

1. 类/节点的定义 (class)

class Node():

2. 节点记录表的类变量 = 空字典 {节点键:节点, …}

    elements = {}

3. 函数/起始 - 参数为 节点名, 节点值 (__init__)
   • 属性.节点名 = 节点名
   • 属性.节点值 = 节点值
   • 属性.父节点 = 无
   • 属性.子节点 = 空列表
   • 属性.节点键 = 调用节点键自动产生函数

    def __init__(self, name, values=None):
        self.name = name
        self.parent = None
        self.children = []
        self.values = {} if values is None else values
        self.key = self.get_key()
        Node.elements[self.key] = self

4. 函数/节点键自动产生 (0 保留给树根, 作为最顶层的存在)
   • 从 1 开始往上加, 在节点记录表找到一个不存在的节点键

    def get_key(self):
        key = 0
        while key in Node.elements:
            key += 1
        return key

5. 函数/增加子节点 - 参数为 该子节点的节点键
   • 子节点列表加入 子节点键
   • 根据子节点键, 在节点记录表中找到子节点, 该子节点的父节点为本节点键.

    def add_child(self, child):
        key = child.key
        self.children.append(key)
        Node.elements[key].parent = self.key
    def add_children(self, children):
        for child in children:
            self.add_child(child)

6. 函数/移除子节点 - 参数为 该子节点的节点键
   • 子节点列表删除 子节点键
   • 根据子节点键, 在节点记录表中找到子节点, 该子节点的父节点为设为 None.

    def remove_child(self, key):
        if key in self.children:
            self.children.remove(key)
            Node.elements[key].parent = None
    def remove_children(self):
        for key in self.children:
            self.remove_child(key)

7. 函数/显示节点的字串形式 (__repr__)
   • 显示 节点名 + 节点值
   • 按子节点列表循环往下找到各个子节点的 节点名 + 节点值
     直到没有子节点

    def get_string(self, key, i=0):
        node = Node.elements[key]
        result = ' '*i + node.name + ' ' + str(node.values) + '\n'
        for child in node.children:
            result += self.get_string(child, i+2)
        return result

    def __repr__(self):
        return self.get_string(self.key).strip()

使用方式

1. 建立节点/树状数据结构

chairs = [Node(f'Chair {i}', values={'material':'metal', 'size':'medium'}) for i in range(12)]
table_1 = Node('Table 1', values={'material':'wood', 'size':'medium'})
table_1.add_children([chairs[i] for i in range(4)])
table_2 = Node('Table 2', values={'material':'wood', 'size':'large'})
table_2.add_children([chairs[i] for i in range(4, 12)])
kitchen = Node('Kitchen 1', values={'area':20})
kitchen.add_child(table_1)
kitchen.add_child(table_2)
bedrooms = [Node(f'Bedroom {i}', values={'size':'double'}) for i in range(3)]
house = Node('House 1', values={'cost':1200000, 'area':100, 'city':'Zuhai'})
house.add_child(kitchen)
house.add_children(bedrooms)

2. 显示结果

>>> house
House 1 {'cost': 1200000, 'area': 100, 'city': 'Zuhai'}
  Kitchen 1 {'area': 20}
    Table 1 {'material': 'wood', 'size': 'medium'}
      Chair 0 {'material': 'metal', 'size': 'medium'}
      Chair 1 {'material': 'metal', 'size': 'medium'}
      Chair 2 {'material': 'metal', 'size': 'medium'}
      Chair 3 {'material': 'metal', 'size': 'medium'}
    Table 2 {'material': 'wood', 'size': 'large'}
      Chair 4 {'material': 'metal', 'size': 'medium'}
      Chair 5 {'material': 'metal', 'size': 'medium'}
      Chair 6 {'material': 'metal', 'size': 'medium'}
      Chair 7 {'material': 'metal', 'size': 'medium'}
      Chair 8 {'material': 'metal', 'size': 'medium'}
      Chair 9 {'material': 'metal', 'size': 'medium'}
      Chair 10 {'material': 'metal', 'size': 'medium'}
      Chair 11 {'material': 'metal', 'size': 'medium'}
  Bedroom 0 {'size': 'double'}
  Bedroom 1 {'size': 'double'}
  Bedroom 2 {'size': 'double'}

注: 删除节点以及移动节点都可以作到, 就是复杂点, 这里就不细说了.

本作品采用《CC 协议》，转载必须注明作者和本文链接