# coding:utf-8"""@ encoding: utf-8@ author: lixiang@ email: lixiang_cn@foxmail.com@ python_version: 2@ time: 2018/4/11 0:09@ more_info:二叉樹是有限個元素的集合，該集合或者為空、或者有一個稱為根節點（root）的元素及兩個互不相交的、分別被稱為左子樹和右子樹的二叉樹組成。1 二叉樹的每個結點至多只有二棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。2 二叉樹的第i層至多有2^{i-1}個結點3 深度為k的二叉樹至多有2^k-1個結點；4 對任何一棵二叉樹T，如果其終端結點數為N0，度為2的結點數為N2，則N0=N2+15 度是二叉樹分支樹，對于二叉樹而言有0，1，2三種取值不管是前中后序遍歷，都是在當前規則下，無路可走時，輸出根結點。"""class TreeNode(object):  def __init__(self, x, left=None, right=None):    self.val = x    self.left = left    self.right = rightdef 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) + 1if __name__ == '__main__':  """  tree是一個表示樹根節點的對象  前序遍歷 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))