Python中的树形数据结构: 三叉搜索树

# 定义节点类
class Node:
    def __init__(self, value=None):
        self.value = value
        self.left = None
        self.middle = None
        self.right = None

# 定义三叉搜索树类
class TernarySearchTree:
    def __init__(self):
        self.root = None

    # 插入节点
    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, node):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        elif value > node.value:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)
        else:
            if node.middle is None:
                node.middle = Node(value)
            else:
                self._insert(value, node.middle)

    # 查找节点
    def search(self, value):
        return self._search(value, self.root)

    def _search(self, value, node):
        if node is None:
            return False
        elif value == node.value:
            return True
        elif value < node.value:
            return self._search(value, node.left)
        elif value > node.value:
            return self._search(value, node.right)
        else:
            return self._search(value, node.middle)

# 创建一个三叉搜索树对象
tree = TernarySearchTree()

# 插入一些节点
tree.insert("p")
tree.insert("i")
tree.insert("d")
tree.insert("a")
tree.insert("n")
tree.insert("c")
tree.insert("o")
tree.insert("d")
tree.insert("e")
tree.insert(".")

# 查找节点
print(tree.search("p"))  # True
print(tree.search("id"))  # False
print(tree.search("."))  # True