博客

广度优先

# bfs
class node(object):
    def __init__(self,key):
        self.key = key
        self.left = None
        self.right = None

root = node(5)
root.left = node(2)
root.right = node(4)
root.left.left = node(7)
root.right.left = node(3)
root.left.right = node(3)
root.right.right = node(6)

from collections import deque
def bfs(node):
    if node is None:
        return
    myset = set()  #seen
    myset.add(node.key) # root is seen
    myqueque = deque()
    myqueque.append(node)
    
    while len(myqueque) > 0:
        cur = myqueque.popleft()
        print(cur.key)
        
        if cur.left:
            if not cur.left.key in myset:
                myset.add(cur.left.key)
                myqueque.append(cur.left)
        if cur.right:
            if not cur.right.key in myset:
                myset.add(cur.right.key)
                myqueque.append(cur.right)

bfs(root)

5

2

4

7

3

6

深度优先

class node(object):
    def __init__(self,key):
        self.key = key
        self.next = []

# dfs
def dfs(node):
    if node is None:
        return 
    
    nodeset = set()
    stack = []
    print(node.key)
    nodeset.add(node)
    stack.append(node)
    while len(stack) > 0:
        cur = stack.pop()
        
        for next_ele in cur.nexts:
            if next_ele not in nodeset:
                stack.append(cur)
                stack.append(next_ele)
                set.add(next_ele)
                print(next_ele)
                break