# 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)) 
