# 二叉樹
class Tree(object):
    def __init__(self, element=None):
        self.element = element
        self.left = None
        self.right = None

    def traversal(self):
        """
        樹的遍歷, 是一個遞歸操作
        """
        print(self.element)
        if self.left is not None:
            self.left.traversal()
        if self.right is not None:
            self.right.traversal()

    def reverse(self):
        self.left, self.right = self.right, self.left
        if self.left is not None:
            self.left.reverse()
        if self.right is not None:
            self.right.reverse()



# hash表
class HashTable(object):
    def __init__(self):
        self.table_size = 10007
        self.table = [0] * self.table_size

    # 這個魔法方法是用來實現(xiàn) in  not in 語法的
    def __contains__(self, item):
        return self.has_key(item)

    def has_key(self, key):
        """
        檢查一個 key 是否存在, 時間很短, 是 O(1)
        如果用 list 來存儲, 需要遍歷, 時間是 O(n)
        """
        index = self._index(key)
        # 取元素
        v = self.table[index]
        if isinstance(v, list):
            # 檢查是否包含我們要找的 key
            for kv in v:
                if kv[0] == key:
                    return True
        return False

    def _insert_at_index(self, index, key, value):
        # 檢查下標處是否是第一次插入數(shù)據(jù)
        v = self.table[index]
        data = [key, value]
        # 也可以用這個判斷 if v == 0:
        if isinstance(v, int):
            self.table[index] = [data]
        else:
            # 如果不是, 得到的會是 list, 直接 append
            self.table[index].append(data)

    def add(self, key, value):
        """
        add 函數(shù)往 hashtable 中加入一對元素
        我們先只支持字符串當 key
        """
        # 先計算出下標
        index = self._index(key)
        # 在下標處插入元素
        self._insert_at_index(index, key, value)

    def get(self, key, default_value=None):
        """
        這個和 dict 的 get 函數(shù)一樣
        """
        index = self._index(key)
        # 取元素
        v = self.table[index]
        if isinstance(v, list):
            for kv in v:
                if kv[0] == key:
                    return kv[1]
        return default_value

    def _index(self, key):
        # 先計算出下標
        return self._hash(key) % self.table_size

    def _hash(self, s):
        n = 1
        f = 1
        for i in s:
            n += ord(i) * f
            f *= 10
        return n




# 鏈表
class Node(object):
    def __init__(self, element=-1):
        self.element = element
        self.next = None


class LinkedList(object):
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def length(self):
        index = 0
        node = self.head
        while node is not None:
            index += 1
            node = node.next
        return index

    def find(self, element):
        node = self.head
        while node is not None:
            if node.element == element:
                break
            node = node.next
        return node

    def _node_at_index(self, index):
        i = 0
        node = self.head
        while node is not None:
            if i == index:
                return node
            node = node.next
            i += 1
        return None

    def element_at_index(self, index):
        node = self._node_at_index(index)
        return node.element


# 隊列
class Node():
    def __init__(self, element=None, next=None):
        self.element = element
        self.next = next

    def __repr__(self):
        return str(self.element)


class Queue():
    def __init__(self):
        self.head = Node()
        self.tail = self.head

    def empty(self):
        return self.head.next is None

    def enqueue(self, element):
        n = Node(element)
        self.tail.next = n
        self.tail = n

    def dequeue(self):
        node = self.head.next
        if not self.empty():
            self.head.next = node.next
        return node

# 棧
class Node():
    def __init__(self, element=None, next=None):
        self.element = element
        self.next = next

    def __repr__(self):
        return str(self.element)


class Stack():
    def __init__(self):
        self.head = Node()

    def is_empty(self):
        return self.head.next is None

    def push(self, element):
        self.head.next = Node(element, self.head.next)

    # 取出head.next指向的元素，如果棧不是空的，就讓head.next指向node.next，這樣node就不在棧中了
    def pop(self):
        node = self.head.next
        if not self.is_empty():
            self.head.next = node.next
        return node

    # head.next就是棧里面第一個元素
    def top(self):
        return self.head.next