数据结构中树基础知识总结 |
您所在的位置：网站首页 › 数据结构中节点是什么 › 数据结构中树基础知识总结 |
数据结构中树基础知识总结
性质1： 在二叉树的第i层上至多有 [2^(i-1)]个节点(i >=1,也即根节点处为第一层);
性质2： 深度为k(最多是k+1层)的二叉树至多有 [(2^k) - 1] 个结点(k >= l);
性质3： 对任何一棵二叉树T，若其叶子节点数为 n0，度为2的节点数为 n2，则n0 = n2 + 1；
补充：
一棵二叉树 ， 除了叶子结点外，剩下的就是度为1和度为2的节点，若设度为1的节点数为 n1, 则树T的总节点数为 n = n0 + n1 + n2
性质4： 具有 n 个结点的完全二叉树的深度为【lon2(n)】 + 1（其中【x】表示不大于x的最大整数，可由性质2 求 k来)
性质5： 如果对一棵有n个结点的完全二叉树（其深度为【lon2(n)】 + 1）的结点按层序编号（从第1层到第【lon2(n)】 + 1层，每层从左到右），
对任一结点i（1n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
3.如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。
二、特殊二叉树
1、斜树：
分为左斜树（所有节点都只有左子树）、右斜树（所有节点都只有右子树）
2、满二叉树：
如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
深度为n的满二叉树的总节点数为： (2^n) - 1； 叶子节点数为：2^(n - 1)
特点：
（1）叶子只能出现在最下一层。出现在其他层就不可能达成平衡。
（2）非叶子结点的度一定是2。否则就是“缺胳膊少腿”了。
（3）在同样深度的二又树中，满二又树的结点个数最多，叶子数最多。
3、完全二叉树：
完全二叉树就是除了最后一层，其余的都是满二叉树，最后一层的节点都连续靠左（也即，不能存在有右节点，而没有左节点得情况）。深度为n的完全二叉树的最少的节点数为：[2^(n-1) -1 ] + 1 注意： 因为最后一层不是满的，所以倒数第二层也露出了一些节点，那些节点也算是叶子节点！ 
满二叉树一定是完全二叉树，但完全二叉树不一定是满的；
完全二叉树性质：
（1）叶子结点只能出现在最下两层。
（2）最下层的叶子一定集中在左部连续位置（你只要是完全二叉树，最下层的叶子的左子树一定存在）
（3）倒数二层，若有叶子结点，一定都在右部连续位置（你只要是完全二叉树，倒数第二层的叶子的右子树一定存在）
（4）如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
（5）同样结点数的二叉树，完全二叉树的深度最小
4、线索二叉树
对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化，这样对我们的插入删除结点、查找某个结点都带来了方便。线索二叉树的线索数就是空指针域的数目。 若有n个节点的线索二叉树，每个节点都有指向左右孩子的两个指针域，则共有2n个指针域，而n个节点共有n-1条分支，所以共有2n-(n-1)个空指针域，即有n+1个线索。 5、扩充二叉树对给定的二叉树，对其中不足两个孩子的节点（包括叶子节点）添加外部附加节点，使得每个节点都有两个孩子节点，所得的二叉树称为原二叉树的扩充二叉树。原节点称为内部节点，新加的节点称作外部节点。对于具有n个内部节点的二叉树，其外部节点个数为 n+1
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上分支数目称作路径长度 每经过一个节点，路径长度都得加1。树的路径长度就是从根到每一结点的路径长度之和。
树的带权路径长度（记为“WPL”）为树中所有叶子节点的 带权路径长度之和。我们把 带权路径长度 WPL 最小的二叉树称做哈弗曼树。上述哈弗曼树 WPL=7 * 1 + 5 * 2 + 2 * 3 + 4 * 3，一般情况下，权值越大的叶子离根越近，那么二叉树的WPL就越小 4个节点k1 k2 k3 k4，分别带权10 16 20 6利用他们做外部节点构造huffman树，求其带权路径长度之和即WPL？ 解释：4个外节点，则有3个内部节点，看5、6可知。
有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树 无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树 换而言之，兄弟结点有顺序的树，称为有序树，兄弟之间无顺序的树称为无序树。 三、遍历二叉树 前序遍历：（根左右）（属于深度优先遍历，DFS用栈实现） 前序遍历第一个为根节点； 前序遍历最后一个节点为整棵树的最右侧的节点（或同为最右侧节点） 中序遍历：（左根右） 中序遍历被根节点截割成左右子树（又一棵小二叉树） 后序遍历：（左右根） 后序遍历最后一个为根节点； 后序遍历第一个节点为整棵树的最左侧的节点（或同为最左侧节点） 以上三种遍历方式不管是递归形式还是非递归形式，其空间复杂度均为O(h)，h表示树的高度； 层次遍历：（从上之下，从左至右）（属于广度优先搜索，BFS可用队列实现） 由前序遍历或后序遍历 和 中序遍历 还原二叉树：中序遍历被根节点截割成左右子树（在小子树中第一个又是根节点），再由前序/后序确定根；循环使用。 由前序遍历和后序遍历（ 缺少中序遍历） 还原二叉树： 仅给定的是先序和后序遍历序列则不能还原二叉树。但是， 可以由先序和后序遍历序列但可以确定二叉树中结点的祖先关系。 1、当两个结点的前序序列为AB与后序序列为BA的组合时，则A为B的祖先（父节点）； 2、当存在三个连续且其中两个位置一样，则位置不一样的是根，看前序遍历确定根（应该是正三角形状）； 3、当存在三个连续且没有位置一样，则为三层结构； 以上2、3还不确定，待归纳证明；（ 也欢迎大家留言交流） 【例题1】 一颗二叉树的前序遍历是ABCDFGHE，后序遍历是BGHFDECA，中序遍历是？ (A): GHBADFCE (B): DGBAFHEC (C): BADGFHCE (D): BAGDFHEC 正确答案: C(更改此处颜色可看答案) 解析：给定的是先序和后序遍历序列则不能还原二叉树。 由前序遍历我们可以得到：A为整棵树的根节点，E为整棵树最右边的节点； 由后序遍历我们可以得到：B为整棵树最左边的节点四、二叉树、树、森林转换 将树转换为二叉树的步骤如下 1、加线。在所有兄弟结点之间加一条连线。 2、去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。 3、层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。 注意第一个孩子是二又树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。 
将森林转换为二叉树的步骤如下 1、把每个树转换为二叉树。 2、第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。 
将二叉树转换为树步骤如下： 1、加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点……哈，反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。 2、去线。删除原二又树中所有结点与其右孩子结点的连线。 3、层次调整。使之结构层次分明。 
将二叉树转换为树步骤如下： 判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。那么如果是转换成森林，步骤如下： 1、从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树。 2、再将每棵分离后的二叉树转换为树即可。 
|
【本文地址】
今日新闻 |
推荐新闻 |