Python的树

Python技术
2023-05-06 17:42

　　Python可以使用列表实现树的功能。树相关操作包含:

　　1. 节点类:

　　- 用于存储节点信息。包含值和子节点列表

　　- 语法:

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

　　2. 添加子节点:

　　- 将新节点追加到节点的子节点列表中

　　- 语法:

python
node.children.append(new_node)

　　3. 树深度:

　　- 从根节点开始,到最远叶子节点的长度

　　- 可以使用 DFS 递归计算树深度

　　- 语法:

python
def maxDepth(root):
    if not root:
        return 0
    depth = 0
    for child in root.children:
        depth = max(depth, maxDepth(child) + 1)
    return depth

　　4. 查找节点:

　　- 从根节点开始,递归查找值为val的节点

　　- 如果找到返回节点,否则返回None

　　- 语法:

python 
def find(root, val):
    if not root:
        return None
    if root.val == val:
        return root
    
    for child in root.children:
        result = find(child, val)
        if result:
            return result
    return None

　　5. 前序遍历:

　　- 先访问根节点,再访问子节点。递归实现

　　- 语法:

python
def preorder(root):
    if not root:
        return 
    print(root.val)
    for child in root.children:
        preorder(child)

　　示例:

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

root = Node(1) 
a = Node(2)
b = Node(3)
root.children.append(a)
root.children.append(b)

# 添加子节点
a.children.append(Node(4))

# 树深度
maxDepth(root)  # 2

# 查找节点
find(root, 3)   # Node 3

# 前序遍历 
preorder(root)  # 1 2 4 3

　　树是一种重要的数据结构,要理解树与链表、队列的区别。要会创建节点和实现增删改、遍历等树操作。

　　要熟练掌握DFS和BFS两种常用遍历树的方法。要会计算树深度和查找指定节点。要在项目中根据需求使用树结构解决问题。

　　树的学习可以理解分支存储和递归逻辑等概念。树在生活和计算机软件中广泛运用,要深入学习树相关知识。

　　树属于数据结构高级部分,要在代码中不断实践,熟练运用。树的理解和应用属于技术提高的重点,需要长期练习总结。

Python的树