导言:树作为数据结构中最为基本的数据结构形式，它是由若干个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的，这一小节主要讲述的是树和二叉树的基本概念。
敲黑板，上课啦！
1.树的基本概念
1.1树的定义
树是由
个结点的有限集合,
的时候称为空树,这是一种特殊的情况.在任意一棵非空树中应当满足:
1)有且仅有一个特定的称为根的结点;
2)当
的时候,其余结点可以分为
个互不相交的有限集合
,其中每一个集合体本身又是一棵树,并且称为根节点的子树.
树有以下的两个具体的特点:
1)树的根节点没有前驱结点,除了根结点之外的所有结点有且只有一个前驱结点.
2)树中所有结点可以有零个或者多个后继结点.
1.2树的基本术语
如图所示
1.考虑到结点K.根A到结点K的唯一路径上的任意结点称为K的祖先结点,而结点K是结点B的子孙节点.路径上最接近结点K的结点E称为K的双亲结点,而K为结点E的孩子结点.根A是树上唯一没有双亲的结点.有相同双亲的结点称为兄弟结点(例如结点K,L).
2.树中一个结点的子结点个数称为该结点的度,树中结点的最大度数称为树的度.
3.度大于0的结点称为分支结点(分终端结点);度为0(没有子女结点)的结点称为叶子结点(终端结点).
4.结点的深度、高度和层次
结点的层次是从树根开始定义,根的结点为第1层(有些教材中将根结点定义为0层),它的子结点为第2层,以此类推.
结点的深度是从根结点开始自顶向下逐层累加的.
结点的高度是从叶结点开始自底向上逐层累加的.
树的高度(又称为深度)是树中结点最大的层数.
5.有序树和无序树:树中结点的子树从左向右是有次序的,不能交换,这样的树叫做有序树,有序树中其子结点按照从左向右是顺序出现是有关联的.反之则称为无序树.
6.路径和路径长度:树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数.
7.森林:森林是
棵互不相交的树的集合.
1.3树的性质
树具有如下最基本的性质:
1)树中的结点数等于所有结点的度数加1.
2)度为m的树中第i层上至多有
个结点(
).
3)高度为h的m叉树至多有
个结点.
4)具有n个结点的m叉树的最小高度为
.
树的一些基本的计算方式:
①总结点数量
;
②总分支数量
;
③总结点数量=总分支数+1;
这样通过三个等式可以得到叶子结点的个数为
这里告一段落，树的定义就是这些了，在后续的图文中将会继续讲述树的一些性质和定义方法。那么，二叉树是树当中的一种特殊的结构，二叉树又有什么样的性质呢？
2.二叉树的概念
2.1二叉树的定义及其主要特性
二叉树是n个结点的有限集合:
①或者为空二叉树,即n=0;
②或者是由一个根结点和两个互不相交的倍称为根的左子树和右子树组成.左子树和右子树又是一棵二叉树.
二叉树是一种有序树,与度为2的树是不一样的.区别如下所示:
①度为2的树至少有3个结点,而二叉树是可以为空的;
②度为2的有序树的孩子结点的左右次序是相对于另外一个结点而言的.二叉树的结点次序不是相对于另外一个结点而言,而是确定的.
几种特殊的二叉树:
1)满二叉树:一棵高度为h并含有
个结点的二叉树称为满二叉树,即树中的每一层都含有最多的结点.满二叉树的叶子结点都几种在二叉树的最下一层,并且除了叶子结点之外的每个结点的度数均为2.
特别地,如果对满二叉树按照层序进行编号,约定编号从根结点(根结点编号为1)起,自上而下,自左向右.这样每个结点结点对应一个编号,对编号为i的结点,如果有双亲,其双亲为
,如果有左孩子,那么左孩子的结点编号为
,右孩子的结点编号为
.
2)完全二叉树:设一个高度为h,有n个结点的二叉树,当且仅当每一个结点都与高度为h的满二叉树中编号为
的结点一一对应的时候,称为完全二叉树.这样的二叉树有以下的一些基本的特点:
①若
,则结点i是分支结点,否则为叶子结点;
②叶子结点只可能在层次最大的两层上出现.对于最大层次中的叶子结点,都一次排列在该层最左边的位置上;
③如果有度为1的结点,只可能有一个,并且该结点只有右孩子或者左孩子;
④按照层次顺序编号之后,一旦出现某结点(编号为i)为叶子结点或只有左孩子,则编号大于i的结点均为叶子结点;
⑤若n为奇数,则每个分支结点都有左子女和右子女;若n为偶数,则编号最大的分支点(编号为n/2)只有左子女,没有右子女,其余分支结点左、右子女都有.
3)排序二叉树:一棵二叉树或者是空二叉树,或者是具有如下性质的二叉树:左子树上所有结点的关键字均小于根结点的关键字;右子树上的所有结点的关键字均大于根结点的关键字.左子树和右子树又各是一棵排序二叉树.
4)平衡二叉树:树上任一结点的左子树和右子树的深度之差不超过1的排序二叉树.
二叉树的性质:
1)非空二叉树上叶子结点树等于度为2的结点数加1,即
;
2)非空二叉树上第K层上至多有
个结点
;
3)高度为H的二叉树至多有
个结点;
4)对应二叉树按照从上到下、从左到右的顺序依次编号$1,2,\dots,N$,则有以下的关系:
①当
时候,结点i的双亲结点编号为
,即当i为偶数的时候,其双亲结点的编号为i/2,它是双亲的左孩子;当i为奇数的时候,其双亲结点的编号为(i-1)/2,它是双亲的右孩子;
②当
的时候,结点i的左孩子编号为2i,否则没有左孩子;
③当
的时候,结点i的右孩子编号为2i+1，否则没有右孩子;
③结点i所在的层次为
;
5)具有$N$个$N0$结点的完全二叉树的高度为
或者为
.
2.2二叉树的存储结构
二叉树有两种存储方式:顺序存储的方式和链式存储的方式:
顺序存储方式
将完全二叉树上编号为i的结点元素存储在某一个下标为i-1的分量中,然后通过一些方法确定结点在逻辑上的父子和兄弟关系.
完全二叉树和满二叉树采用顺序存储的方式比较合适,树中结点的序号可以唯一地反映出结点之间的逻辑关系,这样既能最大可能地节省存储空间,又可以利用数组元素下标值确定结点在二叉树中的位置,以及结点之间的关系.
对于一般的二叉树,为了能够显示二叉树中结点的逻辑关系,只能是添加一些并不存在的空结点让其每个结点与完全二叉树上的结点相对照,再存储到一维数组的相应分量中.在最坏的情况下,一个高度为H并且只有H个结点的单支树却需要占据接近
个存储单元.
链式存储方式
一般的二叉树通常采用链式存储的方式存储.链式结构是指用一个链表来存储一棵二叉树,二叉树中的每一个结点用链表的一个链结点来存储.在二叉树中,结点结构通常包括若干数据域以及若干个指针域.二叉链表至少包含有3个域:数据域data、左指针leftchild和右指针rightchild.
笔者这里使用C++类表示复杂结构的结点结构:
#ifndefBITREENODE_H#defineBITREENODE_H//二叉树的结点定义方法templatetypenameElementTypeclassBiNode{private:BiNodeElementType*left;BiNodeElementType*right;ElementTypedata;public:BiNode(){this-left=NULL;this-right=NULL;}BiNode(ElementTypedata){this-left=NULL;this-right=NULL;this-data=data;}BiNode(ElementTypedata,BiNodeElementType*left,BiNodeElementType*right){this-data=data;this-left=left;this-right=right;}voidSetLeft(BiNodeElementType*left){this-left=left;}voidSetRight(BiNodeElementType*right){this-right=right;}voidSetData(ElementTypedata){this-data=data;}ElementTypeGetData(){returnthis-data;}BiNodeElementType*GetLeft(){returnthis-left;}BiNodeElementType*GetRight(){returnthis-right;}~BiNode(){}};#endif//BITREENODE_H
注意:在含有N个结点的二叉链表中含有N+1个空链域.
END
~~~下课铃~~~
这里告一段落，今天的内容就是这么多，那么二叉树以及树在编程过程中又如何表示呢？尽请期待下一期把！预览时标签不可点收录于话题#个上一篇下一篇