数据结构_010_树和二叉树基本概念
树型结构介绍
树形结构就像一颗倒着的树,根朝上,叶子朝下。树有一个唯一的根节点,可以分发出很多个分支,每个分支也可以继续分发分支。
树形结构的基本概念
树是n(n≧0)个结点的有限集。n=0时称为空树,n>0是非空树。在任意一颗非空树中:有且仅有一个特定的称为根的结点。
对于非空树来说,只有一个根节点,其余结点可分为m(m>0)个互不相交的有限集T1、T2、T3……、Tm,其中每个集合本身又是一棵树,并且称为根的子树。
>>树相关的术语<<
结点分类:
-
结点:包含 数据元素和 若干个指向子树的分支。 -
子结点:一个结点 含有的子树的根结点称为该结点的子结点。 -
叶子结点或终端结点: 度为0的结点。K,L,F,G,H,M,J都是叶子结点。 -
分支结点或非终端结点: 度不为0的结点。除根节点外,分支结点也称为 内部结点。 -
结点的度:结点 拥有子树数。A的度为3,C的度为1,H的度为0。 -
树的度:树内各个结点 度的最大值。上图树的度为3。
结点关系:
-
双亲结点或父节点:若一个结点含有子结点,则这个结点称为其子结点的父结点。B是F的双亲。
-
兄弟结点:同一个双亲/父节点的子节点之间互称为兄弟结点。E,F,G互为兄弟。
-
结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推。上图F为第三层。
-
树的深度:树中结点的最大层次称为树的深度或高度。上图树的深度为4。
-
堂兄弟结点:双亲在同一层的结点互为堂兄弟。E和F,G,H,I,J互为堂兄弟。
-
结点的祖先:从根到该结点所经分支上的所有结点。K的祖先是E,B,A。
-
结点的子孙:以某结点为根的子树中任一结点都称为该结点的子孙。B的子孙,E,F,G,K,L。
其他:
-
路径:树中 两个结点之间所经过的结点序列。K到A之间的路径为K-E-B-A。 -
路径长度: 两个结点之间路径上经过的边数。K到A的路径长度为3。树中任意两个结点之间的路径都是唯一的。 -
森林:由 m(m>=0)棵不相交的树组成的集合。 -
有序树:结点的 各个子树从左至右有序,不能互换位置。 -
无序数:结点 各个子树可互换位置。
树的存储结构
顺序存储:
-
双亲表示法。 -
孩子表示法。 -
双亲孩子表示法。
链式存储:
-
孩子链表表示法。 -
孩子兄弟表示法。
二叉树概念
二叉树(Binary Tree)是由n(n>=0)个结点构成的有限集合,该集合可能为空树(空二叉树),或者由一个根节点和两颗互不相交的左子树和右子树的二叉树组成。
左子树和右子树是有序的,不可以互换。二叉树中不存在度大于2的结点。
二叉树的形态
>>二叉树的五种形态<<
>>三个结点二叉树的五种形态<<
特殊的二叉树
>>满二叉树<<
如果该二叉树的所有叶子节点都在最后一层,并且结点总数= 2^n -1 , n 为层数,也就是说二叉树的每一层的结点都充满了,我们称之为满二叉树。
>>完全二叉树<<
除了最后一层,其他层都是充满的,也就是说所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为完全二叉树。
二叉树的性质
性质1:在二叉树的第i层上最多有 个结点。
第一层:1个结点,第二层:2个结点,第三层:4个结点……
性质2:深度为k的二叉树最多有 个结点。
假设每一层都满层,则深度为k的二叉树结点数最多为 。
性质3:对任意二叉树,若叶子数为 ,度为2的结点数为 ,那么 。
假设二叉树的总结点为 ,叶子结点个数为 个,度为1的结点个数为 个,度为2的结点个数为$n_2
。
暂时把树干叫做分支,因为叶子结点的分支为0,度为1的结点的分支为1,度为2的结点的分支为2,且二叉树的总结点数量为 ,为什么减1呢,因为根节点没有树干。
结合这两个式子就可得出结论了。
性质4:针对完全二叉树:具有n个结点的完全二叉树的深度k满足 ,k为整数。
假设完全二叉树的深度为k,完全二叉树的倒数第二层一定是满的。
最少结点的情况,最后一层只有一个结点,且在最左边,总结点个数为 。
最多结点的情况,最后一层也是满的,总结点个数为 。
所以 ,因为n是整数,则所以 ,取对数则得到结论。
性质5:针对完全二叉树:假如从上至下,从左至右编号,则编号为 的结点,其左子节点的编号是 ,其右子节点编号为 ,其父节点的编号为 。
❝假如一棵完全二叉树有1001个元素,那么叶子结点有多少个?
1001/2 = 500,最后一个拥有子结点的结点的编号为500,那么叶子结点有1001-500=501个。
二叉树存储方式
二叉树的存储方式分为顺序存储和链式存储。
>>顺序存储<<
假如是完全二叉树,我们就可以拿数组来表示这棵树。
假如是普通的二叉树,我们可以把缺少的位置用0来弥补。但是普通二叉树可能需要补很多0的位置,浪费空间。
>>链式存储<<
链式存储有两种,
-
一个数据域,两个指向左右子结点的指针。 -
一个数据域,两个指向左右子节点的指针,和一个指向父节点的指针。