《主题TreeProblems.ppt》由会员分享,可在线阅读,更多相关《主题TreeProblems.ppt(48页珍藏版)》请在三一文库上搜索。
1、1,主題: Tree Problems,Tree structures Rooted trees 例題講解: H.90.2, A.615 Binary trees 例題講解: A.536, A.699 Undirected trees 例題講解: A.10459 歷年題目,2,Trees,常用的兩個定義 connected and no cycle n-1 edges and connected,3,Rooted trees,root,depth,0,1,2,3,存在一個特殊的 node 叫做 root 從 root 往下長出數量不等且互不相連的 child nodes 這些 nodes 再各
2、自往下長出互不相連的 child nodes,4,Terminology,parent,child,一條 edge 所連接的兩個 nodes,上面的是 parent,下面的是 child 根據應用,有時候我們會定義所有 edge 是由 parent 指向 child,有時候會定義是由 child 指向 parent,5,Terminology (cont.),若 node u 可以往下走到 node v,則 u 為 v 的 ancestor,v 為 u 的 descendent 自己會是自己的 ancestor,也會是自己的 descendent Node u 的所有 descendents
3、合起來稱為 u 的 subtree,而 u 就是此 subtree 的 root,subtree,ancestor,descendent,6,Representation,parent 陣列: parenti 記錄第 i 個 node 的 parent 是哪一個 node children 陣列: childreni 記錄第 i 個 node 的 children list,0,1,2,3,4,5,6,7,8,9,10,11,node,parent,0,0,0,1,1,1,4,4,2,2,8,9,children,如何存放 children list?,7,Representation,0,1
4、,2,3,4,5,6,7,8,9,10,11,parent,children,0,0,1,1,1,4,4,2,2,8,9,1,2,null,3,4,5,null,8,9,null,null,6,7,null,null,null,null,3,null,3,null,null,null,0,1,2,3,4,5,6,7,8,9,10,11,8,Children lists,將 children list 集中存在一個陣列內 按照出現順序直接將每個 child 放到 edge 陣列中,並用 sibling 陣列記錄每個 child 在 children list 的下一個 node,9,7,8,6,
5、1,2,10,5,3,11,4,2,3,5,8,10,edge,sibling,9,Children lists (sorted),將 children list 集中存在一個陣列內 將屬於同一個 parent 的 children list 集中連續放置,每個 node 記住自己的 children list 在 edge 陣列所在的位置及 children 個數,1,2,3,4,5,8,9,6,7,10,11,0,2,5,7,9,10,children-first,edge,2,3,2,0,2,0,0,0,1,1,0,0,degree,10,常見的 input 格式,所有 edges 以任
6、意順序輸入,如: (2, 9), (4, 7), (2, 8), (4, 6), (0, 1), (0, 2), (8, 10), (1, 5), (1, 3), (9, 11), (1, 4) 有時候會規定一個 parent 的所有 children 在 children list 中的排列次序,如依 node id 的大小或是出現順序等等 如何整理成可用的 children list?,11,整理成 list 形式,last-child: last-childi 記錄 node i 已出現的 children 中,最後一個在 edge 陣列中的位置 要是又出現 node i 的 child
7、,就可以把 sibling 接起來,9,7,8,6,1,2,10,5,3,11,4,2,3,5,8,10,4,7,0,1,6,9,last-child,node,sibling,children,4,7,0,1,6,9,5,8,10,2,3,.,.,12,整理成連續形式,對 edge 陣列做 sort,可以同時完成連續擺放與符合規定順序兩種效果 整理規則 (sorting) 當兩 edge 的 head (parent) 不同時 head 較小的放在前面 當兩 edge 的 head (parent) 相同時 題目如規定依 child 大小順序,由 tail 決定 題目如規定依出現次序,需記住
8、出現次序加以比較或使用 stable sort,13,整理成連續次序 (cont.),需額外記住每條 edge 的 head 以做比較 整理之前 整理之後,0,1,2,3,4,5,6,7,8,9,10,edge,edge-head,edge-tail,0,1,0,2,1,3,1,4,1,5,2,8,2,9,4,6,4,7,8,10,9,11,node 順序,依 id 大小,0,1,2,3,4,5,6,7,8,9,10,edge,edge-head,edge-tail,2,9,4,7,2,8,4,6,0,1,0,2,8,10,1,5,1,3,9,11,1,4,14,例題講解: H.90.2 (h
9、ttp:/www.cc.nccu.edu.tw/info_race90/finalprogram.pdf),給予一棵王室的家族樹,同一個父親的兒子年紀是由左到右遞減排序,將王位的繼承順位照順序列出 (包括現任),15,繼承規則,當現任國王死後 先考慮其兒子,年紀由大到小 再考慮其弟弟,年紀由大到小 再來是國王父親的弟弟們,年紀由大到小 再來是國王祖父的弟弟們,年紀由大到小 如現任國王為 Charles,則接下來是: William, Edward, Adam, Benjamin, Peter, Chris, Bill,16,Input format,先給予現任國王的名字 再來每次給予一對父子配
10、對,如: Tom John,而且沒有一定的給予順序 同一個父親的兒子們,先出現的年紀較大,如: Tom John Tom Charles 則 John 的年紀 (順位) 大於 Charles,17,直覺想法,每個 node 的名字都是字串而非數字,如何存放?,18,Re-labeling,把不能當作陣列 index 的文字 (或數字),轉換成範圍在 0 n 1 的 node index 準備一個文字的對應表 (mapping),每看到一個字串,就到表中查詢是否已經出現過,如果出現過就回報對應此字串的 index,否則就新增一筆對應資料,19,Charles Peter Allen Charle
11、s William George Tom Charles Edward Tom John George Peter Tom Charles Tom Adam Chris James George Chris Tom Benjamin,Re-labeling (cont.),建完後照名字 sort,Linear Search,Binary Search,ID 名字,名字 ID,20,例題講解: A.615 (http:/acm.uva.es/p/v6/615.html),給一堆 edge (u, v),代表 u v,數量次序不拘,依照下列規則判斷是否為 rooted tree (假設 edge
12、方向由 parent 指向 child) 沒有任何 node 也算 tree 如有 node,必有一個特殊的 node 為 root 除了 root 以外每個 node 的 in-degree (指向這個 node 的 edge 數目) 皆為 1 從 root 出發到任何一個 node 都只有一條唯一的路可走,21,Sample input/output,u, v 皆為大於 0 的 integer,如: 3 8 6 8 6 4 5 3 5 6 5 2 0 0 1 2 2 50000 1 1000 0 0 -1 -1 Case 1 is not a tree Case 2 is a tree,c
13、ase 結束,input 結束,22,解題方法,Re-labeling: 由於 node 的數字除了大於 0 以外沒有範圍,所以需要做 re-labeling 來將每個數字轉換成 0 到 n 1 的 node id (n 為 node 個數) 條件一: 找到 in-degree 為 0 的 node 視為 root 條件二: 檢查其他 node 的 in-degree 是否為 1,23,檢查第三項條件,從 root 出發做 DFS 檢查所有 nodes 是否 connected connected 代表為 tree 請注意: 一棵 tree 加上一些 cycles 也會通過前兩項檢查,但不會是
14、 connected,0,1,2,3,4,5,6,7,8,9,10,11,24,Binary trees,是 rooted tree 的一種 每個 node 只會往下長出最多兩個 children 左邊的稱為 left child 其 subtree 為 left subtree 右邊的稱為 right child 其 subtree 為 right subtree,root,right child,left child,25,Representation,每一個 node 記錄自己的 left child 和 right child (parent 則看需求而定),26,Traversal
15、order,對一棵 binary tree 上的任何一個 node v 及其 children leftv 和 rightv 來說,不同的 traverse 順序代表著不同的意義 node v 先於 leftv 先於 rightv: preorder leftv 先於 node v 先於 rightv: inorder leftv 先於 rightv 先於 node v: postorder left child 優先於 right child,27,Traversal order (cont.),Traverse (v) return; ,visit v; Traverse(leftv);
16、Traverse(rightv);,Traverse(leftv); visit v; Traverse(rightv);,Traverse(leftv); Traverse(rightv); visit v;,/ preorder traversal,/ inorder traversal,/ postorder traversal,28,Preorder traversal,preorder traversal 的特徵在於 subtree 的 root 會先處理自己的資料,才去處理自己的所有 descendent,所以可以把自己算好的資料往下傳遞 適合在 tree 上進行 top-down
17、 式的計算,例如計算每一個 node 的深度 (depth),29,Preorder sequence,e,d,h,b,a,c,g,i,f,j,如果將 visit 的動作設為輸出 node 上的字元,就會得到一組 sequence preorder traversal 的動作是看到就先做,會輸出,e,d,b,a,c,h,g,f,i,j,30,Postorder traversal,postorder traversal 的特徵在於 subtree 的 root 會等自己的所有 descendent 都處理完畢之後,才去處理自己的資料,所以可以把下面算好的資料傳回來 (往上) 適合在 tree
18、上進行 bottom-up 式的計算,例如將 tree 上每個 node 的數字做加總 (每個 node 將自己的數字和 subtree 的數字總合加總之後往上傳),31,Postorder sequence,e,d,h,b,a,c,g,i,f,j,a,c,b,d,f,g,j,i,h,e,如果將 postorder traversal 的 visit 動作設為輸出 node 上的字元,就會得到 postorder sequence,32,Inorder traversal,inorder traversal 是一個只定義在 binary tree 上的特殊 traversal 順序,所以用途上
19、也比較受限 可以將 binary tree 上的資料根據 binary tree 被壓扁之後的順序由左至右的輸出 也可以將 binary search tree 上的資料由小到大輸出,33,Inorder sequence,e,d,h,b,a,c,g,i,f,j,如果將 inorder traversal 的 visit 動作設為輸出 node 上的字元,就會得到 inorder sequence,a,b,c,d,e,f,g,h,i,j,A binary search tree,34,例題講解: A.536 (http:/acm.uva.es/p/v5/536.html),給定某個 binar
20、y tree 的 preorder sequence 與 inorder sequence,要求輸出 postorder sequence 類題: 給 inorder 和 postorder sequences,要求還原出整個 binary tree,35,解題方法,preorder: inorder: postorder:,tree construction,traversal,36,Tree construction,利用兩種 traversal order 的特性 preorder: sequence 中第一個 node 一定是 root inorder: 在 sequence 中,ro
21、ot 的前面是 left subtree 的 inorder sequence,而後面是 right subtree 的 inorder sequence 來回的檢視兩個 sequence 來判定 tree 上的 parent-child 關係 Implement: 利用 recursive call,37,Tree construction: root,preorder,inorder,tree root,D,38,Tree construction: left subtree,preorder,left tree inorder,subtree root,D,B,39,例題講解: A.69
22、9 (http:/acm.uva.es/p/v6/699.html),按照 preorder 的順序給一棵 binary tree,沒有 child 的地方會標 -1,如: 先出現的是 root 5 再來是 5 的 left subtree 7 再來應是 7 的 left subtree,因為缺乏所以填 -1 再來是 7 的 right subtree 6 6 的左右都是 -1,表示 6 是個 leaf 輸出定義在這棵 tree 上的一些數據 (省略),5,7,-1,6,-1,-1,3,-1,-1,40,Tree construction,5,7,-1,6,-1,-1,3,-1,-1,5,7,
23、3,6,直接對 input 做 recursive call,用 preorder 的順序建造 node,但是用 postorder 的順序把 edge 接上,41,Undirected trees,不存在 root,每一條 edge 都沒有方向,沒有分 parent 和 child 任兩個 node 間的 path 都只有一條,degree = 4,degree = 1,42,Representation,neighbor 陣列: neighbori 記錄 node i 的 neighbor list (注意: 當輸入一條 edge (u, v) 時,把它變成兩條 edge u v 和 v
24、u),1,2,null,3,4,5,null,null,null,6,7,null,null,null,null,0,1,2,3,4,5,6,7,0,1,2,5,4,3,6,7,0,0,1,1,1,4,4,null,8,2,8,8,43,例題講解: A.10459 (http:/acm.uva.es/p/v104/10459.html),Rooted tree 的 height 為由 root 到最遠的 leaf 時,所需要經過的總 edge 數目 對一棵 undirected tree 來說,若任意指定其中一個 node 為 root,就可以將 tree 轉換成一個 rooted tree
25、給定一棵 undirected tree 的 neighbor list,求出使 height 最小以及最大的所有 node,44,Sample input,9 2 1 2 4 0 3 4 5 2 0 8 1 1 3 1 6 7 1 1 1 4 1 4 1 2,neighbor list 的長度,45,解題技巧,Diameter path: 在 tree 上相距最遠的兩點 之間的 path (unweighted 或 weighted 的距離都可以),可能不只一條 Point center: diameter path 的中點,可能在 node 上或 edge 中間 Node center:
26、離 point center 最靠近的 node (最多只有兩個),46,解題技巧 (cont.),A.10459 所給的是 undirected tree,要找使 height 最小及最大的 roots 使 height 最小的 root 就是 node center,最多會有兩個 使 height 最大的 root 就是 diameter path 的端點,由於 diameter path 可能不只一條,所以端點可能會有好幾個 從 edge center u 出發,所有diameter path 的端點都是離 u 最遠的點,47,Diameter path 的找法,任取 tree 上一個
27、node v,找出離 v 最遠的 node u (任一個) DFS 找出離 u 最遠的 node w (任一個),則 u 到 w 為一條 diameter path DFS 如何找出題目所求的點? DFS,48,歷年題目,練習題 H.90.2 王位繼承 http:/www.cc.nccu.edu.tw/info_race90/finalprogram.pdf A.615 Is It A Tree? http:/acm.uva.es/p/v6/615.html A.536 Tree Recovery http:/acm.uva.es/p/v5/536.html A.112 Tree Summing http:/acm.uva.es/p/v1/112.html A.115 Climbing Trees http:/acm.uva.es/p/v1/115.html 挑戰題 A.679 Dropping Balls http:/acm.uva.es/p/v6/679.html 歷年題目 無,
链接地址:https://www.31doc.com/p-2714445.html