二叉树基本性质

第 i 层的节点数最多为2^i-1 个(i>=1)。深度为K 的二叉树中，节点总数N最多为2^K-1个(k>=1)。 eg: 设k为4，为满二叉树，证明2^k-1方程。 2⁰+2¹+2²+2³ = 2⁴-1 由第二条可推算出，具有N个结点的二叉树的深度为 [log₂N]+1 。 --------即 K=[log₂N]+1 -------- 总节点数N=N₁ 个度为1的结点，N₂个度为2的结点，N₀个度为0的结点相加。 --------即N=N₀+N₁+N₂--------总分支数M=总结点数N-1。即M=N-1；如果由度为1或度为2的结点来计算总分支数M。** --------即M=N₁+2N₂-------- 由第四条可推算出，总结点N=度为1的结点+2倍的度为2的结点+1。 --------即N=N₁+2N₂+1--------由第三条和第五条结合可推算出，度为0的结点总比度为2的结点多一个。 --------即N₀=N₂-1-------- 设一颗有N个结点的完全二叉树的结点从1到N按照层次顺序编号（从左到右）编号，对任意一结点 i（1<=i<=N），有多种情况。 i=1时，结点 i 是二叉树的根，没有父结点。i>1时，父结点的编号为 [i/2]。（向下舍入）2i>N时，在此范围内无左子结点。2i<N时，左子结点的编号为 2i 。2i+1>N时，在此范围内无右子结点。2i+1<N时，右子结点的编号为2i+1。

二叉树的存储结构

二叉树可用顺序存储结构也可用链式存储结构。

链式存储结构

存储方法：数据域、指针域（左指针域、右指针域） 二叉树的存储方法 可根据二叉树的性质来计算出各结点的层次关系。

顺序存储结构

将二叉树存储在一个数组里，通过存储元素的下标来反映元素之间的上下件关系。

二叉树的遍历

遍历 指 按一定的次序访问二叉树中的每一个结点。

遍历：前序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD） D(Data)：访问根结点 L(lchild)：遍历根结点的左子树 R(rchild)：遍历根结点的右子树

⚠️：二叉树为空时，则结束返回。

前序遍历（DLR）/ 先根遍历 / 先序遍历

访问顺序为（1）访问根结点（2）遍历根结点的左子树（3）遍历根结点的右子树 解释：首先访问根结点A并记录，随后进行遍历根结点A的左子树；将B作为根结点进行访问并记录，随后进行遍历根结点B的左子树；将D作为根结点进行访问并记录，随后进行遍历根结点D的左子树；将G作为根结点进行访问并记录，随后进行遍历根结点G的左子树，因根结点G无左子树，所以转换为遍历右子树；将I作为根结点进行访问并记录，因根结点I的左子树和右子树都为无，所以向上返回到根结点G；因根结点G的左右子树已遍历完，所以再向上返回到根结点D；因根结点D的右子树为无，所以再向上返回到根结点B；开始遍历根结点B的右子树，将E作为根结点进行访问并记录，因根结点E的左子树和右子树都为无，所以向上返回到根结点A；开始遍历根结点A的右子树；将C作为根结点进行访问并记录，因根结点C无左子树，所以转换为遍历右子树；将F作为根结点进行访问并记录，随后进行遍历根结点F的左子树；将H作为根结点进行访问并记录，随后进行遍历根结点J的左子树；将J作为根结点进行访问并记录，因根结点J的左子树和右子树都为无，所以向上返回到根结点H；开始遍历根结点H的右子树，将K作为根结点进行访问并记录，因根结点K的左子树和右子树都为无，所以向上返回到根结点H；因根结点H的左右子树已遍历完，所以再向上返回到根结点F，根结点F的右子树为无，所有节点访问完成。

中序遍历（LDR）/ 中根遍历

访问顺序为（1）遍历根结点的左子树（2）访问根结点（3）遍历根结点的右子树 解释：首先遍历根结点A的左子树，因根结点A有左子树，所以将B作为根结点开始遍历根结点B的左子树；因根结点B有左子树，所以将D作为根结点开始遍历根结点D的左子树；因根结点G无左子树，所以开始访问并记录根结点G；随后进行遍历根结点G的右子树；将I作为根结点，因根结点I无左子树，所以开始访问并记录根结点I；因根结点I无右子树，所以返回根结点G；因根结点G已遍历完，所以返回根结点D；开始访问并记录根结点D；因根结点D无右子树，所以返回根结点B；开始访问并记录根结点B；随后进行遍历根结点B的右子树；将E作为根结点，因根结点E无左子树，所以开始访问并记录根结点E；因根结点E无右子树，所以返回根结点B；因根结点B已遍历完，所以返回根结点A；开始访问并记录根结点A；随后进行遍历根结点A的右子树；将C作为根结点，因根结点C无左子树，所以开始访问并记录根结点C；随后进行遍历根结点C的右子树；将F作为根结点，因根结点F有左子树，所以将H作为根结点开始遍历根结点H的左子树；因根结点H有左子树，所以将J作为根结点；因根结点J无左子树，所以开始访问并记录根结点J；因根结点J无右子树，所以返回根结点H；开始访问并记录根结点H；随后进行遍历根结点H的右子树；将K作为根结点，因根结点K无左子树，所以开始访问并记录根结点K；因根结点K无右子树，所以返回根结点H；因根结点H已遍历完，所以返回根结点F；开始访问并记录根结点F；所有节点访问完成。

后序遍历（LRD）/ 后根遍历

访问顺序为（1）遍历根结点的左子树（2）遍历根结点的右子树（3）访问根结点 解释：首先遍历根结点A的左子树，因根结点A有左子树，所以将B作为根结点开始遍历根结点B的左子树；因根结点B有左子树，所以将D作为根结点开始遍历根结点D的左子树；因根结点G无左子树，所以转换为访问根结点G的右子树；将I作为根结点，因根结点I无左右子树，所以开始访问并记录根结点I；因根结点I已遍历完，所以返回根结点G；因根结点G已遍历完，所以开始访问并记录根结点G；随后返回根结点D；因根结点D无右子树，所以开始访问并记录根结点D；因根结点D已遍历完，所以开始访问并记录根结点D；随后返回根结点B；随后进行遍历根结点B的右子树；将E作为根结点，因根结点E无左右子树，所以开始访问并记录根结点E；随后返回根结点B；因根结点B已遍历完，所以开始访问并记录根结点B；随后返回根结点A；随后进行遍历根结点A的右子树；将C作为根结点，因根结点C无左子树，随后进行遍历根结点C的右子树；将F作为根结点，因根结点F有左子树，所以将H作为根结点开始遍历根结点H的左子树；因根结点H有左子树，所以将J作为根结点；因根结点J无左右子树，所以开始访问并记录根结点J；因根结点J已遍历完，所以返回根结点H；随后进行遍历根结点H的右子树；将K作为根结点，因根结点K无左右子树，所以开始访问并记录根结点K；因根结点K已遍历完，所以返回根结点H；因根结点H已遍历完，所以开始访问并记录根结点H；随后返回根结点F；因根结点F无右子树，所以开始访问并记录根结点F；随后返回根结点C；因根结点C已遍历完，所以开始访问并记录根结点C；随后返回根结点A；因根结点A已遍历完，所以开始访问并记录根结点A；所有节点访问完成。