สมมติว่าเรามีลำดับการข้ามผ่านคำสั่งภายหลังของแผนผังการค้นหาแบบไบนารี เราต้องสร้างต้นไม้จากลำดับเหล่านี้ ดังนั้น ถ้าลำดับภายหลังคือ [9,15,7,20,3] ต้นไม้จะเป็น −
ในการสร้างต้นไม้ เราจำเป็นต้องมีการข้ามผ่านแบบไม่เรียงลำดับด้วย แต่สำหรับทรีการค้นหาแบบไบนารี การข้ามผ่านแบบไม่เรียงลำดับจะอยู่ในรูปแบบที่จัดเรียง
ให้เราดูขั้นตอน -
-
Inorder =รายการเรียงลำดับของการข้ามผ่านภายหลัง
-
กำหนดวิธีการ build_tree() ซึ่งจะใช้เวลาไม่เป็นระเบียบ ลำดับภายหลัง -
-
หากรายการ inorder ไม่ว่างเปล่า −
-
root :=สร้างโหนดทรีด้วยค่าสุดท้ายของ postorder จากนั้นลบองค์ประกอบนั้น
-
ind :=ดัชนีของข้อมูลรูทในรายการไม่เรียงลำดับ
-
ทางขวาของรูท :=build_tree(inorder จากดัชนี ind ถึง end, postorder)
-
ด้านซ้ายของ root :=build_tree(ไม่เรียงลำดับจาก 0 ถึงดัชนี ind - 1, postorder)
-
-
คืนค่ารูท
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def print_tree(root): if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) class Solution(object): def buildTree(self, inorder, postorder): if inorder: root = TreeNode(postorder.pop()) ind = inorder.index(root.data) root.right = self.buildTree(inorder[ind+1:],postorder) root.left = self.buildTree(inorder[:ind],postorder) return root ob1 = Solution() postorder = [3,9,20,15,7] inorder = list(sorted([3,9,20,15,7])) print_tree(ob1.buildTree(inorder, postorder))
อินพุต
[9,3,15,20,7] [9,15,7,20,3]
ผลลัพธ์
[3,7,9,15,20]
