# coding:utf-8
"""
@ encoding: utf-8
@ author: lixiang
@ email: lixiang_cn@foxmail.com
@ python_version: 2
@ time: 2018/4/11 0:09
@ more_info:
二叉樹是有限個元素的集合，該集合或者為空、或者有一個稱為根節(jié)點（root）的元素及兩個互不相交的、分別被稱為左子樹和右子樹的二叉樹組成。
1 二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。
2 二叉樹的第i層至多有2^{i-1}個結(jié)點
3 深度為k的二叉樹至多有2^k-1個結(jié)點；
4 對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為N0，度為2的結(jié)點數(shù)為N2，則N0=N2+1
5 度是二叉樹分支樹，對于二叉樹而言有0，1，2三種取值
不管是前中后序遍歷，都是在當(dāng)前規(guī)則下，無路可走時，輸出根結(jié)點。
"""
class TreeNode(object):
  def __init__(self, x, left=None, right=None):
    self.val = x
    self.left = left
    self.right = right
def pre_traverse(root):
  """
  根左右
  :param root:
  :return:
  """
  if not root:
    return
  print root.val,
  pre_traverse(root.left)
  pre_traverse(root.right)
def mid_travese(root):
  """
  左根右
  :param root:
  :return:
  """
  if not root:
    return
  mid_travese(root.left)
  print root.val,
  mid_travese(root.right)
def after_travese(root):
  """
  左右根
  :param root:
  :return:
  """
  if not root:
    return
  after_travese(root.left)
  after_travese(root.right)
  print root.val,
def level_travese(root):
  if not root:
    return
  queue = []
  queue.append(root)
  while queue:
    cur = queue.pop(0)
    print cur.val,
    if cur.left:
      queue.append(cur.left)
    if cur.right:
      queue.append(cur.right)
def depth(root):
  if not root:
    return 0
  left = depth(root.left)
  right = depth(root.right)
  return max(left, right) + 1
if __name__ == '__main__':
  """
  tree是一個表示樹根節(jié)點的對象
  前序遍歷 1 2 4 5 8 9 11 3 6 7 10
  中序遍歷 4 2 8 5 11 9 1 6 3 10 7
  后序遍歷 4 8 11 9 5 2 6 10 7 3 1
  層序遍歷 1 2 3 4 5 6 7 8 9 10 11
  深度 5
  """
  tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5, TreeNode(8), TreeNode(9, left=TreeNode(11)))), TreeNode(3, TreeNode(6), TreeNode(7, left=TreeNode(10))))
  print("\n前序遍歷")
  pre_traverse(tree)
  print("\n中序遍歷")
  mid_travese(tree)
  print("\n后序遍歷")
  after_travese(tree)
  print("\n層序遍歷")
  level_travese(tree)
  print("\n深度")
  print(depth(tree))