python求多叉树任意两点之间的距离

对于多叉树求两点之间的距离，最难的地方在于有没有思路，如何找到指定点的位置，以及如何去计算两个指定点之间的距离，下图是一个简单的的多叉树，从5到1的距离为2，从5到7的距离为4。

我们可以将求解两点之间的距离分为2个任务，第一个任务是寻找从root开始到指定点之间的路径，第二个任务是找到公共祖先，并通过找到两点的公共祖先来计算两点之间的距离，代码如下

class Node(object):
    def __init__(self, value=0):
        self.value = value
        self.children = []
        self.left = self.right = None


def get_path_length(root, path, k):
    # base case handling
    if root is None:
        return False
    path.append(root.value)
    if root.value == k:
        return True
    for child in root.children:
        if (child.children != None and get_path_length(child, path, k)):
            return True
    # 如果当前结点的值并不是k
    path.pop()
    return False
def find_distance(root, n1, n2):
    if root:
        # 获取第一个结点的路径（存储跟结点到i）
        path1 = []
        get_path_length(root, path1, n1)
        # 获取第二个结点的路径
        path2 = []
        get_path_length(root, path2, n2)
        # 找到它们的公共祖先
        i = 0
        while i < len(path1) and i < len(path2):
            if path1[i] != path2[i]:
                break
            i = i + 1
        # 减去重复计算的跟结点到lca部分即为结果
        return (len(path1) + len(path2) - 2 * i)
    else:
        return 0


if __name__ == '__main__':
    with open(r'D:\PekingInfoResearch\HiAGM_new\data\rcv1.taxonomy', 'r', encoding='utf-8') as f:
        first_line = f.readline()
        root = Node(first_line.split()[0])
        root.children = [Node(x) for x in first_line.split()[1:]]
        for line in f:
            line = line.split()
            for child in root.children:
                if line[0] == child.value:
                    child.children = [Node(x) for x in line[1:]]
                    break
                if child.children:
                    for child_1 in child.children:
                        if line[0] == child_1.value:
                            child_1.children = [Node(x) for x in line[1:]]
                            break

    dist = find_distance(root, 'C41', 'G15')
    print("Distance between node {} & {}: {}".format('C41', 'G15', dist))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

rcv1.taxonomy

Root	CCAT	ECAT	GCAT	MCAT
CCAT	C11	C12	C13	C14	C15	C16	C17	C18	C21	C22	C23	C24	C31	C32	C33	C34	C41	C42
C15	C151	C152
C151	C1511
C17	C171	C172	C173	C174
C18	C181	C182	C183
C31	C311	C312	C313
C33	C331
C41	C411
ECAT	E11	E12	E13	E14	E21	E31	E41	E51	E61	E71
E12	E121
E13	E131	E132
E14	E141	E142	E143
E21	E211	E212
E31	E311	E312	E313
E41	E411
E51	E511	E512	E513
GCAT	G15	GCRIM	GDEF	GDIP	GDIS	GENT	GENV	GFAS	GHEA	GJOB	GMIL	GOBIT	GODD	GPOL	GPRO	GREL	GSCI	GSPO	GTOUR	GVIO	GVOTE	GWEA	GWELF
G15	G151	G152	G153	G154	G155	G156	G157	G158	G159
MCAT	M11	M12	M13	M14
M13	M131	M132
M14	M141	M142	M143
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

感谢banananana提供的python二叉树求解两点之间距离的思路