羅德興老師的教學歷程檔案 - 中華科技大學數位化學習歷程

'''

# Binarytree Module in Python

A binary tree is a data structure in which every node or vertex has atmost two children.

In Python, a binary tree can be represented in different ways with different data structures(dictionary, list) and class representation for a node.

However, binarytree library helps to directly implement a binary tree. It also supports heap and binary search tree(BST). This module does not come pre-installed with Python’s standard utility module. To install it type the below command in the terminal.

pip install binarytree

Creating Node

The node class represents the structure of a particular node in the binary tree. The attributes of this class are values, left, right.

Syntax: binarytree.Node(value, left=None, right=None)

Parameters:

value: Contains the data for a node. This value must be number.

left: Conatins the details of left node child.

right: Contains details of the right node child

Note: If left or right child node is not an instance of binarytree.Node class then binarytree.exceptions.NodeTypeError is raised and if the node value is not a number then binarytree.exceptions.NodeValueError is raised.

'''

# This is ch06-tree.py by 0000000XXX (學號) YYYYYY(姓名) on 2020/06/05

# This is 展示 Bibary tree (二元樹)的實作

# 程式的前兩行務必註明：學號、姓名、題號、及用途

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)

# EX6-1. 從一個 list 的 10 個數值依序填滿建立一個二元樹，並印出其值。

# 使用 from binarytree import build

'''

Build a binary tree from the List

Instead of using the Node method repeatedly, we can use build() method to convert a list of values into a binary tree.

Here, a given list contains the nodes of tree such that the element at index i has its left child at index 2*i+1, the right child at index 2*i+2 and parent at (i - 1)//2. The elements at index j for j>len(list)//2 are leaf nodes. None indicates the absence of a node at that index. We can also get the list of nodes back after building a binary tree using values attribute.

Syntax: binarytree.build(values)

Parameters:

values: List representation of the binary tree.

Returns: root of the binary tree.

'''

# Creating binary tree

# from given list

from binarytree import build

print ('Ex6-1 \n')

# List of nodes

nodes =[3, 6, 8, 2, 11, None, 13]

# Builidng the binary tree

binary_tree = build(nodes)

print('Binary tree from list :\n',

binary_tree)

# Getting list of nodes from

# binarytree

print('\nList from binary tree :',

binary_tree.values)

# EX6-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.

'''

from binarytree import tree

print ('Ex6-2 \n')

# Create a random binary

# tree of any height

root = tree()

print("Binary tree of any height :")

print(root)

# Create a random binary

# tree of given height

root2 = tree(height = 2)

print("Binary tree of given height :")

print(root2)

# Create a random perfect

# binary tree of given height

root3 = tree(height = 2,

is_perfect = True)

print("Perfect binary tree of given height :")

print(root3)

# EX6-3. 輸入樹高，建立一個二元搜尋樹，並印出其值。

# 使用 from binarytree import bst

'''

Building a BST

The binary search tree is a special type of tree data structure whose inorder gives a sorted list of nodes or vertices. In Python, we can directly create a BST object using binarytree module. bst() generates a random binary search tree and return its root node.

Syntax: binarytree.bst(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 BST.

'''

from binarytree import bst

print ('Ex6-3 \n')

# Create a random BST

# of any height

root = bst()

print('BST of any height : \n',

root)

# Create a random BST of

# given height

root2 = bst(height = 2)

print('BST of given height : \n',

root2)

# Create a random perfect

# BST of given height

root3 = bst(height = 2,

is_perfect = True)

print('Perfect BST of given height : \n',

root3)

# EX6-4. 輸入樹高，建立一個二元搜尋樹，並印出其值。

# 使用 from binarytree import heap

'''

Importing heap

Heap is a tree data structure that can be of two types –

max heap

min heap

Using the heap() method of binarytree library, we can generate a random maxheap and return its root node. To generate minheap, we need to set the is_max attribute as False.

Syntax: binarytree.heap(height=3, is_max=True, is_perfect=False)

Parameters:

height: It is the height of the tree and its value can be between the range 0-9 (inclusive)

is_max: If set True generates a max heap else min heap.

is_perfect: If set True a perfect binary is created.

Returns: Root node of the heap.

'''

from binarytree import heap

print ('Ex6-4 \n')

# Create a random max-heap

root = heap()

print('Max-heap of any height : \n',

root)

# Create a random max-heap

# of given height

root2 = heap(height = 2)

print('Max-heap of given height : \n',

root2)

# Create a random perfect

# min-heap of given height

root3 = heap(height = 2,

is_max = False,

is_perfect = True)

print('Perfect min-heap of given height : \n',

root3)

'''

作業6：

# EX6-1. 從一個 list 的 10 個數值依序填滿建立一個二元樹，並印出其值。

# 使用 from binarytree import build

# EX6-2. 輸入樹高，建立一個亂數數值的二元樹，並印出其值。

# 使用 from binarytree import tree

# EX6-3. 輸入樹高，建立一個二元搜尋樹，並印出其值。

# 使用 from binarytree import bst

# EX6-4. 輸入樹高，建立一個二元搜尋樹，並印出其值。

# 使用 from binarytree import heap

# EX6-5. 使用前序追蹤該二元樹 (MLR)

# EX6-6. 使用中序追蹤該二元樹 (LMR)

# EX6-7. 使用後序追蹤該二元樹 (LRM)

'''

Binary Tree