参考：https://blog.csdn.net/IqqIqqIqqIqq/article/details/52674684

1. 树的创建

class BinaryTree(object):
    def __init__(self,item):
        self.key=item
        self.leftChild=None
        self.rightChild=None

2. 遍历

• 名字的意思是把根节点放在哪里。
• 深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。

2.1 前序遍历

中左右

2.1.1 递归方式实现

1. 先访问根节点
2. 再序遍历左子树
3. 最后序遍历右子树

def preorder(self, root):
      """递归实现先序遍历"""
      if root == None:
          return
      print root.elem
      self.preorder(root.lchild)
      self.preorder(root.rchild)

2.1.2 非递归实现

1. 首先申请一个新的栈，记为stack；
2. 将头结点head压入stack中；
3. 每次从stack中弹出栈顶节点，记为cur，然后打印cur值，如果cur右孩子不为空，则将右孩子压入栈中；如果cur的左孩子不为空，将其压入stack中；
4. 重复步骤3，直到stack为空.
   先压右孩子再压左孩子，打印的时候先打印栈顶，即为左孩子，然后如果cur有孩子的话也会压入栈，在右孩子上面。

def preOrder(self, root):
    if root == None:
        return
    myStack = []
    node = root
    while node or myStack:
        while node:
            # 从根节点开始，一直找它的左子树
            print node.val
            myStack.append(node)
            node = node.lchild
        # while结束表示当前节点node为空，即前一个节点没有左子树了
        node = myStack.pop()
        # 开始查看它的右子树
        node = node.rchild

2.2 中序遍历

左中右

2.2.1 递归实现

1. 先中序遍历左子树
2. 再访问根节点
3. 最后中序遍历右子树

def inorder(self, root):
      """递归实现中序遍历"""
      if root == None:
          return
      self.inorder(root.lchild)
      print root.elem
      self.inorder(root.rchild)

2.2.2 非递归实现

1. 申请一个新栈，记为stack，申请一个变量cur，初始时令cur为头节点；
2. 先把cur节点压入栈中，对以cur节点为头的整棵子树来说，依次把整棵树的左子树压入栈中，即不断令cur=cur.left，然后重复步骤2；
3. 不断重复步骤2，直到发现cur为空，此时从stack中弹出一个节点记为node，打印node的值，并让cur = node.right，然后继续重复步骤2；
4. 当stack为空并且cur为空时结束。
   第二步里压节点但是不打印，直到最左最下，所以先打印左节点；
   第三步里，没有左节点时，打印双亲节点，然后转向双亲的右孩子，所以是第二个打印中间的，最后打印右边的

def inOrder(self, root):
    if root == None:
        return
    myStack = []
    node = root
    while node or myStack:
        while node:
            # 从根节点开始，一直找它的左子树
            myStack.append(node)
            node = node.lchild
        # while结束表示当前节点node为空，即前一个节点没有左子树了
        node = myStack.pop()
        print node.val
        # 开始查看它的右子树
        node = node.rchild

2.3 后序遍历

左右中

2.3.1 递归方法

1. 先后序遍历左子树
2. 再后序遍历右子树
3. 最后访问根节点

def postorder(self, root):
      """递归实现后续遍历"""
      if root == None:
          return
      self.postorder(root.lchild)
      self.postorder(root.rchild)
      print root.elem

2.3.2 非递归方法

1. 申请两个栈stack1，stack2，然后将头结点压入stack1中；
2. 从stack1中弹出的节点记为cur，然后先把cur的左孩子压入stack1中，再把cur的右孩子压入stack1中；
3. 在整个过程中，每一个从stack1中弹出的节点都放在第二个栈stack2中；
4. 不断重复步骤2和步骤3，直到stack1为空，过程停止；
5. 从stack2中依次弹出节点并打印，打印的顺序就是后序遍历的顺序；

重点在弹出的顺序，每次先弹一个到stack2，但是要把这个节点的左右孩子压入stack1，然后再弹孩子的时候，就会把双亲节点压在下面，最后顺序打印就得到后序遍历。

def later_stack(self, root):
    if root == None:
        return
    myStack1 = []
    myStack2 = []
    node = root
    myStack1.append(node)
    while myStack1:
    # 这个while循环的功能是找出后序遍历的逆序，存在myStack2里面
        node = myStack1.pop()
        if node.lchild:
            myStack1.append(node.lchild)
        if node.rchild:
            myStack1.append(node.rchild)
        myStack2.append(node)
    while myStack2:
    # 将myStack2中的元素出栈，即为后序遍历次序
        print myStack2.pop().val

2.4 层序遍历

1. 首先申请一个新的队列，记为queue；
2. 将头结点head压入queue中；
3. 每次从queue中出队，记为node，然后打印node值，如果node左孩子不为空，则将左孩子入队；如果node的右孩子不为空，则将右孩子入队；
4. 重复步骤3，直到queue为空。

def breadth_travel(self, root):
        """利用队列实现树的层次遍历"""
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print node.elem,
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)