深度优先算法和广度优先算法(python)_广度优先法 记录open表和close表 python

深度优先算法：深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索
实现方法：

广度优先算法：广度优先算法（Breadth-First Search），同广度优先搜索，又称作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索演算法。简单的说，BFS（也是一种盲目搜寻法）是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。广度优先搜索的实现一般采用open-closed表。目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
实现方法：

算法：

深度优先：根左右遍历（递归实现）

def  depth_tree(tree_node):
    if  tree_node   is  not None:
        print(tree_node._data)
        if  tree_node._left is  not None:
            return depth_tree(tree_node._left)
        if  tree_node._right  is  not None:
            return depth_tree(tree_node._right)
1
2
3
4
5
6
7

广度优先：层次遍历，一层一层的遍历（队列实现）

def   level_queue(root):
    if  root  is  None:
        pass
    my_queue=[]
    node=root
    my_queue.append(node)   ##根结点入队
    while my_queue:
        node=my_queue.pop(0)  ##出队列
        print(node.elem)      ##访问结点
        if  node.lchild  is  not  None:
            my_queue.append(node.lchild)    ##入队
        if  node.rchild  is  not  None:
            my_queue.append(node.rchild)    ##入队
1
2
3
4
5
6
7
8
9
10
11
12
13

代码实现：

构建如上图树

一.列表法：

用列表构建如上图树：

 my_Tree = [
    'D',  ##根结点
    ['B',
     ['F', [], []],
     ['G', ['E', [], []], []]
     ],  ##左子叶
    ['C',[],
     ['A', ['H', [], []], []]
     ]  ##右子叶
]
1
2
3
4
5
6
7
8
9
10

深度优先

print(my_Tree[1])
print(my_Tree[2])

def depth_tree(tree_node):
    if tree_node:
        print(tree_node[0])
        ##访问左子叶
        if tree_node[1]:

            depth_tree(tree_node[1])  ##递归遍历
        # ##访问右子叶
        if tree_node[2]:

            depth_tree(tree_node[2])  ##递归遍历

depth_tree(my_Tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#D B F G E C A H

广度优先：

def   level_queue(root):
    if  not  root:
        pass
    my_queue=[]
    node=root
    my_queue.append(node)   ##根结点入队
    while my_queue:
        node=my_queue.pop(0)  ##出队列
        print(node[0])      ##访问结点
        if  node[1]:
            my_queue.append(node[1])    ##入队
        if  node[2]:
            my_queue.append(node[2])    ##入队
level_queue(my_Tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#D B F G E C A H

二.构造类结点法:

class  Tree:
    root=''
    right=None
    left=None
    ##初始化类
    def __init__(self,node):
        self.root=node
    def set_root(self,node):
        self.root=node
    def get_root(self,node):
        return self.root
##初始化树
a=Tree('A')
b=Tree('B')
c=Tree('C')
d=Tree('D')
e=Tree('E')
f=Tree('F')
g=Tree('G')
h=Tree('H')

##根据点的联系，生成关系树
a.left=h
b.left=f
b.right=g
c.right=a
d.left=b
d.right=c
g.left=e
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

深度优先:

def depth_tree(tree_node):
    if tree_node is not None:
        print(tree_node.root)
        if tree_node.left is not None:
             depth_tree(tree_node.left)      ##递归遍历
        if tree_node.right is not None:
             depth_tree(tree_node.right)
##传入根结点
depth_tree(d)
1
2
3
4
5
6
7
8
9

#D B F G E C A H

广度优先：

def   level_queue(root):
    if  root  is  None:
        pass
    my_queue=[]
    node=root
    my_queue.append(node)   ##根结点入队
    while my_queue:
        node=my_queue.pop(0)  ##出队列
        print(node.root)      ##访问结点
        if  node.left  is  not  None:
            my_queue.append(node.left)    ##入队
        if  node.right  is  not  None:
            my_queue.append(node.right)    ##入队
level_queue(d)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#D B F G E C A H