Python中的树形数据结构: 链表实现树

2023-04-11 00:00:00 python 数据结构链表

链表实现树是一种常见的树形数据结构，它将每个节点保存为一个节点对象，每个节点包含一个数据元素和一个指向子节点的指针。

在Python中，可以使用类来表示树的节点，每个节点可以包含多个子节点，这样就可以形成树形结构。以下是基于链表实现的树的代码实现：

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

    def add_child(self, child):
        self.children.append(child)

在上面的代码中，TreeNode类表示树的节点，每个节点包含一个数据元素和一个子节点列表。add_child()方法用于向节点添加子节点。

接下来，可以使用TreeNode类创建一个树对象，并添加节点：

root = TreeNode("pidancode.com")
root.add_child(TreeNode("Python"))
root.add_child(TreeNode("Java"))
root.add_child(TreeNode("JavaScript"))
root.children[0].add_child(TreeNode("Django"))
root.children[0].add_child(TreeNode("Flask"))
root.children[1].add_child(TreeNode("Spring"))
root.children[1].add_child(TreeNode("Hibernate"))
root.children[2].add_child(TreeNode("React"))
root.children[2].add_child(TreeNode("Angular"))

上面的代码创建了一个根节点，然后添加了三个子节点：Python、Java和JavaScript。然后添加了Python节点的两个子节点：Django和Flask，Java节点的两个子节点：Spring和Hibernate，JavaScript节点的两个子节点：React和Angular。

最后，可以遍历树的节点，将树的结构打印出来：

def print_tree(node, level=0):
    if node:
        print("\t" * level, node.data)
        for child in node.children:
            print_tree(child, level+1)

print_tree(root)

输入输出：

pidancode.com
     Python
         Django
         Flask
     Java
         Spring
         Hibernate
     JavaScript
         React
         Angular

上面的代码使用递归遍历树的节点，如果节点存在子节点，就打印出子节点的数据元素，然后递归遍历子节点的子节点。最后，调用print_tree()函数，将树的结构打印出来。

链表实现树是一种简单、灵活、易于实现的树形数据结构，适用于处理大量的树形数据。

相关文章