“二叉树是另一种树形结构。”
对于一棵树而言，加一些限制，就会变成二叉树。-每个结点至多只有两棵子树，也就是说二叉树中每个节点的度都≤2；-子树有左右之分，其次序不能任意颠倒。01
—
二叉树
树是n（n≥0）个结点的有限集合，而二叉树是加了限制条件的树，二叉树也是n（n≥0）个结点的有限集合。n=0，为空二叉树；n＞0，或由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。看图！那么，一个度为2的有序树就是二叉树，对还是错？错！度为2的树至少有3个结点，而二叉树可以为空。度为2的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的。02
—
二叉树整的那些花样
满二叉树除了叶子节点，其他节点的度都为2，就是满二叉树。完全二叉树就是满二叉树的阉割版！满二叉树的最后一行，从右往左，按顺序删掉一些叶子节点，就得到了完全二叉树。上面这个图，第三个就只是一个普通的二叉树了，因为它并不是满二叉树最后一行从右往左删掉一些节点得来的。而是凭空删掉了倒数第二个节点。二叉排序树二叉排序树二叉树的结构没什么限制，它限制的是节点里面存的数值。二叉排序树里面，任意一个节点，该节点的值，比它的左子树节点的值更大，比右子树节点的值更小。这就是二叉排序树。比如看上面，
在这里，50是根节点，
50的左子树是25，比50小，
右子树是，比50大，
然后的左子树是80，比根节点更大，比更小。
03
—
二叉树的性质
1)、非空二叉树上的叶子结点数等于度为2的结点数加1，即n0=n2+1。2)、非空二叉树上第k层上至多有2^(k-1)个结点（k≥1）。3)、高度为h的二叉树至多有2^h-1个结点（h≥1）。4)、对完全二叉树按从上到下、从左到右的顺序依次编号1，2，...，n，有以下关系:①当t1时，结点i的双亲的编号为i/2，即当i为偶数时，其双亲的编号为i/2，它是双亲的左孩子；当i为奇数时，其双亲的编号为(i一1)/2，它是双亲的右孩子。②当2i≤n时，结点i的左孩子编号为2i，否则无左孩子。③当2i+1≤n时，结点i的右孩子编号为2i+1，否则无右孩子。④结点i所在层次(深度)为log2i+1。5)、具有n个（n0）结点的完全二叉树的高度为log2(n+1)或log2n+1。其中！！！最重要的公式，有两个！！！1、N=N0+N1+N22、N=N1+2×N2+1这两个式子，用的特多！！！啥意思？N就是二叉树结点的总个数，N0就是度为0的结点的个数，N1就是度为1的结点的个数，以此类推。然后，第一个式子，也就是，二叉树的结点个数，等于度为0、1、2的结点个数想加的和。第二个式子，也很好理解，一个度为1的结点，其子节点有一个，度为2的结点，子节点有两个。所以就得到了N=0×N0+N1+2×N2+1。注意！+1不能忘了！！在题目中，比如题目问你度为1的节点个数，度为2的节点个数，你就能通过联立这两个式子，得到答案！如果觉得有用，不点个再看么少年？↓[]~(￣▽￣)~*
小冰冲冲冲