求 树的匹配算法

时间:2021-11-22 05:57:25
现有一棵大树和几棵小树,要从大树里面找出结构跟小树一样的分支。有什么好的算法啊?
谢谢各位大侠指点

1 个解决方案

#1


提供思路:
记录大树和小树每个节点的父节点和子节点
注意记忆的技巧
根节点:                   dot1 ------------父亲节点为空,特殊标记0
2层:         dot21,dot22,dot23 …………   --------判断他们的父亲节点,如果父亲节点的特殊标记为0,那么他们的特殊标记为1
3层:    dot31,dot32,dot33,…………… -------判断他们的父亲节点如果特殊标记为1那么,他们的特殊标记为2,如果父亲的标记为0,那么他们的标记为1
    ………………………………

好了,现在开始判断大树和小树
从大树的根一层的开始(也就是特殊标记为0的开始),先得到它的子树的一个数组,同时统计数组长度;然后和小树的标记为0的比较一下,如相同,那么,大树进行刚才得到的数组的判断,小树也一样,对每个数组元素判断,即
大数组[0]的孩子的节点数=小数组[0]的孩子的节点数
……  [1]………………………… [1]……………………

如果都相等,那么判断下一层即大数小树标记都为2的层
如果不同,那么跳出
大树的开始标记变为1,而小树的仍然是0,如此递归

浅妄薄见,望与斟酌

#1


提供思路:
记录大树和小树每个节点的父节点和子节点
注意记忆的技巧
根节点:                   dot1 ------------父亲节点为空,特殊标记0
2层:         dot21,dot22,dot23 …………   --------判断他们的父亲节点,如果父亲节点的特殊标记为0,那么他们的特殊标记为1
3层:    dot31,dot32,dot33,…………… -------判断他们的父亲节点如果特殊标记为1那么,他们的特殊标记为2,如果父亲的标记为0,那么他们的标记为1
    ………………………………

好了,现在开始判断大树和小树
从大树的根一层的开始(也就是特殊标记为0的开始),先得到它的子树的一个数组,同时统计数组长度;然后和小树的标记为0的比较一下,如相同,那么,大树进行刚才得到的数组的判断,小树也一样,对每个数组元素判断,即
大数组[0]的孩子的节点数=小数组[0]的孩子的节点数
……  [1]………………………… [1]……………………

如果都相等,那么判断下一层即大数小树标记都为2的层
如果不同,那么跳出
大树的开始标记变为1,而小树的仍然是0,如此递归

浅妄薄见,望与斟酌