Python树结构库Treelib实战指南

文章目录

一、安装

二、基本用法

2.1 创建多叉树

2.2 添加节点

2.2 输出树结构

2.3 返回多叉树中的节点

2.3.1 tree.all_nodes()

2.3.2 tree.all_nodes_itr()

2.3.3 tree.expand_tree()

2.4 判断是否为根/叶子节点

2.5 多叉树的深度和叶子节点

2.5.1 多叉树的深度

2.5.2 树的叶子节点

2.5.3 到叶子节点的路径

2.6 其他用法

三、高级用法

参考文献

树结构是一种常见且重要的数据结构。Python中的treelib库是对树结构的有效实现。在 treelib 库中，实现了两个类 Tree 和 Node，分别用于创建多叉树和创建节点。

一、安装

pip install treelib

二、基本用法

2.1 创建多叉树

from treelib import Tree, Node

# 创建一棵多叉树
tree = Tree()  

Tree 类用于实例化一棵多叉树。有四个初始化参数：Tree(tree=None, deep=False, node_class=None, identifier=None)，都有默认值。函数定义如下：

def __init__(self, tree=None, deep=False, node_class=None, identifier=None):

tree表示拷贝一棵已有的树，传入一个Tree的对象。

deep表示拷贝另一棵树时是否深拷贝。

node_class表示节点类，一般不需要使用，可以不管。

identifier表示树的id，在初始化时会默认分配一个唯一的id值，也可以手动指定一个id，保证是唯一的就行，树一旦创建完成，id就不能再修改。

2.2 添加节点

创建完多叉树后，我们可以基于tree.create_node()函数来添加节点。

# 添加节点
tree.create_node('Harry', 'harry')  # 根节点
tree.create_node('Jane', 'jane', parent='harry')
tree.create_node('Bill', 'bill', parent='harry')
tree.create_node('Diane', 'diane', parent='jane')
tree.create_node('Mary', 'mary', parent='diane')
tree.create_node('Mark', 'mark', parent='jane')

create_node(tag=None, identifier=None, parent=None, data=None): 创建一个节点并直接添加到树中。函数定义如下：

def create_node(self, tag=None, identifier=None, parent=None, data=None):
    """
    Create a child node for given @parent node. If ``identifier`` is absent,
    a UUID will be generated automatically.
    """

tag表示节点的标签，在控制台打印树的结构时显示的就是节点的标签，可以指定值，如果不指定值则默认等于id。

identifier表示节点的id，默认会分配一个唯一的id，也可以指定一个唯一id。这里要注意，id是唯一的，不能重复，标签是可以重复的但最好别重复。

parent表示节点的父节点，根节点可以不指定，不过，一棵树只能有一个根节点，如果树中已经有根节点了，parent还为空会报错。

data表示节点中保存的数据，可以是各种数据类型。

add_node(node, parent=None): 添加一个节点到树中。这个方法需要先用 Node 类创建好节点，第一个参数传入节点，第二参数同create_node()方法。

def add_node(self, node, parent=None):
    """
    Add a new node object to the tree and make the parent as the root by default.

    The 'node' parameter refers to an instance of Class::Node.
    """

2.2 输出树结构

tree.show()

这你，如果 tree.show()显示很多符号，而不是教程中所给的树结构时，可以使用
tree.show(line_type='ascii')。

print(tree)

输出如下：

Harry
├── Bill
└── Jane
    ├── Diane
    │   └── Mary
    └── Mark

2.3 返回多叉树中的节点

2.3.1 tree.all_nodes()

all_nodes(): 返回多叉树中的所有节点，返回结果是一个节点对象构成的列表，节点的顺序是添加到树中的顺序。

print(tree.all_nodes())  # 返回多叉树中的节点

输出：

[Node(tag=Harry, identifier=harry, data=None), Node(tag=Jane, identifier=jane, data=None), Node(tag=Bill, identifier=bill, data=None), Node(tag=Diane, identifier=diane, data=None), Node(tag=Mary, identifier=mary, data=None), Node(tag=Mark, identifier=mark, data=None)]

