Python中的树形数据结构: 双亲表示法与孩子表示法
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
相关文章