python樹(shù)的同構(gòu)學(xué)習(xí)筆記
一、題意理解
給定兩棵樹(shù)T1和T2。如果T1可以通過(guò)若干次左右孩子互換就變成T2,則我們稱兩棵樹(shù)是“同構(gòu)的”。現(xiàn)給定兩棵樹(shù),請(qǐng)你判斷它們是否是同構(gòu)的。
輸入格式:輸入給出2棵二叉樹(shù)的信息:
先在一行中給出該樹(shù)的結(jié)點(diǎn)樹(shù),隨后N行
第i行對(duì)應(yīng)編號(hào)第i個(gè)結(jié)點(diǎn),給出該結(jié)點(diǎn)中存儲(chǔ)的字母、其左孩子結(jié)點(diǎn)的編號(hào)、右孩子結(jié)點(diǎn)的編號(hào)
如果孩子結(jié)點(diǎn)為空,則在相應(yīng)位置給出“-”
如下圖所示,有多種表示的方式,我們列出以下兩種:
二、求解思路
搜到一篇也是講這個(gè)的,但是那篇并沒(méi)有完全用到單向鏈表的方法,所以研究了一下,寫(xiě)了一個(gè)是完全用單向鏈表的方法:
其實(shí)應(yīng)該有更優(yōu)雅的刪除整個(gè)單向列表的方法,比如頭設(shè)為none,可能會(huì)改進(jìn)下?
# python語(yǔ)言實(shí)現(xiàn) L1 = list(map(int, input().split())) L2 = list(map(int, input().split())) # 節(jié)點(diǎn) 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 # 為了訪問(wèn)私有類 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()
以上就是本次介紹的全部?jī)?nèi)容知識(shí)點(diǎn),相關(guān)內(nèi)容可以參閱下方知識(shí)點(diǎn),感謝大家對(duì)腳本之家的支持。
相關(guān)文章
關(guān)于PyCharm安裝后修改路徑名稱使其可重新打開(kāi)的問(wèn)題
這篇文章主要介紹了關(guān)于PyCharm安裝后修改路徑名稱使其可重新打開(kāi)的問(wèn)題,本文通過(guò)圖文實(shí)例相結(jié)合給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-10-10Python3連接SQLServer、Oracle、MySql的方法
這篇文章較詳細(xì)的給大家介紹了Python3連接SQLServer、Oracle、MySql的方法,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2018-06-06Python實(shí)現(xiàn)重建二叉樹(shù)的三種方法詳解
這篇文章主要介紹了Python實(shí)現(xiàn)重建二叉樹(shù)的三種方法,結(jié)合實(shí)例形式分析了Python重建二叉樹(shù)的實(shí)現(xiàn)方法、操作技巧與注意事項(xiàng),需要的朋友可以參考下2018-06-06PyQt5?python?數(shù)據(jù)庫(kù)?表格動(dòng)態(tài)增刪改詳情
這篇文章主要介紹了PyQt5?python?數(shù)據(jù)庫(kù)?表格動(dòng)態(tài)增刪改詳情,首先手動(dòng)連接數(shù)據(jù)庫(kù)與下一個(gè)的程序連接數(shù)據(jù)庫(kù)是獨(dú)立的2個(gè)部分,下面來(lái)看看文章的詳細(xì)介紹2022-01-01python中pycryptodome模塊實(shí)現(xiàn)加密算法庫(kù)
PyCryptodome提供了許多密碼學(xué)算法和協(xié)議的實(shí)現(xiàn),包括對(duì)稱加密、非對(duì)稱加密、消息摘要、密碼哈希、數(shù)字簽名等,本文主要介紹了python中pycryptodome模塊實(shí)現(xiàn)加密算法庫(kù),感興趣的可以了解一下2023-11-11Python用threading實(shí)現(xiàn)多線程詳解
這篇文章主要給大家介紹了Python用threading實(shí)現(xiàn)多線程的方法示例,文中介紹的很詳細(xì),對(duì)大家具有一定的參考借鑒價(jià)值,有需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2017-02-02