|
羅德興老師的教學歷程檔案 - 112-2 資料結構 (2024年) - Unit 7 樹 (Tree) |
|
|
|
|
Unit 7 樹 (Tree)範例與作業 一、 # This is ds-ex7-0(tree).ipynb by 0000000XXX (學號) YYYYYY(姓名) on 2023/05/15 # This is 展示 Bibary tree (二元樹)的實作 (土法煉鋼) # 程式的前兩行務必註明：學號、姓名、題號、及用途 # 資料來源：https://github.com/abg3/Python-Data-Structures/blob/master/Python%20Data%20Structures%20-%20Binary%20Trees.ipynb ''' The Node class has three attributes: self.value self.left self.right ''' class Node(object): def __init__(self, value): self.value = value self.left = None self.right = None class BinaryTree(object): def __init__(self, root): self.root = Node(root) def print_tree(self, traversal_type): if traversal_type == "preorder": return self.preorder_print(tree.root, "") elif traversal_type == "inorder": return self.inorder_print(tree.root, "") elif traversal_type == "postorder": return self.postorder_print(tree.root, "") else: print("Traversal type " + str(traversal_type) + " is not supported.") return False def preorder_print(self, start, traversal): """Root->Left->Right""" if start: traversal += (str(start.value) + "-") traversal = self.preorder_print(start.left, traversal) traversal = self.preorder_print(start.right, traversal) return traversal def inorder_print(self, start, traversal): """Left->Root->Right""" if start: traversal = self.inorder_print(start.left, traversal) traversal += (str(start.value) + "-") traversal = self.inorder_print(start.right, traversal) return traversal def postorder_print(self, start, traversal): """Left->Right->Root""" if start: traversal = self.postorder_print(start.left, traversal) traversal = self.postorder_print(start.right, traversal) traversal += (str(start.value) + "-") return traversal # 1-2-4-5-3-6-7- # 4-2-5-1-6-3-7 # 4-5-2-6-7-3-1 # 1 # / \ # 2 3 # / \ / \ # 4 5 6 7 # Set up tree: tree = BinaryTree(1) tree.root.left = Node(2) tree.root.right = Node(3) tree.root.left.left = Node(4) tree.root.left.right = Node(5) tree.root.right.left = Node(6) tree.root.right.right = Node(7) print('Preorder:\n',tree.print_tree("preorder")) print('Inorder:\n', tree.print_tree("inorder")) print('Postorder:\n', tree.print_tree("postorder")) print(tree.print_tree("laworder")) 二、 # This is ds-ex7-1(tree).ipynb by 0000000XXX (學號) YYYYYY(姓名) on 2023/05/15 # This is 展示 Bibary tree (二元樹)的實作 # 程式的前兩行務必註明：學號、姓名、題號、及用途 ''' 作業7： # EX7-1. 從一個 list 的 10 個數值 依序填滿建立一個二元樹，並印出其值。 # 使用 from binarytree import build # EX7-2. 輸入樹高，建立一個亂數數值的二元樹，並印出其值。 # 使用 from binarytree import tree # EX7-3. 輸入樹高，建立一個二元搜尋樹，並印出其值。 # 使用 from binarytree import bst # EX7-4. 輸入樹高，建立一個二元搜尋樹，並印出其值。 # 使用 from binarytree import heap # EX7-5. 使用前序追蹤該二元樹 (MLR) # EX7-6. 使用中序追蹤該二元樹 (LMR) # EX7-7. 使用後序追蹤該二元樹 (LRM) ''' # !pip install binarytree --upgrade from binarytree import Node root = Node(3) root.left = Node(6) root.right = Node(8) # Getting binary tree print('Binary tree (二元樹) :', root) # Getting list of nodes print('List of nodes (列出節點) :', list(root)) # Getting inorder of nodes print('Inorder of nodes (節點的中序) :', root.inorder) # Checking tree properties print('Size of tree (樹的大小) :', root.size) print('Height of tree (樹的高度):', root.height) # Get all properties at once print('Properties of tree (樹的屬性): \n', root.properties) 三、 # This is ds-ex7-2(tree).ipynb by 0000000XXX (學號) YYYYYY(姓名) on 2023/05/15 # This is 展示 Bibary tree (二元樹)的實作 # 程式的前兩行務必註明：學號、姓名、題號、及用途 # EX7-2. 輸入樹高，建立一個亂數數值的二元樹，並印出其值。 # 使用 from binarytree import tree ''' Build a random binary tree tree() generates a random binary tree and returns its root node. Syntax: binarytree.tree(height=3, is_perfect=False) Parameters: height: It is the height of the tree and its value can be between the range 0-9 (inclusive) is_perfect: If set True a perfect binary is created. Returns: Root node of the binary tree. ''' # !pip install binarytree --upgrade from binarytree import tree print ('Ex7-2 \n') # Create a random binary # tree of any height root3 = tree(height = 3, is_perfect = True) print("Perfect binary tree of given height :") print('root3:', root3) # 建立 樹的節點 from binarytree import Node print('建立 樹 的節點 中...... ') root = Node(3) root.left = Node(6) root.right = Node(8) root[1] = Node(5) root[1].left = Node(15) root[1].right = Node(7) root[2] = Node(9) root[2].left = Node(10) root[2].right = Node(2) print('建立 樹 的節點 完畢\n') for i in range (0,3,1): print('現在是 Root : %d 的子樹 \n ' % i) print (root[i]) print (root[i].left) print (root[i].right)
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 中華科技大學數位化學習歷程 - 意見反應 |  |
