vlambda博客
学习文章列表

数据结构_010_树和二叉树基本概念

树型结构介绍

  树形结构就像一颗倒着的树,根朝上,叶子朝下。树有一个唯一的根节点,可以分发出很多个分支,每个分支也可以继续分发分支。

树形结构的基本概念

  树是n(n≧0)个结点的有限集。n=0时称为空树,n>0是非空树。在任意一颗非空树中:有且仅有一个特定的称为根的结点。

  对于非空树来说,只有一个根节点,其余结点可分为m(m>0)个互不相交的有限集T1、T2、T3……、Tm,其中每个集合本身又是一棵树,并且称为根的子树。

>>树相关的术语<<

数据结构_010_树和二叉树基本概念

结点分类:

  • 结点:包含 数据元素和 若干个指向子树的分支。
  • 子结点:一个结点 含有的子树的根结点称为该结点的子结点。
  • 叶子结点或终端结点度为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的结点。

二叉树的形态

>>二叉树的五种形态<<

数据结构_010_树和二叉树基本概念

>>三个结点二叉树的五种形态<<

数据结构_010_树和二叉树基本概念

特殊的二叉树

>>满二叉树<<

  如果该二叉树的所有叶子节点都在最后一层,并且结点总数= 2^n -1 , n 为层数,也就是说二叉树的每一层的结点都充满了,我们称之为满二叉树。

>>完全二叉树<<

 除了最后一层,其他层都是充满的,也就是说所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为完全二叉树。

数据结构_010_树和二叉树基本概念

二叉树的性质

  性质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个。

数据结构_010_树和二叉树基本概念

二叉树存储方式

  二叉树的存储方式分为顺序存储和链式存储。

>>顺序存储<<

  假如是完全二叉树,我们就可以拿数组来表示这棵树。

  假如是普通的二叉树,我们可以把缺少的位置用0来弥补。但是普通二叉树可能需要补很多0的位置,浪费空间。

>>链式存储<<

  链式存储有两种,

  • 一个数据域,两个指向左右子结点的指针。
  • 一个数据域,两个指向左右子节点的指针,和一个指向父节点的指针。