解决二叉树的编程问题(共25张PPT).pptx

解决二叉树的编程问题 本资源摘要信息涵盖了二叉树的基本概念、逻辑结构、存储结构、基本操作和主要性质等方面的知识点。 一、基本概念 * 二叉树的定义：二叉树是一种树形结构，由一个根结点和两个不相交的子树组成。 * 结点的度：结点所拥有的子树的个数称为该结点的度。 * 叶结点：度为0的结点称为叶结点或终端结点。 * 分支结点：度不为0的结点称为分支结点或非终端结点。 * 左孩子、右孩子、双亲：树中一个结点的子树的根结点称为这个结点的孩子，而这个结点称为它孩子结点的双亲。 * 路径、路径长度：一棵树的一串结点n1,n2,…,nk的路径长度是k-1。 二、逻辑结构 * 二叉树的逻辑结构：二叉树可以分为根结点、左子树和右子树三个部分。 * 结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。 * 树的深度：树中所有结点的最大层数称为树的深度。 * 树的度：树中各结点度的最大值称为该树的度。 三、存储结构 * 二叉树的存储结构：二叉树可以使用链表或数组来存储。 * 链表存储：每个结点都包含一个数据域和两个指针域，指向左子树和右子树。 * 数组存储：使用数组来存储二叉树的结点，结点的索引可以计算出其左子树和右子树的索引。 四、基本操作 * Initiate（bt）：建立一棵空二叉树。 * Create（x，lbt，rbt）：生成一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左子树和右子树的二叉树。 * InsertL（bt，x，parent）：将数据域信息为x的结点插入到二叉树bt中作为结点parent的左孩子结点。 * InsertR（bt，x，parent）：将数据域信息为x的结点插入到二叉树bt中作为结点parent的右孩子结点。 * DeleteL（bt，parent）：在二叉树bt中删除结点parent的左子树。 * DeleteR（bt，parent）：在二叉树bt中删除结点parent的右子树。 * Search（bt，x）：在二叉树bt中查找数据元素x。 * Traverse（bt）：按某种方式遍历二叉树bt的全部结点。 五、主要性质 * 性质1：一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。 * 性质2：一棵深度为k的二叉树中，最多具有2k－1个结点。 * 性质3：对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有：n0＝n2＋1。 * 性质4：具有n个结点的完全二叉树的深度k为[log2n]+1。 * 性质5：对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：（1）如果i>1，则序号为i的结点的双亲结点的序号为i/2（“/”表示整除）；如果i＝1，则序号为i的结点是根结点，无双亲结点。（2）如果2i≤n，则序号为i的结点的左子树的根结点的序号为2i，右子树的根结点的序号为2i＋1。