在 Python 中使用三等分搜索树

Question

我正在尝试从以下三分树中搜索一个节点，每个节点都有三个子节点（必须使用递归）

                        (1,5)
                      /0  |1  
                     /    |    \                   
                (2,7)          (1,3)
              /0  |1       /0 |1 
                  |   \         |   \
                     (7,5)          (0,-5)
                  

key=(1,5), children=[key=(2,7), children=[None, None, key=(7,5), children=[None, None, None]], None, key=(1,3), children=[None, None, key=(0,-5), children=[None, None, None]]]

这是我的搜索函数，包含参数 p（p 是我要搜索的节点，例如 (1,3)）

def search(self,p):
        
        if self.key == None:
            return None
        if p == self.key:
            return self
        elif self.child[0]:
                            
            if self.child[0] == None:
                return None
            else:
                return self.child[0].search(p)
        elif self.child[1]:
                            
            if self.child[1] == None:
                return None
            else:
                return self.child[1].search(p)
        elif self.child[2]:
                           
            if self.child[2] == None:
                return None
            else:
                return self.child[2].search(p)

输出可以是 if p=(1,3)

key=(1,3), children=[None, None, key=(0,-5), children=[None, None, None]]

怎么做..

Answer 1

一些问题：

如果您进入 elif self.child[0] 块，那么下一个（嵌套的）if 条件 (self.child[0] == None) 将始终为假。
在同一个块中，总会有一个 return 执行，即不会检查其他 child。

不是问题，但是：

self.key == None 条件似乎假设...可能有一个 None 键，这让我觉得你的树 class 总是有至少一个节点，并且您用 None 键指示一棵空树。这不是最佳做法。一棵空树应该只有 no 个节点。因此，您应该将节点 class 与树 class 分开，其中树 class 的根属性可以是 None（空树）或节点实例。

这里是你方法的更正：

    def search(self, p):
        if p == self.key:
            return self
        for child in self.child:
            found = child and child.search(p)
            if found:
                return found

在 Python 中使用三等分搜索树

Working with Trisection Search Tree in Python

python

tree

recursion

binary-tree

binary-search-tree