Friday 6 December 2013
Week 9
'''
This week we talk about the main idea for three sorts,
which is selection sort, merge sort, and quick sort.
Selection Sort is a simple and intuitive sorting algorithm.
First, find the smallest unsorted sequence (large) elements
stored in the collating sequence of the starting position,
and then again from the remaining unsorted elements continue
to look for the smallest (large) elements, and then sorted into
the end of the sequence. And so on until all the elements are sorted.
Merge sort, divide the list in half, sort the halves, then merge the
sorted results, i think it should be easy done by use recursion. By the way,
the efficiency of merger sort is just after quick sort, it is a stable s
sorting algorithm, generally used for general disorder, but each child is
relatively orderly sequence.
Quick sort, which is fastest in almost all case , but not the worst case.
the main idea of quick sort is choose a pivot; decide where the pivot goes
with respect to the rest of the list, repeat on the partition.
'''
This week we talk about the main idea for three sorts,
which is selection sort, merge sort, and quick sort.
Selection Sort is a simple and intuitive sorting algorithm.
First, find the smallest unsorted sequence (large) elements
stored in the collating sequence of the starting position,
and then again from the remaining unsorted elements continue
to look for the smallest (large) elements, and then sorted into
the end of the sequence. And so on until all the elements are sorted.
Merge sort, divide the list in half, sort the halves, then merge the
sorted results, i think it should be easy done by use recursion. By the way,
the efficiency of merger sort is just after quick sort, it is a stable s
sorting algorithm, generally used for general disorder, but each child is
relatively orderly sequence.
Quick sort, which is fastest in almost all case , but not the worst case.
the main idea of quick sort is choose a pivot; decide where the pivot goes
with respect to the rest of the list, repeat on the partition.
'''
Week 8
''' In the class we talking about the 'big O' notation,
which describes the limiting behavior of the function
when the argument trends towards a particular value of infinity
example :
f(x)= 3x^4 - 2x^3 + 1 ;
if we wanna simply function , using O notation, the highest growth rate is
3x^4, and we take x^4 from 3x^4. Thus, we say that f(x) is a 'big-O' of (x^4),
can be write as f(x)=O(x^4).
And from class we know O(1) ∈ O(lg n) ∈ O(n) ∈ O(n^2) ∈ O(n^3) ∈ O(2^n) ∈ O(n^n)
Also we learn the binary search tree(BST), there is some properties of BST(from Wikipedia):
in a list of size n is x=log_2 (n). the logarithm base two of n.
'''
'''
class BST:
def __init__(self, container=[]):
self.root = None
for item in container:
self.insert(item)
def __str__(self):
return BST._str("",self.root)
def _str(indent, root):
if root is None:
return ""
else:
return (BST._str(indent + "\t", root.right) +
indent + repr(root.item) + "\n" +
BST._str(indent + "\t", root.left))
def insert(self, item):
parent, current = None, self.root
while current is not None and current.item != item:
if item < current.item:
parent, current = current, current.left
else:
parent, current = currrnt, curren.right
if current is None:
parent = _BSTNode(item)
if parent is None:
self.root = current
elif item < parent.item:
parent.left = current
else:
parent.right = current
class _BSTNode:
"""A node in a BST."""
def __init__(self, item, left=None, right=None):
"""(_BSTNode, object, _BSTNode, _BSTNode) -> NoneType
Initialize this node to store item and have children left and right.
"""
self.item = item
self.left = left
self.right = right
'''
'''
x = _BSTNode(1,_BSTNode(2,_BSTNode(4),_BSTNode(7)),_BSTNode(3,_BSTNode(6),_BSTNode(5)))
print(x)
y = BST([1,2,3,4])
y.insert(2)
y.insert(1)
y.insert(9)
y.insert(5)
y.insert(4)
print(y._str(y.root))
'''
class BTNode:
"""Binary Tree node."""
"""initial the Binary tree node"""
def __init__(self: 'BTNode', data: object,
left: 'BTNode'=None, right: 'BTNode'=None) -> None:
"""Create BT node with data and children left and right."""
self.data, self.left, self.right = data, left, right
def __repr__(self: 'BTNode') -> str:
"""Represent this node as a string."""
return ('BTNode(' + str(self.data) + ', ' + repr(self.left) +
', ' + repr(self.right) + ')')
def is_leaf(self: 'BTNode') -> bool:
"""Is this node a leaf?"""
return self.data and not self.left and not self.right
"""
this line equal to
if self.data != None and self.left == None and self.right == None:
return True
else:
return False
>>>x=BTNode(1)
>>>print(x.is_leaf())
True
"""
"""binary search tree ADT"""
class BST:
"""Binary search tree."""
def __init__(self: 'BST', root: BTNode=None) -> None:
"""Create BST with BTNode root.
initial self to None, if dont hv BTNode
"""
self._root = root
def __repr__(self: 'BST') -> str:
"""Represent this binary search tree."""
return 'BST(' + repr(self._root) + ')'
def find(self: 'BST', data: object) -> BTNode:
"""Return node containing data, otherwise return None."""
return _find(self._root, data)
def insert(self: 'BST', data: object) -> None:
"""Insert data, if necessary, into this tree.
>>> b = BST()
>>> b.insert(8)
>>> b.insert(4)
>>> b.insert(2)
>>> b.insert(6)
>>> b.insert(12)
>>> b.insert(14)
>>> b.insert(10)
>>> b
BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
BTNode(12, BTNode(10, None, None), BTNode(14, None, None))))
"""
def __insert(node, data):
return_node = node
if not node:
return_node = BTNode(data)
elif node.data > data:
node.left = __insert(node.left, data)
elif node.data < data:
node.right = __insert(node.right, data)
else:
pass
return return_node
self._root = __insert(self._root, data)
def delete(self: 'BST', data: object) -> None:
"""Remove, if there, node containing data.
>>> b = BST()
>>> b.insert(8)
>>> b.insert(4)
>>> b.insert(2)
>>> b.insert(6)
>>> b.insert(12)
>>> b.insert(14)
>>> b.insert(10)
>>> b.delete(12)
>>> b
BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
BTNode(10, None, BTNode(14, None, None))))
>>> b.delete(14)
>>> b
BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
BTNode(10, None, None)))
"""
def __find_max(node):
return __find_max(node.right) if node.right else node
def __delete(node, data):
return_node = node
if not node:
pass
elif node.data > data:
node.left = __delete(node.left, data)
elif node.data < data:
node.right = __delete(node.right, data)
else:
if not node.right:
return_node = node.left
elif not node.left:
return_node = node.right
else:
node.data = __find_max(node.left).data
#go throught the left side and dine max again and replace as None
node.left = __delete(node.left, node.data)
return return_node
self._root = __delete(self._root, data)
def height(self: 'BST') -> int:
"""Return height of this tree."""
return _height(self._root)
def insert2(self, data):
return_node = self._root
if not self._root:
return_node = BTNode(data)
elif self._root > data:
self._root.left = self.insert2(self.left, data)
elif self._root < data:
self._root.right = self.insert2(self.right, data)
else:
pass
def _insert(node: BTNode, data: object) -> BTNode:
"""Insert data in BST rooted at node, if necessary, and return root."""
return_node = node
if not node:
return_node = BTNode(data)
elif data < node.data:
node.left = _insert(node.left, data)
elif data > node.data:
node.right = _insert(node.right, data)
else: # nothing to do
pass
return return_node
def _find(node: BTNode, data: object):
"""Return the node containing data, or else None."""
if not node or node.data == data:
return node
else:
return (_find(node.left, data) if (data < node.data)
else _find(node.right, data))
def _delete(node: BTNode, data: object) -> BTNode:
"""Delete, if exists, node with data and return resulting tree."""
# Algorithm for _delete:
# 1. If this node is None, return that
# 2. If data is less than node.data, delete it from left child and
# return this node
# 3. If data is more than node.data, delete it from right child
# and return this node
# 4. If node with data has fewer than two children,
# and you know one is None, return the other one
# 5. If node with data has two non-None children,
# replace data with that of its largest child in the left subtree,
# and delete that child, and return this node
return_node = node
if not node:
pass
elif data < node.data:
node.left = _delete(node.left, data)
elif data > node.data:
node.right = _delete(node.right, data)
elif not node.left:
return_node = node.right
elif not node.right:
return_node = node.left
else:
node.data = _find_max(node.left).data
node.left = _delete(node.left, node.data)
return return_node
def _find_max(node: BTNode) -> BTNode:
"""Find and return maximal node, assume node is not None"""
return _find_max(node.right) if node.right else node
def _height(node):
"""Return height of tree rooted at node."""
# use max to get the deeper node
return 1 + max(_height(node.left), _height(node.right)) if node else -1
if __name__ == '__main__':
import doctest
doctest.testmod()
b = BST()
b.insert(8)
b.insert(4)
b.insert(2)
b.insert(1)
b.insert(6)
b.insert(5)
b.insert(7)
b.insert(10)
b.insert(9)
b.insert(12)
print(b)
b.delete(4)
print(b)
print('1')
b.delete(14)
print(b)
print(b.height())
a = BTNode(2)
print(_find_max(a).data)
which describes the limiting behavior of the function
when the argument trends towards a particular value of infinity
example :
f(x)= 3x^4 - 2x^3 + 1 ;
if we wanna simply function , using O notation, the highest growth rate is
3x^4, and we take x^4 from 3x^4. Thus, we say that f(x) is a 'big-O' of (x^4),
can be write as f(x)=O(x^4).
And from class we know O(1) ∈ O(lg n) ∈ O(n) ∈ O(n^2) ∈ O(n^3) ∈ O(2^n) ∈ O(n^n)
Also we learn the binary search tree(BST), there is some properties of BST(from Wikipedia):
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree each must also be a binary search tree.
- There must be no duplicate nodes.
in a list of size n is x=log_2 (n). the logarithm base two of n.
'''
'''
class BST:
def __init__(self, container=[]):
self.root = None
for item in container:
self.insert(item)
def __str__(self):
return BST._str("",self.root)
def _str(indent, root):
if root is None:
return ""
else:
return (BST._str(indent + "\t", root.right) +
indent + repr(root.item) + "\n" +
BST._str(indent + "\t", root.left))
def insert(self, item):
parent, current = None, self.root
while current is not None and current.item != item:
if item < current.item:
parent, current = current, current.left
else:
parent, current = currrnt, curren.right
if current is None:
parent = _BSTNode(item)
if parent is None:
self.root = current
elif item < parent.item:
parent.left = current
else:
parent.right = current
class _BSTNode:
"""A node in a BST."""
def __init__(self, item, left=None, right=None):
"""(_BSTNode, object, _BSTNode, _BSTNode) -> NoneType
Initialize this node to store item and have children left and right.
"""
self.item = item
self.left = left
self.right = right
'''
'''
x = _BSTNode(1,_BSTNode(2,_BSTNode(4),_BSTNode(7)),_BSTNode(3,_BSTNode(6),_BSTNode(5)))
print(x)
y = BST([1,2,3,4])
y.insert(2)
y.insert(1)
y.insert(9)
y.insert(5)
y.insert(4)
print(y._str(y.root))
'''
class BTNode:
"""Binary Tree node."""
"""initial the Binary tree node"""
def __init__(self: 'BTNode', data: object,
left: 'BTNode'=None, right: 'BTNode'=None) -> None:
"""Create BT node with data and children left and right."""
self.data, self.left, self.right = data, left, right
def __repr__(self: 'BTNode') -> str:
"""Represent this node as a string."""
return ('BTNode(' + str(self.data) + ', ' + repr(self.left) +
', ' + repr(self.right) + ')')
def is_leaf(self: 'BTNode') -> bool:
"""Is this node a leaf?"""
return self.data and not self.left and not self.right
"""
this line equal to
if self.data != None and self.left == None and self.right == None:
return True
else:
return False
>>>x=BTNode(1)
>>>print(x.is_leaf())
True
"""
"""binary search tree ADT"""
class BST:
"""Binary search tree."""
def __init__(self: 'BST', root: BTNode=None) -> None:
"""Create BST with BTNode root.
initial self to None, if dont hv BTNode
"""
self._root = root
def __repr__(self: 'BST') -> str:
"""Represent this binary search tree."""
return 'BST(' + repr(self._root) + ')'
def find(self: 'BST', data: object) -> BTNode:
"""Return node containing data, otherwise return None."""
return _find(self._root, data)
def insert(self: 'BST', data: object) -> None:
"""Insert data, if necessary, into this tree.
>>> b = BST()
>>> b.insert(8)
>>> b.insert(4)
>>> b.insert(2)
>>> b.insert(6)
>>> b.insert(12)
>>> b.insert(14)
>>> b.insert(10)
>>> b
BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
BTNode(12, BTNode(10, None, None), BTNode(14, None, None))))
"""
def __insert(node, data):
return_node = node
if not node:
return_node = BTNode(data)
elif node.data > data:
node.left = __insert(node.left, data)
elif node.data < data:
node.right = __insert(node.right, data)
else:
pass
return return_node
self._root = __insert(self._root, data)
def delete(self: 'BST', data: object) -> None:
"""Remove, if there, node containing data.
>>> b = BST()
>>> b.insert(8)
>>> b.insert(4)
>>> b.insert(2)
>>> b.insert(6)
>>> b.insert(12)
>>> b.insert(14)
>>> b.insert(10)
>>> b.delete(12)
>>> b
BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
BTNode(10, None, BTNode(14, None, None))))
>>> b.delete(14)
>>> b
BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
BTNode(10, None, None)))
"""
def __find_max(node):
return __find_max(node.right) if node.right else node
def __delete(node, data):
return_node = node
if not node:
pass
elif node.data > data:
node.left = __delete(node.left, data)
elif node.data < data:
node.right = __delete(node.right, data)
else:
if not node.right:
return_node = node.left
elif not node.left:
return_node = node.right
else:
node.data = __find_max(node.left).data
#go throught the left side and dine max again and replace as None
node.left = __delete(node.left, node.data)
return return_node
self._root = __delete(self._root, data)
def height(self: 'BST') -> int:
"""Return height of this tree."""
return _height(self._root)
def insert2(self, data):
return_node = self._root
if not self._root:
return_node = BTNode(data)
elif self._root > data:
self._root.left = self.insert2(self.left, data)
elif self._root < data:
self._root.right = self.insert2(self.right, data)
else:
pass
def _insert(node: BTNode, data: object) -> BTNode:
"""Insert data in BST rooted at node, if necessary, and return root."""
return_node = node
if not node:
return_node = BTNode(data)
elif data < node.data:
node.left = _insert(node.left, data)
elif data > node.data:
node.right = _insert(node.right, data)
else: # nothing to do
pass
return return_node
def _find(node: BTNode, data: object):
"""Return the node containing data, or else None."""
if not node or node.data == data:
return node
else:
return (_find(node.left, data) if (data < node.data)
else _find(node.right, data))
def _delete(node: BTNode, data: object) -> BTNode:
"""Delete, if exists, node with data and return resulting tree."""
# Algorithm for _delete:
# 1. If this node is None, return that
# 2. If data is less than node.data, delete it from left child and
# return this node
# 3. If data is more than node.data, delete it from right child
# and return this node
# 4. If node with data has fewer than two children,
# and you know one is None, return the other one
# 5. If node with data has two non-None children,
# replace data with that of its largest child in the left subtree,
# and delete that child, and return this node
return_node = node
if not node:
pass
elif data < node.data:
node.left = _delete(node.left, data)
elif data > node.data:
node.right = _delete(node.right, data)
elif not node.left:
return_node = node.right
elif not node.right:
return_node = node.left
else:
node.data = _find_max(node.left).data
node.left = _delete(node.left, node.data)
return return_node
def _find_max(node: BTNode) -> BTNode:
"""Find and return maximal node, assume node is not None"""
return _find_max(node.right) if node.right else node
def _height(node):
"""Return height of tree rooted at node."""
# use max to get the deeper node
return 1 + max(_height(node.left), _height(node.right)) if node else -1
if __name__ == '__main__':
import doctest
doctest.testmod()
b = BST()
b.insert(8)
b.insert(4)
b.insert(2)
b.insert(1)
b.insert(6)
b.insert(5)
b.insert(7)
b.insert(10)
b.insert(9)
b.insert(12)
print(b)
b.delete(4)
print(b)
print('1')
b.delete(14)
print(b)
print(b.height())
a = BTNode(2)
print(_find_max(a).data)
Sunday 27 October 2013
Short paragraphs of OOP and Recursion.
There are several reasons why programming languages such as python enable developers to define new classes. Classes that are custom-built for a particular application will make the application program more intuitive and easier to develop, debug, read, and maintain. The ability to create new classes also enables a new approach to structuring application programs. A class exposes to the computer scientist the methods that can be applied to objects of the class but encapsulate how the data contained in the objects is stored and how the classmethods are implemented. OOP is a software development paradigm that achieves modularity and code portability by organizing application programs around components that are classes and objects.
Recursion is a problem-solving technique that expresses the solution to a problem in terms of solutions to subproblems of the original problem. Recursion can be used to solve problems that might otherwise be quite challenging. The function developed by solving a problem recursively will naturally call themselves, and we refer to them as recursive functions. In some instances, recursive thinking offers insights that lead to solutions that are more efficient than the obvious or original solution. In other instances, it will lead to a solution that is far worse.
Recursion is a problem-solving technique that expresses the solution to a problem in terms of solutions to subproblems of the original problem. Recursion can be used to solve problems that might otherwise be quite challenging. The function developed by solving a problem recursively will naturally call themselves, and we refer to them as recursive functions. In some instances, recursive thinking offers insights that lead to solutions that are more efficient than the obvious or original solution. In other instances, it will lead to a solution that is far worse.
Week 7
In this week class, we learn about linked lists, which is example of attributes that refer to other objects. Linked lists are made up of nodes, where each ode contains a reference to the next node in the list. In addition, each node contains a unit of data called the cargo. A linked list is considered a recursive data structure because it has a recursive definition. And Recursive data structures lend themselves to recursive methods.
class Node:
def __init__(self, cargo = None, next = None):
self.cargo = cargo
self.next = next
def __str__(self):
return str(self.cargo)
def print_backward(self):
if self.next is not None:
tail = self.next
tail.print_backward()
print(self.cargo, end=" ")
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3
#node3.next = node1
#print(node3.next)
def print_list(node):
while node is not None:
print(node, end=" ")
node = node.next
print()
#print_list(node1)
def print_backward(list):
if list is None:
return
head = list
tail = list.next
print_backward(tail)
print(head, end=" ")
#print_backward(node1)
def remove_second(list):
if list is None:
return
else:
first = list
second = list.next
#make first.next point to third node by skip node 2
first.next = second.next
#however node 2 still there
#so second.next still be the node 3
#unless we give second.next point none
second.next = None
return second
'''
print_list(node1)
removed = remove_second(node1)
print_list(removed)
print_list(node1)
'''
class LinkedList:
def __init__(self):
self.length = 0
self.head = None
def print_backward(self):
print("[",end = " ")
if self.head is not None:
self.head.print_backward()
print("]", end = " ")
def print_list(self):
if self.head is not None:
print(self.head)
def add_first(self,cargo):
node = Node(cargo)
node.next = self.head
self.head = node
self.length += 1
def get_length(self):
return self.length
'''
x = LinkedList()
x.add_first(1)
x.add_first(2)
x.add_first(3)
x.add_first(4)
x.add_first(5)
x.add_first(6)
x.add_first(7)
x.print_backward()
print(x.get_length())
x.print_list()
'''
class LListNode:
def __init__(self, value = None, nxt = None):
self.value, self.nxt = value, nxt
def __repr__(self):
return 'LListNode(' + str(self.value) + ',' + str(self.nxt) + ')'
#x=LListNode(5556, 2)
#print(x)
class TreeNode:
#initial value of value here is an object that can be define as anything,
#and give the list initial type of list and value none, so when children
#is none them return empty list
#example can be seem @1
def __init__(self: 'TreeNode',
value: object =None, children: list =None):
self.value = value
if not children:
#=if children == None:
self.children = []
else:
self.children = children[:]
def __repr__(self: 'TreeNode'):
return ('TreeNode(' + str(self.value) + ',' +
repr(self.children) + ')' )
'''
#@1
test_list1 = [1,2,3,4,5]
#x=LListNode(5556, 2)
x='xxxx'
y=TreeNode(x,test_list1)
#y = TreeNode(x)
print(y)
'''
class Tree:
def __init__(self, root = None):
self.root = root
def arity(self: 'Tree') -> int:
pass
class b(object):
def __init__(self, item, left=None, right=None):
self.item = item
self.left = left
self.right = right
self.depth = 0
def __str__(self):
if self.right:
str_right = "\t" + str(self.right).replace("\n","\n\t") + "\n"
else:
str_right = ""
if isinstance(self.item, str):
str_item = repr(self.item)
else:
str_item = str (self.item)
if self.left:
str_left = "\n\t" + str(self.left).replace("\n","\n\t")
else:
str_left = ""
return str_right + str_item + str_left
def set_depth(self,depth):
if self.left == None and self.right == None:
self.depth = depth
if self.left:
self.depth = depth
self.left.set_depth(self.depth+1)
if self.right:
self.depth = depth
self.right.set_depth(self.depth+1)
def leaves_and_internals(self):
i = [[],[]]
def insidelai(node):
if node.left == None and node.right == None:
i[1].append(node.item)
else:
if node.left is None:
i[0].append(node.item)
insidelai(node.right)
elif node.right is None:
i[0].append(node.item)
insidelai(node.left)
else:
i[0].append(node.item)
insidelai(node.left)
insidelai(node.right)
return i
return insidelai(self)
'''
def leaves_and_intenals(self)：
leaves = []
internals = []
if (not self.left) and (not self.right):
leaves.append(self.item)
else:
internals.append(self.item)
left = self.left.leaves_and_internals()
right = self.right.leaves_and_internals()
leaves = left[0] + right[0]
internals = internals + left[1] + right[1]
return (leaves, internals)
'''
#x=b(1,b(2,None,b(4)),b(5,b(6),b(7)))
#print(x.leaves_and_internals())
def cd(node,depth):
temp = depth
if node.left == None and node.right == None:
return temp
else:
#if not node.left == None:
temp = temp+1
return cd(node.left,temp)
'''
x.set_depth(1)
print(x)
#print(cd(x.left,1),cd(x.left.left,1))
print(x.right.depth)
#y=BTNode(2,x,x)
#print(y)
#z=BTNode(2,y,y)
#print(z)
'''
class Node:
def __init__(self, cargo = None, next = None):
self.cargo = cargo
self.next = next
def __str__(self):
return str(self.cargo)
def print_backward(self):
if self.next is not None:
tail = self.next
tail.print_backward()
print(self.cargo, end=" ")
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3
#node3.next = node1
#print(node3.next)
def print_list(node):
while node is not None:
print(node, end=" ")
node = node.next
print()
#print_list(node1)
def print_backward(list):
if list is None:
return
head = list
tail = list.next
print_backward(tail)
print(head, end=" ")
#print_backward(node1)
def remove_second(list):
if list is None:
return
else:
first = list
second = list.next
#make first.next point to third node by skip node 2
first.next = second.next
#however node 2 still there
#so second.next still be the node 3
#unless we give second.next point none
second.next = None
return second
'''
print_list(node1)
removed = remove_second(node1)
print_list(removed)
print_list(node1)
'''
class LinkedList:
def __init__(self):
self.length = 0
self.head = None
def print_backward(self):
print("[",end = " ")
if self.head is not None:
self.head.print_backward()
print("]", end = " ")
def print_list(self):
if self.head is not None:
print(self.head)
def add_first(self,cargo):
node = Node(cargo)
node.next = self.head
self.head = node
self.length += 1
def get_length(self):
return self.length
'''
x = LinkedList()
x.add_first(1)
x.add_first(2)
x.add_first(3)
x.add_first(4)
x.add_first(5)
x.add_first(6)
x.add_first(7)
x.print_backward()
print(x.get_length())
x.print_list()
'''
class LListNode:
def __init__(self, value = None, nxt = None):
self.value, self.nxt = value, nxt
def __repr__(self):
return 'LListNode(' + str(self.value) + ',' + str(self.nxt) + ')'
#x=LListNode(5556, 2)
#print(x)
class TreeNode:
#initial value of value here is an object that can be define as anything,
#and give the list initial type of list and value none, so when children
#is none them return empty list
#example can be seem @1
def __init__(self: 'TreeNode',
value: object =None, children: list =None):
self.value = value
if not children:
#=if children == None:
self.children = []
else:
self.children = children[:]
def __repr__(self: 'TreeNode'):
return ('TreeNode(' + str(self.value) + ',' +
repr(self.children) + ')' )
'''
#@1
test_list1 = [1,2,3,4,5]
#x=LListNode(5556, 2)
x='xxxx'
y=TreeNode(x,test_list1)
#y = TreeNode(x)
print(y)
'''
class Tree:
def __init__(self, root = None):
self.root = root
def arity(self: 'Tree') -> int:
pass
class b(object):
def __init__(self, item, left=None, right=None):
self.item = item
self.left = left
self.right = right
self.depth = 0
def __str__(self):
if self.right:
str_right = "\t" + str(self.right).replace("\n","\n\t") + "\n"
else:
str_right = ""
if isinstance(self.item, str):
str_item = repr(self.item)
else:
str_item = str (self.item)
if self.left:
str_left = "\n\t" + str(self.left).replace("\n","\n\t")
else:
str_left = ""
return str_right + str_item + str_left
def set_depth(self,depth):
if self.left == None and self.right == None:
self.depth = depth
if self.left:
self.depth = depth
self.left.set_depth(self.depth+1)
if self.right:
self.depth = depth
self.right.set_depth(self.depth+1)
def leaves_and_internals(self):
i = [[],[]]
def insidelai(node):
if node.left == None and node.right == None:
i[1].append(node.item)
else:
if node.left is None:
i[0].append(node.item)
insidelai(node.right)
elif node.right is None:
i[0].append(node.item)
insidelai(node.left)
else:
i[0].append(node.item)
insidelai(node.left)
insidelai(node.right)
return i
return insidelai(self)
'''
def leaves_and_intenals(self)：
leaves = []
internals = []
if (not self.left) and (not self.right):
leaves.append(self.item)
else:
internals.append(self.item)
left = self.left.leaves_and_internals()
right = self.right.leaves_and_internals()
leaves = left[0] + right[0]
internals = internals + left[1] + right[1]
return (leaves, internals)
'''
#x=b(1,b(2,None,b(4)),b(5,b(6),b(7)))
#print(x.leaves_and_internals())
def cd(node,depth):
temp = depth
if node.left == None and node.right == None:
return temp
else:
#if not node.left == None:
temp = temp+1
return cd(node.left,temp)
'''
x.set_depth(1)
print(x)
#print(cd(x.left,1),cd(x.left.left,1))
print(x.right.depth)
#y=BTNode(2,x,x)
#print(y)
#z=BTNode(2,y,y)
#print(z)
'''
Week 5
In this week class, we learn about treelist with
preoder, postorder and inorder. We learn about how to create a binary tree. The
tree just like a combination of nodes, has leaf: node with no children,
internal node: node with one or more children, subtree: tree formed by any tree
node together with its descendants and the edges leading to them. And there is
a unique path from root to each node. And again, we learn how to do it by using
recursion.
def preorder(tl: 'TreeLIst') -> list:
if tl == None:
return []
else:
return [tl[0]] + preorder(tl[1]) + preorder(tl[2])
#print(preorder([5, [4, [2, None, [3, None, None]],[6, [7, None, None], None]], [3, [2, None, None], [1, None, None]]]))
#print(preorder([10, [6, [8, None, None], None], [12, [11, None, None], [15, None, None]]]))
'''
5
4 3
2 6 2 1
N 3 N N N N
N N
5
4 3
2 N 9 1
8 3
N 6
7 N
postorder [6 3 2 4 2 1 3 5]
inorder [2 3 6 4 5 2 3 1]
[10, 6, 8, 12, 11, 15]
10
6 11
8 12 15
[8, 6, 12, 10, 11, 15]
'''
'''
def inorder(tl: 'TreeList') -> list:
return ((inorder(tl[1]) if tl[1] else []) + [tl[0]] +
(inorder(tl[2]) if tl[2] else []))
'''
def inorder(tl: 'TreeList') -> list:
"""
Return a list of values of tl inorder
>>> inorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
[4, 5, 2, 3, 1]
"""
return ((inorder(tl[1]) if tl[1] else []) +
[tl[0]] +
(inorder(tl[2]) if tl[2] else []))
print(inorder([5, [4, [2, [8, None, None], [3, None, [6, [7, None, None], None]]], None], [3, [9, None, None],
[1, None, None]]]))
def postorder(tl:list):
return ((postorder(tl[1]) if tl[1] else []) + (postorder(tl[2]) if tl[2] else []) + [tl[0]])
'''
print(postorder([5, [4, [2, None, [3, None, [6, None, None]]], None], [3, [2, None, None],
[1, None, None]]]))
print(inorder([10, [6, [8, None, None], None], [12, [11, None, None], [15, None, None]]]))
print(preorder([10, [8, [6, None, None], [12, None, None]], [11, None, [15, None, None]]]))
print(inorder([10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]))
print(preorder([10, [6, None, None], [8, None, [12, [11, None, None], [15, None, None]]]]))
print(inorder([10, [6, None, None], [8, None, [12, [11, None, None], [15, None, None]]]]))
print(preorder([10,[6,[8,None,None],[12,None,None]],[11,None,[15,None,None]]]))
print(inorder([10,[6,[8,None,None],[12,None,None]],[11,None,[15,None,None]]]))
#10,6,8,12,11,15
'''
def preorder(tl: 'TreeLIst') -> list:
if tl == None:
return []
else:
return [tl[0]] + preorder(tl[1]) + preorder(tl[2])
#print(preorder([5, [4, [2, None, [3, None, None]],[6, [7, None, None], None]], [3, [2, None, None], [1, None, None]]]))
#print(preorder([10, [6, [8, None, None], None], [12, [11, None, None], [15, None, None]]]))
'''
5
4 3
2 6 2 1
N 3 N N N N
N N
5
4 3
2 N 9 1
8 3
N 6
7 N
postorder [6 3 2 4 2 1 3 5]
inorder [2 3 6 4 5 2 3 1]
[10, 6, 8, 12, 11, 15]
10
6 11
8 12 15
[8, 6, 12, 10, 11, 15]
'''
'''
def inorder(tl: 'TreeList') -> list:
return ((inorder(tl[1]) if tl[1] else []) + [tl[0]] +
(inorder(tl[2]) if tl[2] else []))
'''
def inorder(tl: 'TreeList') -> list:
"""
Return a list of values of tl inorder
>>> inorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
[4, 5, 2, 3, 1]
"""
return ((inorder(tl[1]) if tl[1] else []) +
[tl[0]] +
(inorder(tl[2]) if tl[2] else []))
print(inorder([5, [4, [2, [8, None, None], [3, None, [6, [7, None, None], None]]], None], [3, [9, None, None],
[1, None, None]]]))
def postorder(tl:list):
return ((postorder(tl[1]) if tl[1] else []) + (postorder(tl[2]) if tl[2] else []) + [tl[0]])
'''
print(postorder([5, [4, [2, None, [3, None, [6, None, None]]], None], [3, [2, None, None],
[1, None, None]]]))
print(inorder([10, [6, [8, None, None], None], [12, [11, None, None], [15, None, None]]]))
print(preorder([10, [8, [6, None, None], [12, None, None]], [11, None, [15, None, None]]]))
print(inorder([10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]))
print(preorder([10, [6, None, None], [8, None, [12, [11, None, None], [15, None, None]]]]))
print(inorder([10, [6, None, None], [8, None, [12, [11, None, None], [15, None, None]]]]))
print(preorder([10,[6,[8,None,None],[12,None,None]],[11,None,[15,None,None]]]))
print(inorder([10,[6,[8,None,None],[12,None,None]],[11,None,[15,None,None]]]))
#10,6,8,12,11,15
'''
Subscribe to:
Posts (Atom)