树的同构 python - Isomorphic

Posted at — Mar 31, 2020

题目见ZJU数据结构 03-树1

示例代码为C语言，网上文章也多是C语言。python有个是用数组实现的 PTA 7-1 树的同构

我最后用结点+数组实现（low是low了点… 但示例里也是一个包含结点数据类型的数组，没差…

struct TreeNode
{
  ElementType Elment;
  Tree Left;
  Tree Right;
} T1[MaxTree], T2[MaxTree];

以下为python代码：

核心思想就是判断当前结点是否相同，如果不相同则为假，如果相同就递归判断t1左儿子t2左儿子是否相同，t1右儿子t2右儿子是否相同，否则就交换左右儿子，再进行递归判断

# 建立结点的class
class TreeNode(object):
    def __init__(self, data = None, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right

# 在tree的数组中添加新结点
def append(Tree, index, item):
    Tree[index] = TreeNode(item[0], item[1], item[2])

# 建造树
def BuildTree():
  	# n为结点个数
    n = int(input())
    # check是输入数据处理完后找到树的root
    check = [0] * n
    root = None
    
    # 生成数量为n个空结点的数组tree
    Tree = [TreeNode()] * n
    
    # 循环处理输入数据
    for i in range(n):       
        l = input().split()
        
        if l[1] == "-":
            l[1] = None
        else:
            l[1] = int(l[1])
            check[l[1]] =+ 1
        if l[2] == "-":
            l[2] = None
        else:
            l[2] = int(l[2])
            check[l[2]] =+ 1
        # 添加结点
        append(Tree, i, l)
        
		# 找到root
    for i in range(len(check)):
        if check[i] == 0:
            root = i
    # 返回树和结点
    return (Tree, root)
  
# 判断树的同构
def isomorphic(T1, R1, T2, R2):
    # 两个树的结点数
    n1 = 0
    n2 = 0
    
# 处理例外情况

    # 如果都为空树，为真
    if len(T1) == 0 and len(T2) == 0:
        return True
    
    # 如果只有一个节点
    if (len(T1) == 1 and len(T2) == 1):
      	# 值相同，为真
        if T1[0].data == T2[0].data:
            return True
        # 否则为假
        else:
            return False
          
    # 如果节点都为零，为真
    if R1 == None and R2 == None:
        return True
    
    # 如果节点数不同，为假
    if len(T1) != len(T2):
        return False
    
# 处理正常情况

    # 如果一个为空，一个不为空，为假
    if (R1 == None and R2 != None) or (R1 != None and R2 == None):
        #print('tag2')
        return False

    # 如果左儿子都为空，判断右儿子是否同构
    if T1[R1].left == None and T2[R2].left == None:
        #print('tag3')
        return isomorphic(T1, T1[R1].right, T2, T2[R2].right)
    
    # 如果左儿子都不为空且数据还是一样的，对左右儿子进行递归判断
    if (T1[R1].left != None and T2[R2].left != None) and (T1[T1[R1].left].data == T2[T2[R2].left].data):
        return (isomorphic(T1, T1[R1].left, T2, T2[R2].left) and isomorphic(T1, T1[R1].right, T2, T2[R2].right))
    # 如果左儿子一个空一个不空或者两个都不同，并且数据不一样，交换左右儿子进行递归判断
    else:
        return (isomorphic(T1, T1[R1].left, T2, T2[R2].right) and isomorphic(T1, T1[R1].right, T2, T2[R2].left))
      
# main

Tree1,r1 = BuildTree()
Tree2,r2 = BuildTree()

result = isomorphis(Tree1, r1, Tree2, r2)

if result:
    print("Yes")
else:
    print("No")

99 problems

Zoo is sad.

树的同构 python - Isomorphic