python树的同构学习笔记

yipeiwu_com5年前Python基础

一、题意理解

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构的”。现给定两棵树,请你判断它们是否是同构的。

输入格式:输入给出2棵二叉树的信息:

先在一行中给出该树的结点树,随后N行

第i行对应编号第i个结点,给出该结点中存储的字母、其左孩子结点的编号、右孩子结点的编号

如果孩子结点为空,则在相应位置给出“-”

如下图所示,有多种表示的方式,我们列出以下两种:

二、求解思路

搜到一篇也是讲这个的,但是那篇并没有完全用到单向链表的方法,所以研究了一下,写了一个是完全用单向链表的方法:

其实应该有更优雅的删除整个单向列表的方法,比如头设为none,可能会改进下?

# python语言实现

L1 = list(map(int, input().split()))
L2 = list(map(int, input().split()))


# 节点
class Node:
  def __init__(self, coef, exp):
    self.coef = coef
    self.exp = exp
    self.next = None


# 单链表
class List:
  def __init__(self, node=None):
    self.__head = node

  # 为了访问私有类
  def gethead(self):
    return self.__head

  def travel(self):
    cur1 = self.__head
    cur2 = self.__head
    if cur1.next != None:
      cur1 = cur1.next
    else:
      print(cur2.coef, cur2.exp, end="")
      return
    while cur1.next != None:
      print(cur2.coef, cur2.exp, end=" ")
      cur1 = cur1.next
      cur2 = cur2.next

    print(cur2.coef, cur2.exp, end=" ")
    cur2 = cur2.next
    print(cur2.coef, cur2.exp, end="")

  # add item in the tail
  def append(self, coef, exp):
    node = Node(coef, exp)
    if self.__head == None:
      self.__head = node
    else:
      cur = self.__head
      while cur.next != None:
        cur = cur.next
      cur.next = node


def addl(l1, l2):
  p1 = l1.gethead()
  p2 = l2.gethead()
  l3 = List()
  while (p1 is not None) & (p2 is not None):
    if (p1.exp > p2.exp):
      l3.append(p1.coef, p1.exp)
      p1 = p1.next
    elif (p1.exp < p2.exp):
      l3.append(p2.coef, p2.exp)
      p2 = p2.next
    else:
      if (p1.coef + p2.coef == 0):
        p1 = p1.next
        p2 = p2.next
      else:
        l3.append(p2.coef + p1.coef, p1.exp)
        p2 = p2.next
        p1 = p1.next
  while p1 is not None:
    l3.append(p1.coef, p1.exp)
    p1 = p1.next
  while p2 is not None:
    l3.append(p2.coef, p2.exp)
    p2 = p2.next
  if l3.gethead() == None:
    l3.append(0, 0)
  return l3


def mull(l1, l2):
  p1 = l1.gethead()
  p2 = l2.gethead()
  l3 = List()
  l4 = List()
  if (p1 is not None) & (p2 is not None):
    while p1 is not None:
      while p2 is not None:
        l4.append(p1.coef * p2.coef, p1.exp + p2.exp)
        p2 = p2.next
      l3 = addl(l3, l4)
      l4 = List()
      p2 = l2.gethead()
      p1 = p1.next
  else:
    l3.append(0, 0)
  return l3


def L2l(L):
  l = List()
  L.pop(0)
  for i in range(0, len(L), 2):
    l.append(L[i], L[i + 1])
  return l


l1 = L2l(L1)
l2 = L2l(L2)
l3 = List()
l3 = mull(l1, l2)
l3.travel()
print("")
l3 = List()
l3 = addl(l1, l2)
l3.travel()

以上就是本次介绍的全部内容知识点,相关内容可以参阅下方知识点,感谢大家对【听图阁-专注于Python设计】的支持。

相关文章

Python中实例化class的执行顺序示例详解

前言 本文主要介绍了关于Python实例化class的执行顺序的相关内容,下面话不多说了,来一起看看详细的介绍吧 Python里对类的实例化时有怎样的顺序 一般来说一个类里面有类变量和...

python调用支付宝支付接口流程

python调用支付宝支付接口流程

项目演示: 一、输入金额 二、跳转到支付宝付款 三、支付成功 四、跳转回自己网站 在使用支付宝接口的前期准备: 1、支付宝公钥 2、应用公钥 3、应用私钥 4、APPID 5、D...

完美解决python遍历删除字典里值为空的元素报错问题

exam = { 'math': '95', 'eng': '96', 'chn': '90', 'phy': '', 'chem': '' } 使用下列遍历的方法删除: 1. for...

python退出命令是什么?详解python退出方法

python退出命令是什么?详解python退出方法

在win上经常会用到上面的编程语言的,那么如何进行退出成了新手的麻烦的,特别是不记得朋友的。在下介绍一下退出的方法。 1、先在终端上,找到这个【>>>】提示,如下图。...

python正则表达式去掉数字中的逗号(python正则匹配逗号)

分析 数字中经常是3个数字一组,之后跟一个逗号,因此规律为:***,***,*** 正则式复制代码 代码如下:[a-z]+,[a-z]? 复制代码 代码如下:import re sen...