1、单链表
class Node(object): """节点""" def __init__(self, elem): self.elem = elem self.next = None class SingleLinkList(object): """单链表""" def __init__(self, node=None): self.__head = node def is_empty(self): """链表是否为空""" return self.__head == None def length(self): """链表长度""" # cur游标，用来移动遍历节点 cur = self.__head # count记录数量 count = 0 while cur != None: count += 1 cur = cur.next return count def travel(self): """遍历整个链表""" cur = self.__head while cur != None: print(cur.elem, end=" ") cur = cur.next print("") def add(self, item): """链表头部添加元素，头插法""" node = Node(item) node.next = self.__head self.__head = node def append(self, item): """链表尾部添加元素, 尾插法""" node = Node(item) if self.is_empty(): self.__head = node else: cur = self.__head while cur.next != None: cur = cur.next cur.next = node def insert(self, pos, item): """指定位置添加元素 :param pos 从0开始 """ if pos <= 0: self.add(item) elif pos > (self.length()-1): self.append(item) else: pre = self.__head count = 0 while count < (pos-1): count += 1 pre = pre.next # 当循环退出后，pre指向pos-1位置 node = Node(item) node.next = pre.next pre.next = node def remove(self, item): """删除节点""" cur = self.__head pre = None while cur != None: if cur.elem == item: # 先判断此结点是否是头节点 # 头节点 if cur == self.__head: self.__head = cur.next else: pre.next = cur.next break else: pre = cur cur = cur.next def search(self, item): """查找节点是否存在""" cur = self.__head while cur != None: if cur.elem == item: return True else: cur = cur.next return False if __name__ == "__main__": ll = SingleLinkList() print(ll.is_empty()) print(ll.length()) ll.append(1) print(ll.is_empty()) print(ll.length()) ll.append(2) ll.add(8) ll.append(3) ll.append(4) ll.append(5) ll.append(6) # 8 1 2 3 4 5 6 ll.insert(-1, 9) # 9 8 1 23456 ll.travel() ll.insert(3, 100) # 9 8 1 100 2 3456 ll.travel() ll.insert(10, 200) # 9 8 1 100 23456 200 ll.travel() ll.remove(100) ll.travel() ll.remove(9) ll.travel() ll.remove(200) ll.travel() 二叉树 class Node(object): """节点类""" def __init__(self, item): self.elem = item self.lchild = None self.rchild = None class Tree(object): """二叉树类""" def __init__(self,root=None): self.root = root def add(self, elem): """为树添加节点""" node = Node(elem) #如果树是空的，则对根节点赋值 if self.root == None: self.root = node else: queue = [] queue.append(self.root) #queue = [self.root] #对已有的节点进行层次遍历 while queue: #弹出队列的第一个元素 cur = queue.pop(0) if cur.lchild == None: #节点为空，新节点赋值 cur.lchild = node return elif cur.rchild == None: cur.rchild = node return else: #节点不为空，加入队列 #如果左右子树都不为空，加入队列继续判断 queue.append(cur.lchild) queue.append(cur.rchild) def breadth_travel(self): """广度遍历 层次遍历""" if self.root is None: return queue=[] queue.append(self.root)#queue = [self.root] while queue: cur_node = queue.pop(0) print(cur_node.elem, end=" ") if cur_node.lchild is not None: queue.append(cur_node.lchild) if cur_node.rchild is not None: queue.append(cur_node.rchild) def preorder(self, root): """先序遍历""" if root is None: return print(root.elem, end=" ") # print(" lchild ", end=" ") self.preorder(root.lchild) # print(" rchild ", end=" ") self.preorder(root.rchild) def inorder(self, node): """中序遍历""" if node is None: return self.inorder(node.lchild) print(node.elem, end=" ") self.inorder(node.rchild) def postorder(self, root): """后序遍历""" if root is None: return self.postorder(root.lchild) self.postorder(root.rchild) print(root.elem, end=" ") if __name__ == "__main__": tree = Tree() tree.add(0) tree.add(1) tree.add(2) tree.add(3) tree.add(4) tree.add(5) tree.add(6) tree.add(7) tree.add(8) tree.add(9) tree.breadth_travel() print(" ") tree.preorder(tree.root) print(" ") tree.inorder(tree.root) print(" ") tree.postorder(tree.root) print(" ")