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)
'''