week8

from queueCircular import CircularQueue
class TNode:
    def __init__(self,data,left,right):
        self.data=data
        self.left=left
        self.right=right


def preorder(n):
    if n is not None:
        print(n.data,end=' ')
        preorder(n.left)
        preorder(n.right)

def inorder(n):
    if n is not None:
        inorder(n.left)
        print(n.data,end=' ')
        inorder(n.right)

def postorder(n):
    if n is not None:
        postorder(n.left)
        postorder(n.right)
        print(n.data,end=' ')

def levelorder(root):
    queue=CircularQueue()
    queue.enqueue(root)
    while not queue.isEmpty():
        n=queue.dequeue()
        if n is not None:
            print(n.data,end=' ')
            queue.enqueue(n.left)
            queue.enqueue(n.right)

class BinaryTree:
    def __init__(self,root=None):
        self.root=root

    def isEmpty(self): return self.root==None
    def clear(self): self.root=None
    def printInOrder(self,msg='   In-Order : '): print(msg,end=''); inorder(self.root); print()
    def printPreOrder(self,msg='  Pre-Order : '): print(msg,end=''); preorder(self.root); print()
    def printPostOrder(self,msg=' Post-Order : '):print(msg,end=''); postorder(self.root); print()
    def printLevelOrder(self,msg='Level-Order : '): print(msg,end=''); levelorder(self.root); print()


g=TNode('G',None,None)
h=TNode('H',None,None)
f=TNode('F',None,None)
d=TNode('D',None,None)
e=TNode('E',g,h)
c=TNode('C',e,f)
b=TNode('B',d,None)
a=TNode('A',b,c)



tree=BinaryTree(a)
tree.printInOrder()
tree.printPreOrder()
tree.printPostOrder()
tree.printLevelOrder()​

MAX_QSIZE = 10
class CircularQueue :
    def __init__( self ) :
        self.front = 0
        self.rear = 0
        self.items = [None] * MAX_QSIZE

    def isEmpty( self ) : return self.front == self.rear
    def isFull( self ) : return self.front == (self.rear+1)%MAX_QSIZE
    def clear( self ) : self.front = self.rear

    def enqueue( self, item ):
        if not self.isFull():
            self.rear = (self.rear+1)% MAX_QSIZE
            self.items[self.rear] = item

    def dequeue( self ):
        if not self.isEmpty():
            self.front = (self.front+1)% MAX_QSIZE
            return self.items[self.front]

    def peek( self ):
        if not self.isEmpty():
            return self.items[(self.front + 1) % MAX_QSIZE]

    def size( self ) :
       return (self.rear - self.front + MAX_QSIZE) % MAX_QSIZE

class LinearProbMap():

    def __init__(self,M):
        self.table=[None]*M
        self.M=M


    def hashFn(self,key):
        sum=0
        for c in key : sum = sum+ ord(c)
        return sum%self.M

    def insert(self, key, value):
        idx=self.hashFn(key)
        while(True):
            if self.table[idx]==None or self.table[idx]==-1:
                self.table[idx]=[key,value]
                break
            idx=(idx+1)%self.M

    def search(self,key):
        idx=self.hashFn(key)
        while(True):
            if self.table[idx]==None or self.table[idx]==-1:
                return "None"
            elif self.table[idx][0] == key:
                return "%s:%s" % (self.table[idx][0], self.table[idx][1])
            else:
                idx = (idx + 1) % self.M


    def delete(self,key):
        for i in range(len(self.table)):
            if self.table[i]!= None and self.table[i]!=-1:
                if self.table[i][0]==key:
                    self.table[i]=-1


    def display(self,msg):
        print(msg)
        for i in range(len(self.table)):
            if self.table[i]==None:
                print("[%2d] ->  None" %(i))
            elif self.table[i]==-1:
                print("[%2d] ->  -1" %(i))
            else:
                print("[%2d] ->  %s:%s" %(i,self.table[i][0],self.table[i][1]))

map=LinearProbMap(13)
map.insert('data','자료')
map.insert('structure','구조')
map.insert('sequential search','선형 탐색')
map.insert('game','게임')
map.insert('binary search','이진 탐색')
map.display('나의 단어장:')

print(' 탐색:game --> ' ,map.search('game'))
print(' 탐색:over --> ' ,map.search('over'))
print(' 탐색:data --> ' ,map.search('data'))

map.delete('game')
map.display('나의 단어장:')
print(' 탐색:game --> ' ,map.search('game'))