二叉树的[深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列

深度优先遍历中，具体分为如下三种：

先序遍历：先访问根节点，再遍历左子树，再遍历右子树；
中序遍历：先遍历左子树，再访问根节点，再遍历右子树；
后序遍历：先遍历左子树，再遍历右子树，再访问根节点；

# 定义二叉树节点
class TreeNode(object):
    def __init__(self,val,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right

#定义二叉树类
class BinaryTree(object):
    def __init__(self,root=None):
        self.root=root
 
    def preOrder(self,retList=[],node='root'):
        if node!=None:
            retList.append(node)
            self.preOrder(retList,node.left)　　　　# 递归调用，将左子节点放到列表里　　
            self.preOrder(retList,node.right)　　  # 递归调用，将右节点放到列表里　　
        return retList
    def inOrder(self,retList=[],node='root'):
        if node!=None:
            self.inOrder(retList,node.left)
            retList.append(node)
            self.inOrder(retList,node.right)
        return retList
    def postOrder(self,retList=[],node='root'):
        if node!=None:
            self.postOrder(retList,node.left)
            self.postOrder(retList,node.right)
            retList.append(node)
        return retList

if __name__=='__main__':
    rootNode=TreeNode(50)
    rootNode.left = TreeNode(20,left=TreeNode(15),right=TreeNode(30))
    rootNode.right = TreeNode(60,right=TreeNode(70))
    binaryTree=BinaryTree(rootNode)
    ret = binaryTree.preOrder([],binaryTree.root)
    for i in ret:
        print(i.val,end='.')
    print('\n'+'-'*20)
    ret = binaryTree.inOrder([],binaryTree.root)
    for i in ret:
        print(i.val,end='.')
    print('\n'+'-'*20)
    ret = binaryTree.postOrder([],binaryTree.root)
    for i in ret:
        print(i.val,end='.')

#先序
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        stack = [root]
        while stack:
            node = stack.pop()
            ret.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return ret

#后序
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        ret = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                ret.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
        return ret[::-1]

广度优先遍历：

从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

from queue import Queue
 
class TreeNode(object):
    def __init__(self,var,left=None,right=None):
        self.var = var
        self.left = left
        self.right = right
 
class BinaryTree(object):
    def __init__(self,root = None):
        self.root = root

    def breathSearth(self):
        if self.root == None:
            return None
        retList = []
        q = [self.root]
        while q :
            node = q.pop(0)
            retList.append(node.var)
            if node.left != None:
                q.append(node.left)
            if node.right != None:
                q.append(node.right)
        return retList

BFS & DFS

BFS

graph={
    "A":["B","C"],
    "B":["A","C","D"],
    "C":["A","B","D","E"],
    "D":["B","C","E","F"],
    "E":["C","D"],
    "F":["D"]
}

def BFS(graph,s):  #s是起始点
    queue=[]  #数组可以动态的添加或者删除 append、pop
    queue.append(s)
    seen=[]  #来保存放过的节点
    seen.append(s)
    parent={s:None}#字典
    
    while(len(queue)>0):
        vertex=queue.pop(0)
        nodes=graph[vertex]
        for node in nodes:
            if node not in seen:
                queue.append(node)
                seen.append(node)
                parent[node]=vertex
        print(vertex) #把当前拿出去的节点打印出来
    return parent


parent=BFS(graph,"A")
print(parent)
v="E"
while v!=None:      #输出最短路径
    print(v)
    v=parent[v]

DFS

def DFS(graph,s):  #s是起始点
    stack=[]  #数组可以动态的添加或者删除 append、pop
    stack.append(s)
    seen=[]  #来保存放过的节点
    seen.append(s)
    while(len(stack)>0):
        vertex=stack.pop()  # 弹出最后一个元素
        nodes=graph[vertex]
        for node in nodes:
            if node not in seen:
                stack.append(node)
                seen.append(node)
        print(vertex) #把当前拿出去的节点打印出来

DFS(graph,"A")

Dijkstra

graph = {
    "A" : {"B":5, "C":1},
    "B" : {"A":5, "C":2, "D":1},
    "C" : {"A":1, "B":2, "D":4, "E":8},
    "D" : {"B":1, "C":4, "E":3, "F":6},
    "E" : {"C":8, "D":3},
    "F" : {"D":6}
}
import heapq

def init_distance(graph, startNode):
    distance = {startNode : 0}
    for vertex in graph:
        if vertex != startNode:
            distance[vertex] = float('inf')
    return distance

def Dijkstra(graph, startNode):
    pqueue = []
    heapq.heappush(pqueue, (0, startNode))
    seen = set()
    parents = {startNode : None}
    distance = init_distance(graph, startNode)

    while (len(pqueue) > 0):
        pair = heapq.heappop(pqueue)
        dist = pair[0]
        vertex = pair[1]
        seen.add(vertex)

        nodes = graph[vertex].keys()
        for w in nodes:
            if w not in seen:
                if dist + graph[vertex][w] < distance[w]:
                    heapq.heappush(pqueue, (dist + graph[vertex][w], w))
                    parents[w] = vertex
                    distance[w] = dist + graph[vertex][w]

    return parents, distance

parent , distance = Dijkstra(graph, "A")
print(parent)
print(distance)