Python编程实现双链表，栈，队列及二叉树的方法示例

本文实例讲述了Python编程实现双链表，栈，队列及二叉树的方法。分享给大家供大家参考，具体如下：

1.双链表

class Node(object):
 def __init__(self, value=None):
   self._prev = None
   self.data = value
   self._next = None
 def __str__(self):
   return "Node(％s)"％self.data
class DoubleLinkedList(object):
 def __init__(self):
   self._head = Node()
 def insert(self, value):
   element = Node(value)
   element._next = self._head
   self._head._prev = element
   self._head = element
 def search(self, value):
   if not self._head._next:
     raise ValueError("the linked list is empty")
   temp = self._head
   while temp.data != value:
     temp = temp._next
   return temp
 def delete(self, value):
   element = self.search(value)
   if not element:
     raise ValueError('delete error: the value not found')
   element._prev._next = element._next
   element._next._prev = element._prev
   return element.data
 def __str__(self):
   values = []
   temp = self._head
   while temp and temp.data:
     values.append(temp.data)
     temp = temp._next
   return "DoubleLinkedList(％s)"％values

2. 栈

class Stack(object):
 def __init__(self):
   self._top = 0
   self._stack = []
 def put(self, data):
   self._stack.insert(self._top, data)
   self._top += 1
 def pop(self):
   if self.isEmpty():
     raise ValueError('stack 为空')
   self._top -= 1
   data = self._stack[self._top]
   return data
 def isEmpty(self):
   if self._top == 0:
     return True
   else:
     return False
 def __str__(self):
   return "Stack(％s)"％self._stack

3.队列

class Queue(object):
 def __init__(self, max_size=float('inf')):
   self._max_size = max_size
   self._top = 0
   self._tail = 0
   self._queue = []
 def put(self, value):
   if self.isFull():
     raise ValueError("the queue is full")
   self._queue.insert(self._tail, value)
   self._tail += 1
 def pop(self):
   if self.isEmpty():
     raise ValueError("the queue is empty")
   data = self._queue.pop(self._top)
   self._top += 1
   return data
 def isEmpty(self):
   if self._top == self._tail:
     return True
   else:
     return False
 def isFull(self):
   if self._tail == self._max_size:
     return True
   else:
     return False
 def __str__(self):
   return "Queue(％s)"％self._queue

4. 二叉树（定义与遍历）

class Node:
 def __init__(self,item):
   self.item = item
   self.child1 = None
   self.child2 = None
class Tree:
 def __init__(self):
   self.root = None
 def add(self, item):
   node = Node(item)
   if self.root is None:
     self.root = node
   else:
     q = [self.root]
     while True:
       pop_node = q.pop(0)
       if pop_node.child1 is None:
         pop_node.child1 = node
         return
       elif pop_node.child2 is None:
         pop_node.child2 = node
         return
       else:
         q.append(pop_node.child1)
         q.append(pop_node.child2)
 def traverse(self): # 层次遍历
   if self.root is None:
     return None
   q = [self.root]
   res = [self.root.item]
   while q != []:
     pop_node = q.pop(0)
     if pop_node.child1 is not None:
       q.append(pop_node.child1)
       res.append(pop_node.child1.item)
     if pop_node.child2 is not None:
       q.append(pop_node.child2)
       res.append(pop_node.child2.item)
   return res
 def preorder(self,root): # 先序遍历
   if root is None:
     return []
   result = [root.item]
   left_item = self.preorder(root.child1)
   right_item = self.preorder(root.child2)
   return result + left_item + right_item
 def inorder(self,root): # 中序序遍历
   if root is None:
     return []
   result = [root.item]
   left_item = self.inorder(root.child1)
   right_item = self.inorder(root.child2)
   return left_item + result + right_item
 def postorder(self,root): # 后序遍历
   if root is None:
     return []
   result = [root.item]
   left_item = self.postorder(root.child1)
   right_item = self.postorder(root.child2)
   return left_item + right_item + result
t = Tree()
for i in range(10):
 t.add(i)
print('层序遍历:',t.traverse())
print('先序遍历:',t.preorder(t.root))
print('中序遍历:',t.inorder(t.root))
print('后序遍历:',t.postorder(t.root))

输出结果：

层次遍历: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
先次遍历: [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]
中次遍历: [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
后次遍历: [7, 8, 3, 9, 4, 1, 5, 6, 2, 0]

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

来源：http://www.cnblogs.com/PrettyTom/p/6677993.html