树的遍历

1. 有序列表内容
2. 生成一棵树
3. 前序遍历，即深度优先遍历（DFS）
4. 中序遍历
5. 后序遍历
6. 层次遍历，即广度优先遍历（BFS）

一、树的生成

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def initTree(nodeList):
    '''
    先序遍历，若空结点以' '表示
    nodeList = ['A', ' ',...]
    '''
    if nodeList == []:
        return None
    else:
        val = nodeList.pop(0)
        if val == ' ':
            return None
        node = TreeNode(val)
        node.left = initTree(nodeList)
        node.right = initTree(nodeList)
    return node

nodeList = ['A', 'B', 'C', ' ', ' ', 'D', 'E', ' ', 'G', ' ', ' ', 'F', ' ', ' ', ' ']
root = initTree(nodeList)

二、先序遍历&&DFS

def preOrderTraverse(root):
    '''
    递归法先序遍历, 即深度优先遍历
    '''
    if not root:
        return 
    print(root.val, end=' ')
    preOrderTraverse(root.left)
    preOrderTraverse(root.right)       

preOrderTraverse(root)

A B C D E G F 

非递归方法的先序遍历，用到了栈。
先序遍历的顺序是:根-->左-->右
访问根节点后访问左子树是没有问题的，但访问左子树后访问右子树，就需要借助根节点。因此我们用栈这种数据结构存储根节点。

def preOrderTraverse2(root):
    '''
    非递归法先序遍历， 即深度优先遍历
    '''
    stack = []
    tmp  = root
    while tmp or stack:
        if tmp:
            print(tmp.val, end = ' ')
            stack.append(tmp)
            tmp = tmp.left
        else:
            tmp = stack.pop().right

preOrderTraverse2(root)

A B C D E G F 

题目

1. 二叉树中和为某一值的路径

三、中序遍历

def inOrderTraverse(root):
    '''
    递归法中序遍历
    '''
    if not root:
        return
    inOrderTraverse(root.left)
    print(root.val, end = ' ')
    inOrderTraverse(root.right)

inOrderTraverse(root)

C B E G D F A 

中序遍历与先序遍历一样，主要的问题就在于访问完左子树后，需要回到根节点，然后再访问右子树
不同点在于，入栈根节点时，不对它进行访问，出栈时才访问。

def inOrderTraverse2(root):
    '''
    非递归法中序遍历
    '''
    stack = []
    tmp = root
    while tmp or stack:
        if tmp:
            stack.append(tmp)
            tmp = tmp.left
        else:
            node = stack.pop()
            print(node.val, end=' ')
            tmp = node.right

inOrderTraverse2(root)

C B E G D F A 

四、后序遍历

def postOrderTraverse(root):
    '''
    递归后序遍历
    '''
    if not root:
        return None
    postOrderTraverse(root.left)
    postOrderTraverse(root.right)
    print(root.val, end=' ')

postOrderTraverse(root)

C G E F D B A 

后序遍历的顺序是 左-->右-->根
难点在于，访问某个结点时，需要判断当前结点时左子树，还是右子树。
若为左子树，则之后应先访问右子树，再访问根节点
若为右子树，则之后应直接访问根节点

def postOrderTraverse2(root):
    '''
    非递归后序遍历
    '''
    stack = []
    tmp = root
    lastVisit = None #上一个被访问的结点
    while tmp:
        stack.append(tmp)
        tmp = tmp.left
    # 结束循环后，tmp==None
    while stack:
        tmp = stack.pop() #当前结点没有左子树
        if tmp.right==None or tmp.right == lastVisit: #若一个结点没有右子树，或右子树已经被访问过，才能访问此节点
            print(tmp.val, end=' ')
            lastVisit = tmp
        else: #访问此节点的右节点
            stack.append(tmp) # 根节点再次入栈
            tmp = tmp.right
            while tmp:
                stack.append(tmp)
                tmp = tmp.left

postOrderTraverse2(root)

C G E F D B A 

五、BFS && 层次遍历

利用队列这一数据结构，对根节点进行顺序保存和顺序访问，就满足了层次遍历的需求

def BFS(root):
    '''
    层次遍历，即广度优先遍历
    '''
    queue = []
    queue.append(root)
    while queue:
        node = queue.pop(0)
        print(node.val, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

BFS(root)

A B C D E F G 

题目

1. 从上往下打印二叉树