V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
JSPIXiaoHei
V2EX  ›  Python

用 Python 如何实现树形数据结构?自己琢磨半天总感觉写的不对

  •  
  •   JSPIXiaoHei · 2022-01-11 17:23:40 +08:00 · 1889 次点击
    这是一个创建于 807 天前的主题,其中的信息可能已经有所发展或是发生改变。

    就是一个根节点下面有数目不定的子节点,比较像文件夹、文件的感觉。

    源数据是表结构,有 自己 id 、父节点 id 、数据内容 这几列。

    想实现的功能是,根据源数据可以创建一个 树的对象 , 树的对象可以根据查询条件返回节点对象或者节点对象列表,节点对象也可以根据查询条件查询符合的子节点、父节点对象(或对象列表),类似于下面的

    class Node:
        def __init__(self, xxx):
            self.parent
            self.children
            self.title
            self.data
    
    class MyTree:
        def __init__(self, data):
            self.root_node = Node(xxx)
            for line in data:
                ???
    
    tree = MyTree(data=data)
    
    root_node = tree.get_root()
    
    if root_node.exists_child(condition):
        such_node = root_node.query(condition)
        if such_node.exists_child(xxx):
            print('found!')
    else:
        print('not exists!')
    
    

    感觉和爬虫用的 lxml.etree 很像,有什么现成的轮子吗?看了 anytree ,感觉不太理想,或者请大佬指教一下写法

    5 条回复    2022-01-11 18:18:00 +08:00
    liprais
        1
    liprais  
       2022-01-11 17:32:15 +08:00
    接邻表呗
    ipwx
        2
    ipwx  
       2022-01-11 17:38:07 +08:00
    node_map = {}

    for line in data:
    ....node = Node(...)
    ....node_map[node.parent_id].children.append(node)
    ....node_map[node.id] = node
    meiyoumingzi6
        3
    meiyoumingzi6  
       2022-01-11 18:16:51 +08:00
    之前写过一个, 不知道是否满足你的需求

    class Node:
    def __init__(self, val, left=None, right=None) -> None:
    self.val = val
    self.left = left
    self.right = right

    def create_tree(data: list):
    if not data:
    return None
    first_node = Node(data[0])
    tmp_list = [first_node]
    tmp_count = 0
    for item in data[1:]:
    node = tmp_list[0]
    new_node = Node(item) if item is not None else None
    if tmp_count == 0:
    node.left = new_node
    # add to tmp_list
    if item is not None:
    tmp_list.append(new_node)
    tmp_count += 1
    continue
    if tmp_count == 1:
    node.right = new_node
    if item is not None:
    tmp_list.append(new_node)
    # POP
    tmp_list.pop(0)
    tmp_count = 0
    continue
    return first_node
    meiyoumingzi6
        4
    meiyoumingzi6  
       2022-01-11 18:17:10 +08:00
    ```python

    class Node:
    def __init__(self, val, left=None, right=None) -> None:
    self.val = val
    self.left = left
    self.right = right

    def create_tree(data: list):
    if not data:
    return None
    first_node = Node(data[0])
    tmp_list = [first_node]
    tmp_count = 0
    for item in data[1:]:
    node = tmp_list[0]
    new_node = Node(item) if item is not None else None
    if tmp_count == 0:
    node.left = new_node
    # add to tmp_list
    if item is not None:
    tmp_list.append(new_node)
    tmp_count += 1
    continue
    if tmp_count == 1:
    node.right = new_node
    if item is not None:
    tmp_list.append(new_node)
    # POP
    tmp_list.pop(0)
    tmp_count = 0
    continue
    return first_node
    ```
    meiyoumingzi6
        5
    meiyoumingzi6  
       2022-01-11 18:18:00 +08:00
    淦 格式老错,

    自己上我博客看吧

    https://blog.yujichenfeng.ml/posts/algorithm/tree/
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3914 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 10:28 · PVG 18:28 · LAX 03:28 · JFK 06:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.