本文实例讲述了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