2025.06.06-布尔访问树算法

#### 门限实现
Gate类实现了一个门限门，参数为k,n；其中n表示该门控制的子节点数量；k表示阈值，可以解释为‘至少k个符合，这个门才能打开’。
```
class Gate:
    def __init__(self, k, n) -> None:
        # Gate 类表示一个门限门（threshold gate）
        # k 表示阈值，比如 "至少 k 个"
        # n 表示该门控制的子节点数量
        self.k = k
        self.n = n

def __str__(self):
        # 返回门限门的字符串表示形式，如 "(k, n)"
        return f'({self.k}, {self.n})'
```
#### 节点Node实现
1）Node为访问结构中的一个节点，参数有：gate为门限门节点，children为子节点列表（Node对象，非叶子节点）,attr为属性名称（只有叶子节点才有），其中self.secret用于存储于该节点对应的秘密值，初始为None。
```
def __init__(self, gate, children, attr) -> None:
        # Node 类表示访问结构中的一个节点
        # gate: Gate 对象，如果该节点是非叶子门限节点，则为门限门对象，否则为 None
        # children: 子节点列表（Node对象列表），非叶子节点才有子节点
        # attr: 属性名称，叶子节点才有属性，非叶子节点为 None
        self.gate = gate
        self.children = children
        self.attr = attr
        # secret: 用于存储与该节点对应的秘密值，初始为 None
        self.secret = None
```
2）构建一个**门限节点**，输入门限门和子节点列表children，返回一个Node对象。
```
@staticmethod
    def threshold_node(gate, children):
        # 静态方法，构造一个门限节点
        # 输入门限门 gate 和子节点列表 children，返回一个 Node 对象
        return Node(gate, children, None)
```
3）构造一个**属性节点**（叶子节点）,输入属性名称attr，返回一个Node对象，gate和children都为None

```
    @staticmethod
    def attr_node(attr):
        # 静态方法，构造一个叶子节点（属性节点）
        # 输入属性名称 attr，返回一个 Node 对象，gate 和 children 都为 None
        return Node(None, None, attr)
```
4）判断节点是否为属性节点，通过self.gate为None来判断

```
def is_leaf(self):
        # 判断该节点是否是叶子节点（即是否为属性节点）
        # 如果 gate 是 None，则说明是叶子节点
        return self.gate is None
```
5）私有递归函数，深度有限遍历访问树节点，用于生成节点及其子节点的字符串表示。

```
def __dfs(self, deep):
        # 私有递归函数，深度优先遍历访问树节点，用于生成节点及其子节点的字符串表示
        # deep 表示当前节点的深度，用于缩进格式化输出
        s = '\t' * deep  # 根据深度添加缩进
        if self.is_leaf():
            # 叶子节点，打印属性名和秘密值
            s += str(self.attr) + f': {self.secret}' + '\n'
        else:
            # 非叶子门限节点，打印门限门信息和秘密值
            s += str(self.gate) + f': {self.secret}' + '\n'
            # 递归遍历所有子节点，增加深度缩进
            for c in self.children:
                s += c.__dfs(deep + 1)
        return s
```
6）当调用 print(node) 或 str(node) 时，调用该函数输出节点信息，调用递归函数 __dfs 从根节点开始遍历。
```
 def __str__(self):
        # 当调用 print(node) 或 str(node) 时，调用该函数输出节点信息
        # 实际调用递归函数 __dfs 从根节点开始遍历
        return self.__dfs(0)
```
#### 例子测试
构造一个布尔访问树，and节点使用门限(2,2)表示，or节点使用(1,2)表示

![](/media/202506/bool_lsss_tn_1749200240.png)
```
from src.node import *
# 构建上述布尔访问树, and节点使用门限(2, 2)表示，or节点使用(1, 2)表示
root = Node.threshold_node(Gate(2, 2), [
    Node.attr_node('E'),
    Node.threshold_node(Gate(1, 2), [
        Node.threshold_node(Gate(1, 2), [
            Node.threshold_node(Gate(2, 2), [Node.attr_node('A'), Node.attr_node('B')]),
            Node.threshold_node(Gate(2, 2), [Node.attr_node('C'), Node.attr_node('D')])
        ]),
        Node.threshold_node(Gate(2, 2), [
            Node.threshold_node(Gate(1, 2), [Node.attr_node('A'), Node.attr_node('B')]),
            Node.threshold_node(Gate(1, 2), [Node.attr_node('C'), Node.attr_node('D')])
        ])
    ])
])

print(root)
```

```
(2, 2): None
	E: None
	(1, 2): None
		(1, 2): None
			(2, 2): None
				A: None
				B: None
			(2, 2): None
				C: None
				D: None
		(2, 2): None
			(1, 2): None
				A: None
				B: None
			(1, 2): None
				C: None
				D: None
```