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
Kcelone
V2EX  ›  Python

求助贴: 删除字典树的某些节点

  •  
  •   Kcelone · 2019-09-23 17:50:53 +08:00 · 2560 次点击
    这是一个创建于 1877 天前的主题,其中的信息可能已经有所发展或是发生改变。

    当前有这样一个树结构: mtt = [ {'wp_id': '6725','children': [ {'wp_id': '6739'}, {'wp_id': '6737'} ] }, {'wp_id': '6738'}, {'wp_id': '6734', 'children': [{'wp_id': '6732'}, {'wp_id': '6733'}] } ] 删除其中 wp_id 不在['6725', '6738', '6732', '6734']中的其他节点。 要求: 某一节点不符合要求,则其所有子节点均视为不合要求,可直接删除。

    自己写了个递归处理,发现不能满足所有情况,求助算法大牛了。

    def delete_node(mt): mc = copy.deepcopy(mt) for i in mc: if i.get('wp_id') not in xt: mt.pop(mt.index(i)) elif i.get('children'): delete_node(i.get('children')) mt = mc return mt

    4 条回复    2019-09-23 18:11:18 +08:00
    Kcelone
        1
    Kcelone  
    OP
       2019-09-23 18:05:46 +08:00
    好吧,刚才已经解决了,原来我之前只写了一半。。。0.0
    Kcelone
        2
    Kcelone  
    OP
       2019-09-23 18:09:04 +08:00
    不过,相对于递归,迭代的性能似乎更高些,我这算是抛转引玉了,如果能有迭代的方法可以解决,望不吝赐教。我把完整代码贴一下:import copy
    def delete_node(mt):
    mc = copy.deepcopy(mt)
    for i in mc:
    if i.get('work_page_id') not in xt:
    mt.pop(mt.index(i))
    elif i.get('children'):
    delete_node(i.get('children'))
    mm = copy.deepcopy(mc)
    for i in mm:
    if i.get('work_page_id') not in xt:
    mc.pop(mc.index(i))
    return mc
    Kcelone
        3
    Kcelone  
    OP
       2019-09-23 18:10:20 +08:00
    哈希树的问题日常还是比较常见的,多多积累。
    Kcelone
        4
    Kcelone  
    OP
       2019-09-23 18:11:18 +08:00
    补充:xt = ['6725', '6738', '6732', '6734']
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3737 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 04:19 · PVG 12:19 · LAX 20:19 · JFK 23:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.