个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 30 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Python编程实现双链表，栈，队列及二叉树的方法示例由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

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

1.双链表 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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. 栈 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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.队列 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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. 二叉树（定义与遍历） 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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))

输出结果:

?
1
2
3
4
层次遍历: [ 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 。

最后此篇关于Python编程实现双链表，栈，队列及二叉树的方法示例的文章就讲到这里了,如果你想了解更多关于Python编程实现双链表，栈，队列及二叉树的方法示例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

30 4 0
文章推荐： python 简单搭建阻塞式单进程,多进程,多线程服务的实例
文章推荐： vps主机和虚拟空间选择哪个好？
文章推荐： Python栈算法的实现与简单应用示例
文章推荐： MySQL中用通用查询日志找出查询次数最多的语句的教程
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com