重点掌握

发表于 | 分类于
字数统计: 1.4k | 阅读时长 ≈ 6

二叉树

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
class Node():
    #节点类
    def __init__(self,data = -1):
        self.data = data
        self.left = None
        self.right = None
class Tree():
    #树类
    def __init__(self):
        self.root = Node()
 
    def add(self,data):
        # 为树加入节点
        node  = Node(data)
        if self.root.data == -1:        #如果树为空，就对根节点赋值
            self.root = node
        else:
            myQueue = []
            treeNode = self.root
            myQueue.append(treeNode)
            while myQueue:              #对已有的节点进行层次遍历
                treeNode = myQueue.pop(0)
                if not treeNode.left:
                    treeNode.left = node
                    return
                elif not treeNode.right:
                    treeNode.right = node
                    return
                else:
                    myQueue.append(treeNode.left)
                    myQueue.append(treeNode.right)
 
    def pre_order_recursion(self,root):     #递归实现前序遍历
        if not root:
            return
        print root.data,
        self.pre_order_recursion(root.left)
        self.pre_order_recursion(root.right)
 
    def pre_order_stack(self,root):         #堆栈实现前序遍历（非递归）
        if not root:
            return
        myStack = []
        node = root
        while myStack or node:
            while node:       #从根节点开始，一直寻找他的左子树
                print node.data,     # 先序，进栈前就要读取了
                myStack.append(node) # 先存进栈，以后还需要它的右节点
                node = node.left
            node = myStack.pop()    #while结束表示当前节点node为空，即前一个节点没有左子树了
            node = node.right       #开始查看它的右子树
 
    def in_order_recursion(self,root):      #递归实现中序遍历
        if not root:
            return
        self.in_order_recursion(root.left)
        print root.data,
        self.in_order_recursion(root.right)
 
    def in_order_stack(self,root):        #堆栈实现中序遍历（非递归）
        if not root:
            return
        myStack = []
        node = root
        while myStack or node:     #从根节点开始，一直寻找它的左子树
            while node:
                myStack.append(node) 
                node = node.left
            node = myStack.pop() # 中序，弹出来后才读取
            print node.data,
            node = node.right
 
 
    def post_order_recursion(self,root):     #递归实现后序遍历
        if not root:
            return
        self.post_order_recursion(root.left)
        self.post_order_recursion(root.right)
        print root.data,
        
    def post_order_stack(self, root):  # 堆栈实现后序遍历（非递归）
        # 先遍历根节点，再遍历右子树，最后是左子树，这样就可以转化为和先序遍历一个类型了，最后只把遍历结果逆序输出就OK了。
        if not root:
            return
        myStack1 = []
        myStack2 = []
        node = root
        while myStack1 or node:
            while node:
                myStack2.append(node)
                myStack1.append(node)
                node = node.right
            node = myStack1.pop()
            node = node.left
        while myStack2:
            print myStack2.pop().data,
 
    def level_order_queue(self,root):       #队列实现层次遍历（非递归）
        if not root :
            return
        myQueue = []
        node = root
        myQueue.append(node)
        while myQueue:
            node = myQueue.pop(0)
            print node.data,
            if node.left:
                myQueue.append(node.left)
            if node.right:
                myQueue.append(node.right)
                
if __name__ == '__main__':
    #主函数
    datas = [2,3,4,5,6,7,8,9]
    tree = Tree()          #新建一个树对象
    for data in datas:
        tree.add(data)      #逐个加入树的节点
 
    print '递归实现前序遍历：'
    tree.pre_order_recursion(tree.root)
 
    print '\n堆栈实现前序遍历'
    tree.pre_order_stack(tree.root)
 
    print "\n\n递归实现中序遍历："
    tree.in_order_recursion(tree.root)
 
    print "\n堆栈实现中序遍历："
    tree.in_order_stack(tree.root)
 
    print '\n\n递归实现后序遍历：'
    tree.post_order_recursion(tree.root)
 
    print '\n堆栈实现后序遍历：'
    tree.post_order_stack(tree.root)
 
    print '\n\n队列实现层次遍历：'
    tree.level_order_queue(tree.root)！

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#  二分查找
def BinarySearch(array,t):
    low = 0
    height = len(array)-1
    while low < height:
        mid = (low+height)/2
        if array[mid] < t:
            low = mid + 1

        elif array[mid] > t:
            height = mid - 1

        else:
            return array[mid]
    return -1


if __name__ == "__main__":
    print BinarySearch([1,2,3,34,56,57,78,87],57)

广度优先与深度优先

下面的代码强调一下: dfs和bfs区别（重点）

  1. pop()和pop(0)
  2. order加入w的时机
  3. 判断w的条件
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
68
69
70
71
72
'''
深度优先遍历： 是一种用于遍历树或者图的算法。沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所在边都被搜索过了。搜索将回溯到节点v的那条边的起始节点。直到已发现从源节点可达的所有节点为止。如果还存在未发现的节点，则选择其中一个作为源节点并重复上述过程，整个进程反复进行直到所有节点都被访问为止.

广度优先遍历：从根节点开始，沿着树的宽度遍历树的节点，如果所有节点都被访问，则算法终止
'''
class Graph(object):
    def __init__(self, nodes, sides):
        # nodes表示用户输入的点，int型，sides表示用户输入的边，是一个二元组(u, v)
        # self.sequence是字典，key是点，value是与key相连的边
        self.sequence = {}
        # self.side是临时变量，主要用于保存与 指定点v 相连接的点
        self.side = []
        for node in nodes:
            for side in sides:
                u, v = side
                if node == u:
                    self.side.append(v)
                elif node == v:
                    self.side.append(u)
            # 第二层主要是遍历属于这个点的所有边，然后将点和边组成字典
            self.sequence[node] = self.side
            self.side = []
        # print self.sequence
        # {1: [2, 3], 2: [1, 4, 5], 3: [1, 6, 7], 4: [2, 8], 5: [2, 8], 6: [3, 7], 7: [3, 6], 8: [4, 5]}
 
    def dfs(self, node0):
        # order里面存放的是具体的访问路径，已经遍历的了
        queue, order = [], []
        queue.append(node0)
        while queue:
            v = queue.pop()  # 取出最后一个，为上一个刚加入节点的连接节点
            order.append(v) # 深度优先先加入，注意这个order的加入顺序
            for w in self.sequence[v]: # 两边
                # 不在order表示没被遍历，
                if w not in order and w not in queue:
                    queue.append(w)
        return order
    
    # bfs同理
    def bfs(self, node0):
        queue, order = [], []
        queue.append(node0)
        order.append(node0)
        while queue:
            v = queue.pop(0)  # 层次遍历按迅速取出
            for w in self.sequence[v]:
                # if w not in order and w not in queue:
                if w not in order
                    order.append(w) # 没被遍历就直接将两边加入order
                    queue.append(w)
        return order
 
 
def main():
        nodes = [i+1 for i in xrange(8)]
        sides = [(1, 2),
                 (1, 3),
                 (2, 4),
                 (2, 5),
                 (4, 8),
                 (5, 8),
                 (3, 6),
                 (3, 7),
                 (6, 7)]
 
        G = Graph(nodes, sides)
        print G.dfs(1)
        print G.bfs(1)
 
 
if __name__ == '__main__':
    main()
-------------Thanks for Reading!-------------