Python中的树形数据结构: 双亲表示法与孩子表示法

2023-04-11 00:00:00 数据结构 孩子 双亲

Python中的树形数据结构可以用双亲表示法和孩子表示法来表示。双亲表示法需要为每个节点指定其父节点,孩子表示法需要为每个节点指定其子节点。

双亲表示法:

class Node:
    def __init__(self, data, parent=None):
        self.data = data
        self.parent = parent

class Tree:
    def __init__(self):
        self.nodes = []

    def add_node(self, data, parent_data=None):
        parent = None
        if parent_data is not None:
            for node in self.nodes:
                if node.data == parent_data:
                    parent = node
                    break
            else:
                raise ValueError("Parent node not found")

        node = Node(data, parent)
        self.nodes.append(node)

    def get_node(self, data):
        for node in self.nodes:
            if node.data == data:
                return node
        else:
            raise ValueError("Node not found")

使用示例:

tree = Tree()
tree.add_node("pidancode.com")
tree.add_node("Tutorials", "pidancode.com")
tree.add_node("Python", "Tutorials")
tree.add_node("Java", "Tutorials")

python_node = tree.get_node("Python")
print(python_node.data)  # Python
print(python_node.parent.data)  # Tutorials

孩子表示法:

class Node:
    def __init__(self, data):
        self.data = data
        self.children = []

class Tree:
    def __init__(self):
        self.root = None

    def add_node(self, data, parent_data=None):
        node = Node(data)
        if parent_data is None:
            if self.root is not None:
                raise ValueError("Root node already exists")
            self.root = node
        else:
            parent = self.get_node(parent_data)
            parent.children.append(node)

    def get_node(self, data):
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            if node.data == data:
                return node
            queue.extend(node.children)
        else:
            raise ValueError("Node not found")

使用示例:

tree = Tree()
tree.add_node("pidancode.com")
tree.add_node("Tutorials", "pidancode.com")
tree.add_node("Python", "Tutorials")
tree.add_node("Java", "Tutorials")

python_node = tree.get_node("Python")
print(python_node.data)  # Python
print(python_node.parent.data)  # Tutorials

相关文章