我
二叉树相关性质
节点的度：一个节点含有的子树的个数称为该节点的度；
叶节点或终端节点：度为零的节点；
节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推。
树的高度或深度：树中节点的最大层次。
在非空二叉树中，第 i 层的结点总数不超过 2^(i-1)，i>=1。
深度为 h 的二叉树最多有 2^h-1 个结点(h>=1)，最少有 h 个结点。
对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2 的结点总数为 N2，则 N0 = N2+1；
给定 N 个节点，能构成 h(N) 种不同的二叉树。h(N)为卡特兰数的第 N 项。(2n)!/(n!(n+1)!)。
二叉树的前序遍历，首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
二叉树的中序遍历，首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
二叉树的后序遍历，首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。
二叉树是非线性数据结构，但是顺序存储结构和链式存储结构都能存储。
一个带权的无向连通图的最小生成树的权值之和是唯一的。
只有一个结点的二叉树的度为 0 。
二叉树的度是以节点的最大的度数定义的。
树的后序遍历序列等同于该树对应的二叉树的中序序列。
树的先序遍历序列等同于该树对应的二叉树的先序序列。
线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写出二叉树的中序遍历序列：debxac，中序遍历中在 x 左边和右边的字符，就是它在中序线索化的左、右线索，即 b、a 。
递归式的先序遍历一个 n 节点，深度为 d 的二叉树，需要栈空间的大小为 O（d），因为二叉树并不一定是平衡的，也就是深度 d！=logn，有可能 d>>logn。所以栈大小应该是 O（d）
一棵具有 N 个结点的二叉树的前序序列和后序序列正好相反 ，则该二叉树一定满足该二叉树只有左子树或只有右子树，即该二叉树一定是一条链（二叉树的高度为 N，高度等于结点数）。
引入二叉线索树的目的是加快查找结点的前驱或后继的速度。
二叉树线索化后，先序线索化与后序线索化最多有 1 个空指针域，而中序线索化最多有 2 个空指针域。
不管是几叉树，节点数等于=分叉数+1
任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序不发生改变。