每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k1个结点深度为m的满二叉树有2m1个结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。二叉树基本性质：1在二叉树的第k层上，最多有2k1k≥1个结点；2深度为m的二叉树最多有2m1个结点；3度为0的结点（即叶子结点）总是比度为2的结点多一个；4具有
个结点的二叉树，其深度至少为log2
1其中log2
表示取log2
的整数部分5具有
个结点的完全二叉树的深度为log2
1；6设完全二叉树共有
个结点。如果从根结点开始，按层序（每一层从左到右）用自然数12…
给结点进行编号（k12…
），有以下结论：
①若k1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INTk2；②若2k≤
，则k结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；③若2k1≤
，则编号为k的结点的右子结点编号为2k1；否则该结点无右子结点。补充：增加度为1的结点不会影响二叉树的叶子结点数，每增加一个度为2的结点便会增加一个叶子结点，没有度为2的结点时叶子结点数为1。已知完全二叉树有x个结点，求其叶子结点数：①确定层数为k；②第k层的结点数yx2k11；③第k1层的叶子结点数
2k11y2若y2有余，则要加1；④最后y
。二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历：（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（树根在第一，下走不跳结点）（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（有左先左，再寻根，后找右。最左边的结点最先遍历，最右边的结点最后遍历）（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。（有左先左，再找右，后寻根，到最右一路上行，树根在最后）

f
前序遍历结果为abdehicfg；中序遍历结果为dbheiafcg；后序遍历结果为dhiebfgca例2：先序遍历图113的二叉树。
图113
先访问整棵二叉树的根结点A，然后再先序遍历左子树T1；在访问T1时，也以先序遍历原则，先访问T1的根结点B，然后再先序遍历T1的左子树T11；在访问T11时，也以先序遍历原则，先访问T11的根结点D，然后再先序遍历T11的左子树。由于此时T11的左子树只有H结点r