首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Coding
V2EX  ›  程序员

万能的 V2,求问两颗树林的比较差异问题

  •  
  •   ourleven · 59 天前 via iPhone · 1146 次点击
    这是一个创建于 59 天前的主题,其中的信息可能已经有所发展或是发生改变。
    我手头有张森林的图,一个节点很多孩子,到另 n 个节点,保存为数据 a。现在别人编辑修改后,保存为数据 b。

    现在问题是,如何高亮显示 a 和 b 的差异部分?有个算法吗?

    每个节点或者方向线都有唯一标识。我的想法是遍历 a 的每个节点和方向线,看 b 里存不存在,不存在的都标记更改。最后 b 里剩下的是多出来的。也不知对不对?

    没学过图论,非程序员科班出身,求大大们指点一二。
    10 回复  |  直到 2019-10-17 21:11:52 +08:00
        1
    starqoq   59 天前
    你可以先比较节点,节点有三种修改情况,
    不变(在修改前和修改后都出现),新增(在修改的时候新增),删除(类似)。

    对于没有变化的节点,这个节点可能在修改中被换了位置,检查一下他的直接父节点是不是变化了
    按照你具体的比较要求处理子树整体移动的情况。

    对于没有变化也没有修改父节点,检查他的在兄弟中的顺序有没有变化。
        2
    taogen   59 天前 via Android
    同一顶点出发,两个图同时 BFS 放队列中,比较两个图的每一层的差集,存储所有差集的指针到 vector 中,高亮所有差集节点。
        3
    tt67wq   59 天前
    ```
    bool cmpTree(struct TreeNode *node1, struct TreeNode *node2) {
    if (node1 == NULL && node2 == NULL)
    return true;

    if (node1 == NULL && node2 != NULL)
    return false;

    if (node1 != NULL && node2 == NULL)
    return false;

    if (node1->val != node2->val)
    // 按楼主的意思,这里给改个颜色
    return false;

    return cmpTree(node1->left, node2->left) &&
    cmpTree(node1->right, node2->right);
    }

    ```
    这样行不行? 我随手写的
        4
    BiteTheDust   59 天前
    可以同时在两边跑 dfs,这样可以跑出相同的部分 剩下的就都是不同的了
        5
    ourleven   59 天前 via iPhone
    @BiteTheDust 感谢!我去科普了下 dfs,收益匪浅。但是感觉没法套用这个场景啊!
    举例,dfs 第一个树结果 a 到 b 到 c 到 e。dfs 第二个树结果,a 到 b 到 d 到 c 到 e。

    结果我能得到 ab 相同,剩下的都不同。但 c 到 e 其实是相同的
        6
    ourleven   59 天前 via iPhone
    @tt67wq 感谢!
    好像简单了点?这样应该是有漏的。到后面不相同了就停了。然而是想要所有的不同
        7
    ourleven   59 天前 via iPhone
    @taogen 谢谢!
    但问题是。。。怎么区分每一层呢?
        8
    ourleven   59 天前 via iPhone
    @starqoq 多谢!目前看起来倾向于这么比对了😂😂
        9
    BiteTheDust   59 天前
    那你得准确地规定什么样算是相同 什么样算是不同了
    如果仅仅是需要标记相同的父子关系 那只要枚举两个树每个节点,取他们孩子的交集就可以了
        10
    taogen   59 天前 via iPhone
    初始状态:定义一个指针 levelPtr 表示指向每一层最后一个节点指针。让第一个节点根节点入队,level 指向根节点。
    循环操作:队首元素出队,并把它所有子节点入队。判断当前出队节点是不是 levelptr 指向的,如果是则更换 levelptr 指向为最后一个入队的子节点,即为下一层的最后一个节点。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1073 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 23ms · UTC 23:23 · PVG 07:23 · LAX 15:23 · JFK 18:23
    ♥ Do have faith in what you're doing.