直接打印节点，会将节点作为一个类对象打印出来。节点的tag、identifier和data三条属性可以单独调用，可以看到在不指定值时，tag与identifier相等，是一个系统分配的唯一值。

2.3.2 tree.all_nodes_itr()

all_nodes_itr(): 返回多叉树中的所有节点，返回结果是一个迭代器，节点的顺序是添加到树中的顺序。

for node in tree.all_nodes_itr():
    print(node)

输出：

Node(tag=Harry, identifier=harry, data=None)
Node(tag=Jane, identifier=jane, data=None)
Node(tag=Bill, identifier=bill, data=None)
Node(tag=Diane, identifier=diane, data=None)
Node(tag=Mary, identifier=mary, data=None)
Node(tag=Mark, identifier=mark, data=None)

2.3.3 tree.expand_tree()

expand_tree(): 返回多叉树中的所有节点id，返回结果是一个生成器，顺序是按深度优先遍历的顺序。可以传入过滤条件等参数来改变返回的生成器。

for id in tree.expand_tree():
    print(id)

输出：

harry
bill
jane
diane
mary
mark

2.4 判断是否为根/叶子节点

is_leaf(tree_id=None): 返回节点在树中的位置是不是叶节点。

is_root(tree_id=None): 返回节点在树中的位置是不是根节点。

for node in tree.all_nodes_itr():
    print(node)
    print('leaf:', node.is_leaf())
    print('root:', node.is_root())

输出：

Node(tag=Harry, identifier=harry, data=None)
leaf: False
root: True
Node(tag=Jane, identifier=jane, data=None)
leaf: False
root: False
Node(tag=Bill, identifier=bill, data=None)
leaf: True
root: False
Node(tag=Diane, identifier=diane, data=None)
leaf: False
root: False
Node(tag=Mary, identifier=mary, data=None)
leaf: True
root: False
Node(tag=Mark, identifier=mark, data=None)
leaf: True
root: False

2.5 多叉树的深度和叶子节点

2.5.1 多叉树的深度

print('tree depth:', tree.depth())

输出：

tree depth: 3

2.5.2 树的叶子节点

print('tree leaves:', tree.leaves())

输出：

tree leaves: [Node(tag=Bill, identifier=bill, data=None), Node(tag=Mary, identifier=mary, data=None), Node(tag=Mark, identifier=mark, data=None)]

2.5.3 到叶子节点的路径

print(tree.paths_to_leaves())

输出：

[['harry', 'bill'], ['harry', 'jane', 'diane', 'mary'], ['harry', 'jane', 'mark']]

2.6 其他用法

children(nid): 传入节点id，返回节点的所有子节点，返回结果是一个节点列表，如果没有子节点则返回空列表。

is_branch(nid): 传入节点id，返回节点的所有子节点id，返回结果是一个列表，如果没有子节点则返回空列表。

siblings(nid): 传入节点id，返回节点的所有兄弟节点，返回结果是一个节点列表，如果没有兄弟节点则返回空列表。

parent(nid): 传入节点id，返回节点的父节点，如果传入的是根节点，则返回None。

ancestor(nid, level=None): 传入节点id，返回节点的一个祖先节点，如果指定level则返回level层的祖先节点，如果不指定level则返回父节点，如果指定level比节点的层数大，则报错。

is_ancestor(ancestor, grandchild): 传入两个节点id，判断ancestor是不是grandchild的祖先，返回布尔值。

rsearch(nid, filter=None): 传入节点id，遍历节点到根节点的路径上的所有节点id，包含该节点和根节点，返回结果是一个生成器。可以传入过滤条件对结果进行过滤。

三、高级用法

判断节点是否在多叉树中

多叉树的合并和子树拷贝

多叉树删除子树

。。。

参考文献

Python treelib库创建多叉树的用法介绍

Python树结构库treelib

作者：酒酿小圆子～