【数据结构】二叉树的逻辑结构 |
您所在的位置：网站首页 › 完全二叉树的基本性质是什么 › 【数据结构】二叉树的逻辑结构 |
|
研究二叉树的意义？
问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。 二叉树的定义二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 注意二叉树定义的递归性！！！ 二叉树的特点：⑴ 每个结点最多有两棵子树； ⑵ 二叉树是有序的，其次序不能任意颠倒。 特殊的二叉树 斜树1、定义 1 .所有结点都只有左子树的二叉树称为左斜树；2 .所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。2、斜树的特点 1、在斜树中，每一层只有一个结点；2、斜树的结点个数与其深度相同。 满二叉树1、定义 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。 2、特点 叶子只能出现在最下一层； 只有度为0和度为2的结点。 满二叉树在同样深度的二叉树中结点个数最多 满二叉树在同样深度的二叉树中叶子结点个数最多 完全二叉树1、定义 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。 2、构造 在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。 3、特点 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。深度为k的完全二叉树在k-1层上一定是满二叉树。 二叉树的基本性质 1、二叉树的第i层上最多有2i-1个结点（i≥1）。 2、一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。 3、在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0＝n2＋1。在有n个结点的满二叉树中，有多少个叶子结点？ 叶子结点n0＝（n + 1）/2 4、完全二叉树的基本性质1、 具有n个结点的完全二叉树的深度为 【log2n】 （向下取整） +1。 2、 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1≤i≤n）的结点（简称为结点i），有： 如果i＞1，则结点i的双亲结点的序号为 i/2；如果i＝1，则结点i是根结点，无双亲结点。如果2i≤n，则结点i的左孩子的序号为2i；如果2i＞n，则结点i无左孩子。如果2i＋1≤n，则结点i的右孩子的序号为2i＋1；如果2i＋1＞n，则结点 i无右孩子。故有： 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则 结点i的双亲结点为 i/2；结点i的左孩子为2i；结点i的右孩子为2i＋1。性质（2）表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |