二叉树笔记
二叉树
二叉树:每个节点至多只有两棵子树满二叉树:深度为k，有2^k-1个节点（全部排满）的二叉树完全二叉树:除了最后一层全部排满，最后一层子节点从左至右连续排


性质
二叉树的第i层上排满时2^(i-1)个节点深度为k的二叉树排满时节点数为2^k-1任意二叉树，度为0，1，2的节点个数分别为n0,n1,n2，则：n0=n2+1(证明:n0+n1+n2-1=2*n2+n1,即所有入度=所有出度)给一颗二叉树从根到叶，从左到右，从1开始编号，则有性质： 1）根节点序号为1
2）若一个节点序号为i，则其左孩子和右孩子序号分别为2i和2i+1
3) 若一个节点序号为i，则其父节点序号为floor(i/2)