Python数据结构之栈、队列及二叉树定义与用法浅析

Python  /  管理员 发布于 7年前   144

本文实例讲述了Python数据结构之栈、队列及二叉树定义与用法。分享给大家供大家参考，具体如下：

目前只实现了三种，栈、队列和二叉树，哪天得空继续补吧~

1. 栈

#栈class Stack:  def __init__(self,size = 16):    self.stack = []    self.size = size    self.top = -1  def setSize(self, size):    self.size = size  def isEmpty(self):    if self.top == -1:      return True    else:      return False  def isFull(self):    if self.top +1 == self.size:      return True    else:      return False  def top(self):    if self.isEmpty():      raise Exception("StackIsEmpty")    else:      return self.stack[self.top]  def push(self,obj):    if self.isFull():      raise Exception("StackOverFlow")    else:      self.stack.append(obj)      self.top +=1  def pop(self):    if self.isEmpty():      raise Exception("StackIsEmpty")    else:      self.top -= 1      return self.stack.pop()  def show(self):    print(self.stack)s = Stack(5)s.push(1)s.push(2)s.push(3)s.push(4)s.push(5)s.show()s.pop()s.show()s.push(6)s.show()

运行结果：

2. 队列

#队列class Queue:  def __init__(self,size = 16):    self.queue = []    self.size = size    self.front = 0    self.rear = 0  def isEmpty(self):    return self.rear == 0  def isFull(self):    if (self.front - self.rear +1) == self.size:      return True    else:      return False  def first(self):    if self.isEmpty():      raise Exception("QueueIsEmpty")    else:      return self.queue[self.front]  def last(self):    if self.isEmpty():      raise Exception("QueueIsEmpty")    else:      return self.queue[self.rear]  def add(self,obj):    if self.isFull():      raise Exception("QueueOverFlow")    else:      self.queue.append(obj)      self.rear += 1  def delete(self):    if self.isEmpty():      raise Exception("QueueIsEmpty")    else:      self.rear -=1      return self.queue.pop(0)  def show(self):    print(self.queue)q = Queue(3)q.add(1)q.add(2)q.show()q.delete()q.show()

运行结果：

3. 二叉树

#队列class Queue:  def __init__(self,size = 16):    self.queue = []    self.size = size    self.front = 0    self.rear = 0  def isEmpty(self):    return self.rear == 0  def isFull(self):    if (self.front - self.rear +1) == self.size:      return True    else:      return False  def first(self):    if self.isEmpty():      raise Exception("QueueIsEmpty")    else:      return self.queue[self.front]  def last(self):    if self.isEmpty():      raise Exception("QueueIsEmpty")    else:      return self.queue[self.rear]  def add(self,obj):    if self.isFull():      raise Exception("QueueOverFlow")    else:      self.queue.append(obj)      self.rear += 1  def delete(self):    if self.isEmpty():      raise Exception("QueueIsEmpty")    else:      self.rear -=1      return self.queue.pop(0)  def show(self):    print(self.queue)#二叉树class BinaryTreeNode:  def __init__(self,data,left,right):    self.left = left    self.data = data    self.right = rightclass BinaryTree:  def __init__(self):    self.root = None  def makeTree(self,data,left,right):    self.root = BinaryTreeNode(data,left,right)    #left.root = right.root = None  def isEmpty(self):    if self.root is None:      return True    else:      return False  def preOrder(self,r):    if r.root is not None:      print(r.root.data)      if r.root.left is not None:        self.preOrder(r.root.left)      if r.root.right is not None:        self.preOrder(r.root.right)  def inOrder(self,r):    if r.root is not None:      if r.root.left is not None:        self.inOrder(r.root.left)      print(r.root.data)      if r.root.right is not None:        self.inOrder(r.root.right)  def postOrder(self,r):    if r.root is not None:      if r.root.left is not None:        self.preOrder(r.root.left)      if r.root.right is not None:        self.preOrder(r.root.right)      print(r.root.data)  def levelOrder(self,a):    q = Queue()    r = a    while r is not None:      print(r.root.data)      if r.root.left is not None:        q.add(r.root.left)      if r.root.right is not None:        q.add(r.root.right)      if q.isEmpty():        print("empty")        r = None      else:        r = q.delete()r = BinaryTree()ra = BinaryTree()ra.makeTree(2,None,None)rb = BinaryTree()rb.makeTree(3,None,None)r.makeTree(1,ra,rb)print("前序遍历")r.preOrder(r)print("中序遍历")r.inOrder(r)print("后序遍历")r.postOrder(r)print("层级遍历")r.levelOrder(r)

运行结果:

后续实现了会慢慢补上~~旧的也会不断改进~~

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。