数据结构与算法：树和二叉树.pptx

树和二叉树; 树和二叉树; 1 树的基本概念;2 树的基本术语 ⑴ 结点(node)：一个数据元素及其若干指向其子树的分支。 ⑵ 结点的度(degree) 、树的度：结点所拥有的子树的个数称为结点的度。树中结点度的最大值称为树的度。 【练习】 下图(b)中各结点的度与树的度分别是多少？ ;⑶ 叶子(left)结点、非叶子结点：树中度为0的结点称为叶子结点(或终端结点)。相对应地，度不为0的结点称为非叶子结点(或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。 如上图(b)中结点H、I、J、K、L、M、N是叶子结点，而所有其它结点都是分支结点。 ⑷ 孩子结点、双亲结点、兄弟结点 一个结点的子树的根称为该结点的孩子结点(child)或子结点；相应地，该结点是其孩子结点的双亲结点(parent)或父结点。; 2 二叉树;二叉树在树结构中起着非常重要的作用。因为二叉树结构简单，存储效率高，树的操作算法相对简单，且任何树都很容易转化成二叉树结构。上节中引入的有关树的术语也都适用于二叉树。 2.二叉树的基本形态 二叉树有5种基本形态，如图所示。; 2 二叉树--二叉树的性质;1.满二叉