第第55章树和二叉树章树和二叉树（（Tree&BinaryTreeTree&BinaryTree））1.树的基本概念2.二叉树3.遍历二叉树4.线索二叉树5.树的应用特点：非线性结构，一个直接前驱，但可能有多个直接后继。（一对多或1:n）二叉树的定义、性质和存储结构二叉树的运算树适于反应层次关系的数据对象的研究。层次化的数据之间可能有:祖先—后代、上级—下级、整体—部分等其它类似的关系。学院法学院工商学院信息学院金融学院人文学院会计学院财税学院计算机系信息系统计系图5.1.1一棵学院信息的树5.1.15.1.1树的定义树的定义由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root）当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。树的定义具有递归性，即“树中还有树”。一棵树至少包含一个树结点，不存在不含树结点的树；树中结点存在着层次关系，但同一层上的树结点之间是无序的。一棵树的每个结点都是某个子树的根。若干术语若干术语——（也称父亲）即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点ABCGEIDHFJFLK根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)ABCGEIDHFJFLK——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝1334（有几个直接后继就是几度，亦称“次数”）ABCDEFGHIJKLM结点A的度：?结点B的度：?结点M的度：?叶子：?结点A的孩子：?结点B的孩子：?结点I的双亲：?结点L的双亲：?结点B，C，D为?结点K，L为?树的度：?结点A的层次：?结点M的层次：?树的深度：?结点F，G为?结点A是结点F，G的?320B，C，DE，F314K，L，F，G，M，I，JDE兄弟兄弟4堂兄弟祖先5.2.1二叉树的定义定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点–每个结点至多有二棵子树(即不存在度大于2的结点)–二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空2.2.二叉树的定义与树的定义的区别二叉树的定义与树的定义的区别1.二叉树存在着空树；但树不能为空。2.二叉树中的每一个结点只可能有0个，1个或2个孩子，也就是说，二叉树不存在度大于2的结点；而树中的每个结点可以有多个子树。3.二叉树的子树有左右之分，两者不能颠倒；但树的子树一般是无序的。除以上区别外，上一节引入树的有关术语对于二叉树也适用。3.3.满二叉树的定义满二叉树的定义若二叉树中所有分枝结点的度数都为2，且叶子结点都在同一层上，则称这类二叉树为满二叉树。5.完全二叉树的定义若二叉树中所有分枝结点的度数要就为2，要就为0，称这类二叉树为完全二叉树。4.顺序二叉树的定义:对满二叉树从上至下，从左至右地从1开始编号，结果是每个结点都可以与满二叉树中编号为1至n的结点一一对应6.退化二叉树的定义:如果一棵非空的二叉树只有一个叶子，且其余结点均只有一个孩子ABCDEFG图5.2.2一棵满二叉树123456789101112图5.2.4一棵顺序二叉树图5.2.5一棵非顺序二叉树12345678912图5.2.8退化的二叉树AIDB12472852(a)(b)5.2.25.2.2二叉树的性质二叉树的性质性质1:在二叉树的第i层上最多有2i-1个结点（i≥1）。用归纳法证明它。1.当i=1时，21-1=1，这时只有一个根结点，显然结论是正确的。2.假...
