數據基礎結構 13

郭煒信息科學技術學院數據結構與算法

(Python描述)課程信息教材數據結構與算法（Python語言實現）郭煒編著清華大學出版社另有Java語言實現，C/C++語言實現兩本，均已經由清華大學出版社出版樹、森林和并查集信息科學技術學院3樹信息科學技術學院首都機場西湖園樹的概念5每個結點可以有任意多棵不相交的子樹子樹有序，從左到右依次是子樹1,子樹2......二叉樹的結點在只有一棵子樹的情況下，要區分是左子樹還是右子樹。樹的結點在只有一棵子樹的情況下，都算其是第1棵子樹(所以二叉樹不是樹)支持廣度優先遍歷、前序遍歷(先處理根結點，再依次處理各個子樹）和后序遍歷（先依次處理各個子樹，再處理根結點），中序遍歷無明確定義樹的性質6結點度數最多為K的樹，第i層最多Ki個結點(i從0開始）。結點度數最多為K的樹，高為h時最多有(Kh+1-1)/(k-1)個結點。n個結點的K度完全樹，高度h是logk

(n)向下取整n個結點的樹有n-1條邊樹的實現7直觀表示法：每個結點有一個變量存放數據，加上一個可變長列表存放所有子結點指針在不支持可變長列表的語言中，就要想別的辦法，比如用二叉樹來表示一棵樹的兒子-兄弟表示法父親表示法：把所有結點編號，在每個結點內記錄其父結點編號（用于并查集）樹的實現8直觀表示法：classTree: def__init__(self,data,*subtrees):#參數個數可變的函數

#參數subtrees是個元組，其中每個元素都是一個Tree對象

self.data=data self.subtrees=list(subtrees)#self.subtrees是子樹列表

defaddSubTree(self,tree):#tree是一個Tree對象

self.subtrees.append(tree) defpreorderTraversal(self,op): op(self) fortinself.subtrees: t.preorderTraversal(op) defpostorderTraversal(self,op): fortinself.subtrees: t.postorderTraversal(op) op(self)樹的實現9 defprintTree(self,level=0):#輸出樹的層次結構 print("\t"*level+str(self.data)) fortinself.subtrees: t.printTree(level+1)輸出形如：A B E C F G D H IBADEGCFHI例題：構建樹10讀入：A B E C F G D H I構建直觀表示法的樹BADECFHIG例題：構建樹構建一棵直觀表示法的樹defbuildTree(level):#讀取nodesPtr指向的那一行，并建立以其為根的子樹

#該根的層次是level。建好后，令nodesPtr指向該子樹的下一行

globalnodesPtr,nodes tree=Tree(nodes[nodesPtr][1])#建根結點

nodesPtr+=1#看下一行

whilenodesPtr<len(nodes)andnodes[nodesPtr][0]==level+1: tree.addSubTree(buildTree(level+1)) returntree11例題：構建樹nodes=[]whileTrue: try: s=input().rstrip() nodes.append((len(s)-1,s.strip())) except: breaknodesPtr=0#表示看到nodes里的第幾行print(nodes)tree=buildTree(0)nodes內容形如：[(0,'A'),(1,'B'),(2,'E'),(1,'C'),(2,'F'),(2,'G'),(1,'D'),(2,'H'),(3,'I')]元素為(縮進，數據)12樹的二叉樹表示法（兒子-兄弟表示法)13用二叉樹表示一棵樹T(二叉樹形式表示的樹，簡稱兒子兄弟樹)T的根就是二叉樹的根R，R不會有右結點R的左兒子S1，以及S1的左子樹，是T的第1棵子樹的二叉樹表示形式S1的右兒子S2，及S2的左子樹，是T的第2棵子樹的二叉樹表示形式S2的右兒子S3，及S3的左子樹，是T的第3棵子樹的二叉樹表示形式.............以此類推樹的二叉樹表示法（兒子-兄弟表示法)14用二叉樹B表示一棵樹T(二叉樹形式表示的樹，簡稱兒子兄弟樹)BADECFHIBADECFHIGG樹的前序遍歷序列，和其兒子兄弟樹的前序遍歷序列一致。樹的后序遍歷序列，和其兒子兄弟樹的中序遍歷序列一致。樹的直觀表示法轉兒子兄弟樹15deftreeToBinaryTree(tree):#直觀表示法的樹轉兒子兄弟樹。tree是Tree對象 bTree=BinaryTree(tree.data)#二叉樹講義中的BinaryTree foriinrange(len(tree.subtrees)): ifi==0: tmpTree=treeToBinaryTree(tree.subtrees[i]) bTree.addLeft(tmpTree) else: tmpTree.addRight(treeToBinaryTree(tree.subtrees[i])) tmpTree=tmpTree.right returnbTree所有結點復制了一份樹的兒子兄弟第表示法轉直觀表示法16defbinaryTreeToTree(biTree):#兒子兄弟樹轉直觀表示法的樹轉。biTree是BinaryTree對象 tree=Tree(biTree.data) son=biTree.left ifson: tree.addSubTree(binaryTreeToTree(son)) whileson.right: tree.addSubTree(binaryTreeToTree(son.right)) son=son.right returntree所有結點復制了一份例題：構建兒子兄弟樹17讀入：A B E C F G D H I構建二叉樹形式表示的樹(留作練習)BADEGCFHI信息科學技術學院瑞士馬特洪峰森林森林的概念19不相交的樹的集合，就是森林森林有序，有第1棵樹、第2棵樹、第3棵樹之分森林可以表示為樹的列表，也可以表示為一棵二叉樹森林的二叉樹表示法201)森林中第1棵樹的根，就是二叉樹的根S1，S1及其左子樹，是森林的第1棵樹的二叉樹表示形式2)S1的右子結點S2，以及S2的左子樹，是森林的第2棵樹的二叉樹表示形式3)S2的右子結點S3，以及S3的左子樹，是森林的第3棵樹的二叉樹表示形式.......以此類推森林的遍歷21廣度優先遍歷:ACHBDEIGF前序遍歷：ABCDEFHIG后續遍歷：BADFECIGH無中序遍歷BADECFGIH森林的二叉樹表示法22BADECFJIHABCDEFHIJ森林的前序遍歷序列，和其兒子兄弟樹的前序遍歷序列一致。森林的后序遍歷序列，和其兒子兄弟樹的中序遍歷序列一致。森林轉二叉樹23defwoodsToBinaryTree(woods):

#woods是個列表，每個元素都是一棵二叉樹形式的樹

biTree=woods[0] p=biTree foriinrange(1,len(woods)): p.addRight(woods[i]) p=p.right returnbiTree#biTree和woods共用結點,執行完后woods的元素不再是原兒子兄弟樹二叉樹轉森林24defbinaryTreeToWoods(tree):#tree是以二叉樹形式表示的森林 p=tree q=p.right p.right=None woods=[p] ifq: woods+=binaryTreeToWoods(q) returnwoodswoods是兄弟-兒子樹的列表,woods和tree共用結點執行完后tree的元素不再原兒子兄弟樹并查集信息科學技術學院25信息科學技術學院美國黃石公園并查集的原理和實現Disjoint-Set并查集N個不同的元素分布在若干個互不相交集合中，需要多次進行以下3個操作：1.合并a,b兩個元素所在的集合Merge(a,b)2.查詢一個元素在哪個集合3.查詢兩個元素是否屬于同一集合Query(a,b)27并查集操作示例OperationDisjointsets初始狀態{a}{b}{c}mgqgvsehbv9{e}{f}Merge(a,b){a,b}{c}mgqgvsehbv9{e}{f}Query(a,c)FalseQuery(a,b)TrueMerge(b,e){a,b,e}{c}mgqgvsehbv9{f}Merge(c,f){a,b,e}{c,f}mgqgvsehbv9Query(a,e)TrueQuery(c,b)FalseMerge(b,f){a,b,c,e,f}mgqgvsehbv9Query(a,e)TrueQuery(d,e)False28簡單算法給集合編號Query–O(1);Merge–O(N)OpElement{a}{b}{c}mgqgvsehbv9{e}{f}123456Merge(a,b)113456Merge(b,e)113416Merge(c,f)113413Merge(b,f)111411Query(a,e)29用樹表示集合的算法開始：Merge(a,b)Merge(b,e)abcdefabcdefabcdef30用樹表示集合的算法Merge(c,f)Merge(b,f)abcdefabcdefabcdef31用樹表示集合的算法設置數組parent,parent[i]=j表示元素i的父親是jparent[i]=i表示i是一棵樹的根結點若開始每個元素自成一個集合，則對任何i，都有parent[i]=i32abcdef用樹表示集合的算法基本操作GetRoot(a)求a的樹根defGetRoot(a):ifparent[a]==a:returnareturnGetRoot(parent[a])33用樹表示集合的算法Query(a,b)比較b和f所在樹的根結點是否相同Merge(a,b)將b的樹根的父親，設置為a的樹根缺點：樹的深度失控則查樹根可能太慢！34abcdO(N)!改進方法一合并兩棵樹時，把深度淺的樹直接掛在另一棵樹的根結點下面合并兩棵同深度的樹時，必然導致深度增加，不夠理想35改進方法二：路徑壓縮查詢一個結點的根時，直接將該結點到根路徑上的每個結點，都直接掛在根下面。經過多次查詢，很可能所有樹的深度都是<=236acbdacbdGetRoot(d)改進方法二：路徑壓縮改進方法二：路徑壓縮基本操作GetRoot(a)求a的樹根defGetRoot(a): ifparent[a]!=a: parent[a]=GetRoot(parent[a]) returnparent[a]38defGetRoot(a):#oldone

ifparent[a]==a:returnareturnGetRoot(parent[a])改進方法二：路徑壓縮parent=[iforiinrange(N)]defMerge(a,b):#把b樹根掛到a樹根下

parent[GetRoot(b)]=GetRoot(a)defQuery(a,b)

#查詢a,b是否位于同一棵樹

returnGetRoot(a)==GetRoot(b)并查集的空間復雜度O(N),時間復雜度就是GetRoot的復雜度39并查集的時間復雜度GetRoot的時間復雜度,是O(log(n))40信息科學技術學院福建省寧德市北岸公園并查集例題TheSuspects新疆喀拉峻鱷魚灣例題1：POJ1611TheSuspects有n個學生，編號0到n-1,以及m個團體，(0<n<=30000,0<=m<=500)一個學生可以屬于多個團體，也可以不屬于任何團體。一個學生得病，則它所屬的整個團體都會被他傳染而得病。開始只有0號學生得病。已知每個團體都由哪些學生構成，求最終一共多少個學生會得病。42SampleInput1004//100人,4團體212//本團體有2人，編號1,25101311121420129922002//200人,2團體15//本團體有1人，編號551234510//1人,0團體00//結束標記43SampleOutput411例題1：POJ1611TheSuspects三組數據，分別是:100個人，4個團體200個人,2個團體1個人,0個團體關鍵:互相感染的人，應該屬于同一個集合。一個集合中任意一人得病，全集合人都得病所有病人都是直接或間接被0號傳染，因此所有病人都和0號在同一集合開始每個人自成一個集合。a和b在同一個團體，就將a所在的集合和b所在的集合合并。最終問0所在的集合有幾個元素44例題1：POJ1611TheSuspectsMAX=30000parent=[0foriinrange(MAX+10)]total=[0foriinrange(MAX+10)]#total[GetRoot(a)]是a所在的group的人數defGetRoot(a):#獲取a的根,并把a的父結點改為根

ifparent[a]!=a: parent[a]=GetRoot(parent[a]) returnparent[a]defMerge(a,b): p1=GetRoot(a) p2=GetRoot(b) ifp1==p2: return total[p1]+=total[p2] parent[p2]=p1例題1：POJ1611TheSuspectswhileTrue: n,m=list(map(int,input().split())) ifn==0andm==0: break foriinrange(n): parent[i]=i total[i]=1 foriinrange(m): lst=list(