关于树
树是一种数据结构，由n个有限节点组成的一个具有层次关系的集合。二叉树则是每个节点最多有两个子树的树结构。二叉树一般有以下性质：
- 二叉树第k层上的节点数目最多为 2k−12k−1
- 深度为 h 的二叉树至多有 2h−12h−1 个节点。
- 包含 n 个节点的二叉树的高度至少为 log2(n+1)log2(n+1)
- 在任意一棵二叉树中，若叶子节点的个数为n0n0，度为2的节点数为n2n2，则n0=n2+1n0=n2+1
二叉树的简单实现
class Node(object): def __init__(self,val=None,left=None,right=None): self.val = val self.left = left self.right = right class Tree(object): def __init__(self,node=None): self.root = node def add(self,item=None): node =Node(val=item) if not self.root or self.root.val is None: self.root = node else: queue = [] queue.append(self.root) while True: current_node = queue.pop(0) if current_node.val is None: continue if not current_node.left: current_node.left = node return elif not current_node.right: current_node.right = node return else: queue.append(current_node.left) queue.append(current_node.right) tree = Tree() for i in range(10): if i == 3: i = None tree.add(i)
树的结构如下：
