1.树的定义
树是n(n>=0)个结点的有限集.n=0时称为空树.在任意一颗非空树种:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,.......Tm,其中每一个集合本身又是一颗树,并且称为根的子数
树的定义还要强调两点
1.n>0时根结点是唯一的,不可能存在多个根结点,就像每个人只有一个妈妈
2.m>0时,子数的个数没有限制,但是它们一定不能相交,跟第一条原因一样
2.结点分类
树的结点包含一个数据元素及若个指向子数的分支.结点拥有的子树称为结点的度.度为0的结点称为叶结点或终端结点(不可进行再分).度不为0的结点称为非终结点或分支结点.除根结点之外,分支结点也称为内部结点,树的度是树内各结点的度的最大值
3.结点间关系
结点的子数的根称为该结点的孩子,相应的,该结点称为孩子的双亲.同一个双亲的孩子之间互称兄弟,结点的祖先是从根到该结点所经分支上的所有结点,反正,以某结点为根的子树中的任一结点都称为该结点的子孙
4.树的其他关系概念
结点的层次是从根开始定义的,根为第一层,根的孩子为第二层.若某结点在第一层,则其子树的根就在1+1层.其双亲在同一层的互为堂兄弟.树中结点的最大层次称为树的深度或高度
森林是m棵互不相交的树的集合.对树中每个结点而言,其子树的集合即为森林
图树的结构关系图,A的两个子树就可以立即为森林
树结构和线性结构的对比:
线性结构:
1.第一个数据结构:无前驱
2.最后一个数据元素:无后继
3.中间元素:一个前驱一个后继
树结构
1.根结点:无双亲,唯一
2.叶结点:无孩子,可以多个
3.中间结点:一个双亲多个孩子
5.树的抽象数据类型
ADT 树
Data:
树是由一个根结点和若干棵子数构成.树中结点具有相同数据类型及层次关系
Operation:
InitTree (*T):构成空树T
DestroyTree(*T):销毁树T
CreateTree(*T,definition):按definition中给出的树的定义来构造树
ClearTree(*T):若树T存在,则将树T请为空树
TreeEmpty(T):若T为空树,返回true,否则返回false
TreeDepth(T):返回T的深度
Root(T):返回T的根结点
Value(T,cur_e):cur_e是树T中一个结点,返回此结点的值
Assign(T,cur_e,value):给树T的结点cur_e赋值为value
Parent(T,cur_e):若cur_e是树T的非根结点,返回它的双亲,否则返回空
LeftChild(T,cur_e):若cur_e是树T的非叶节点,则返回它的最左孩子,否则返回空
RightSibling(T,cur_e):若cur_e有右兄弟,则返回他的右兄弟,否则返回空
InsertChild(*T,*p,i,c):其中p指向树T的某个结点,T为所指结点p的度加上1,非空树c与T不相交,操作结果为插入c为树T中p所指结点的第i棵子树
DeleteChile(*T,*p,i):其中p指向树T的某个结点,i为所指结点p的度,操作结果为删除T中p所指结点的第i棵子树
endADT
6.树的存储结构
6.1双亲表示法
除了根结点之外,其余每个结点,它不一定有孩子,但是一定**有且仅有一个**双亲
我们假设以一组连续空间存储树的特点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置,也就是说,每个结点除了知道自己是谁外,还知道他的双亲在哪里
结点结构定义代码
//树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100
typedef int TElemType; //树结点的数据类型,目前暂定义为整型
typedef struct PTNode //结点结构
{
TElemType data; //结点数据
int parent; //双亲位置
}PTNode;
typedef struct //树结构
{
PTNode nodes[MAX_TREE-SIZE]; //结点数组
int r,n; //根的位置和结点树
}PTree;
由于根结点是没有双亲的,所有我们约定根结点的位置域设置为-1,这就意味着我们所有的结点都存在他的双亲结点
我们可以根据结点的parent指针很容易找到它的双亲结点,所有时间复杂度为O(1),知道parent为-1,表示找到了树结点的根.可如果我们要知道结点的孩子是什么,就必须遍历整个结构才行
我们增加一个结点最左边孩子的域,不妨叫它长子域,这样就可以很容易得到结点的孩子,如果没有孩子的结点,这个长子域就这种为-1
对于0个或1个孩子结点来说,这样的结构是解决了要找结点孩子的问题了.甚至有2个孩子,知道长子是谁,另外一个当然就是次子
另外一个场景,我们很关注各兄弟之间的关系,双亲表示法无法体现这样的关系,我们可以增加一个右兄弟域来体现兄弟关系,也就是说,每一个结点如果它存在右兄弟,则记录下右兄弟的下标,同样的,如果右兄弟不存在,则赋值为-1
但如果结点的孩子比较多,超过2个.我们又关注结点的双亲,又关注结点的孩子,还关注结点的兄弟,而是对时间遍历要求比较高,那么我们还可以把此结构扩展为双亲域,长子域还有右兄弟域.
存储结构的设计是一个非常灵活的过程,一个存储结构设计是否合理,取决于基于该存储结构的运送是否合适,是否方便,时间复杂度好不好等,
6.2孩子表示法
由于树中每个结点可能有多棵子树,可以考虑多重链表,即每个指针指向一棵子数的根结点,我们把这种方法叫多重链表表示法.不过,树的每个结点的度,也就是它的孩子个数是不同的
方案一:
一种是指针域的个数就等于树的度
这种方法对于树中各结点的度相差很大时,显然很浪费空间,因为有很多的结点,他的指针域都是空的.不过如过树的各结点度相差很小时,那就意味着开辟空间被充分利用了,这是缺点变优点
方案二:按需分配空间
每个结点指针域的个数等于该结点的度,我们专门取一个位置来储存结点指针域的个数
克服了浪费空间的缺点,对空间利用率提高,但是由于各个结点的链表是不相同的结构,加上要维护结点的度的数值,在运算上会带来时间上的损耗
孩子表示法:把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此链表为空.然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中
为此设置了两种结点结构:一个是孩子链表的孩子结点
另一个是表头数组的表头结点
这样的结构对于我们要查找某个结点的某个孩子,或者找某结点的兄弟,只需要查找这个结点的孩子单链表即可.但是要在知道某结点的双亲是谁,比较麻烦,需要遍历整棵树才行.这样我们就需要另一种表示方法,双亲孩子表示法
6.3孩子兄弟表示法
我们从树结点的兄弟的角度来考虑,对于树的层次结构开始,只研究结点的兄弟是不行的,任意一棵树,它的结点的第一个孩子
如果存在就是唯一的,它的右兄弟如果存在也是唯一的,因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的兄弟
6.4二叉树定义
二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的,分别称为根结点的左子数和右子数
6.5.1二叉树特点
二叉树的特点:
1.每个结点最多有两颗子树,所以二叉树不存在度大于2的结点
2.左子树和右子树是有顺序的,次序不能任意颠倒
3.即使树中某结点只有一颗子树,也要区分左子数和右子数的
二叉树的五种2基本形态
1.空二叉树
2.只有一个根结点
3.根结点只有左子树
4.根结点只有右子树
5.树既有左子树也有右子树
6.5.2特殊二叉树
1.斜树
斜树一定是斜的,所有的结点都只有左子树的二叉树叫左斜树.所有的二叉树只有右子数的二叉树叫右斜树.这两者统称为斜树
斜树有个很明显的特点,就是每一层都只有一个结点,结点的个数跟树的深度相同.
有人会想,这那能叫树,这边就是线性表么?没错,线性表就是特殊的二叉树
6.5.3满二叉树
在一棵二叉树中,如果所有分支结点都存在左子数和右子数,并且所有叶子都在同一层上,这样的二叉树称为满二叉树
单个每个结点都存在左右子数,不能算满二叉树,必须所有的叶子结点都在同一层上,这样就达到了整棵树的平衡.
满二叉树的特点:
1.叶子只能出现在最下一层,出现在其他层就不可能达到平衡
2.非叶子结点的度一定是2,缺胳膊短腿就达不到圆满了
3,在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多
6.5.4完全二叉树
对一棵具有n个结点的二叉树按层序编号,如果编号为i(1<= i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树树完全二叉树
"完全"和"满"是有差异的,完全是两个字,而满是一个字的,而且笔画数也不相同的
好了,不扯了,"完全"和"满"确实是有差异的,满二叉树一定是完全二叉树,而完全二叉树不一定是满二叉树
完全二叉树的特点:
1.叶子结点只能出现在最下两层
2.最下层的叶子一定集中在左部连续位置
3.倒数两层,若有叶子结点,一定都在右部连续位置
4.若结点度为1,则该结点只有左孩子,即不存在只有右子树的情况
5.同样结点树的二叉树,完全二叉树的深度最小
6.6二叉树的性质
性质1:在二叉树的第i层上至多有2^i-1个结点(i>=1)
性质2:深度为k的二叉树至多有2^k-1个结点(k>1)
性质3:对任何一棵二叉树T,如果其终端结点数(叶子结点数)为n0,度为2的结点数为n2,则n0 = n2+1
一棵二叉树中,除了叶子结点外,剩下的就是度为1或2的结点树了,设n1为度为1的结点数.则树的总结点数n = n0+n1+n2
性质4:具有n个结点的完全二叉树的深度为[log2N]+1的结点按层序编号(从第1层到第[log2N]+1层,每层从左到右),对任一结点i(1<=<=n)有:
1.如果i= 1,则结点i是二叉树的根,无双亲;如果i>1,则双亲是结点[i/2]
2.如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i
3.如果2i+1>n,则结点i无右孩子,否则其右孩子是结点2i+1
对于第一条,i= 1时就是根结点.i> 1,比如结点7,其双亲结点为7/2 = 3,结点9的双亲结点为9/2 = 4
第二条:比如结点6,26>10,超过结点总数.所有该结点无左孩子,是叶子结点.同样,结点5,25 =10,所有它的左孩子是结点10
第三条:结点5,25 +1 =11 > 10,所以它无右孩子,而结点3,23+1=7<10,所有右孩子是结点7
6.7二叉树的存储结构
6.7.1二叉树顺序存储结构
二叉树的顺序结构是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系,比如双亲与孩子的关系,左右兄弟的关系
先举个特殊的例子,完全二叉树的存储
将这棵二叉树存入到数组中,相应的下标对应其同样的位置
完全二叉树存入到数组中,相应的下标对应其同样的位置,而对于一般的二叉树,尽管层序编号不能反映逻辑关系,但是可以将其按完全二叉树
编号,只不过,把不存在的结点设置为"^"
考虑一种极端的情况,一棵深度为k的右斜树,它只有k个结点,却需要分哦2^k-1个存储单元,会造成对空间的极度浪费,所有,顺序结构一般只用于完全二叉树
6.7.2二叉链表
顺序存储适用性不强,我们就要考虑链式存储结构.二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域,我们称这样的链表为二叉链表
图完全二叉树的存储图片以二叉链表表示:
6.8遍历二叉树
二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得某个结点被访问一次且仅被访问一次
6.8.1二叉树遍历方法
1.前序遍历
若二叉树为空,则空操作返回,否则
1.先访问根结点
2.前序遍历左子树,
3.前序遍历右子树.
遍历的顺序为:ABDGHCEIF
2.中序遍历
若树为空,则空操作返回
1.从根结点开始(注意不是先访问根结点)
2.中序遍历根结点的左子树,然后是访问根结点
3.中序遍历右子树
,遍历的顺序为GDHBAEICF
3.后序遍历
若树为空,则空操作返回
1.从左到右先叶子后结点的方式遍历访问左右子树
2.最后是访问根结点.
遍历的顺序为:GHDBIEFCA
4.层次遍历
若树为空,则空操作返回
1.从树的第一层,也就是根结点开始访问
2.从上而下逐层遍历
3.在同一层中,按从左到右的顺序对结点逐个访问
6.8.2前序遍历算法
二叉树的定义是用递归的方式,所以实现遍历算法也可以采用递归
//二叉树的前序遍历递归算法
void PreOrderTraverse(BITree T){
if (T == NULL)
return;
printf("%c",T->data);//显示结点数据,可以更改为其他对结点操作
PreOrderTraverse(T->lchild);//在先前序 遍历左子树
PreOrderTraverse(T->rchild);//最后前序遍历右子树
}
6.8.3中序遍历算法
//中序遍历递归算法
void InOrderTraverse(BITree T){
if (T == NULL)
return;
InOrderTraverse(T->lchild);//中序遍历左子树
printf("%c",T->data);//显示结点数据,可以更改为其他对结点操作
InOrderTraverse(T->rchild);//最后中序遍历右子树
}
6.8.4后序遍历算法
void PostOrderTraverse(BITree T){
if (T == NULL)
return;
PostOrderTraverse(T->lchild);//后序遍历左子树
PostOrderTraverse(T->rchild);//再后序遍历右子树
printf("%c",T->data);//显示结点数据,可以更改为其他对结点操作
}
6.8.5
中序遍历:
1.A有左孩子B,从B接着往下遍历,C无左孩子,所以打印其结点C
2.然后遍历C的右孩子D,D有左孩子,接着遍历F,F无左右孩子,所以 打印其结点F
3.返回F的上一个结点D,因为其左孩子已经遍历过了,可以暂时当其不存在,所有打印结点D
4.结点D的左孩子已经遍历完成,,所有遍历其右孩子E,E无左右结点,所以打印其结点E
5.返回其双亲结点D,D以打印完成,返回其双亲结点C,C也打印完成,返回其双亲结点B,B的左孩子已经遍历过了,所以打印其结点B
6.遍历其B的右孩子G,G无左孩子,所有打印G
7.遍历G的下一个结点H,H有左孩子I,I有左孩子J,但J无左孩子,所有打印其结点J
8.结点I的左孩子已经打印完成,所有打印其结点I
9.遍历I的右孩子K,K有左孩子L,L无左孩子,打印其结点L
10.遍历L的右孩子M,M无左右孩子,打印M
11.返回结点L,L以打印完成,返回结点K,K无右孩子,打印其结点K
12.返回K的双亲结点I,返回H,H无右孩子,打印其结点H
13.返回结点G,返回结点B,返回结点A,打印其结点A
中序的顺序:CFDEBGJILMKHA
后序遍历:
1.A有左孩子B,B有左孩子C,C无左孩子,但有右孩子D,D有左孩子F,F无左右孩子,所有打印结点F
2.返回结点D,D有右孩子E,E无左右孩子,打印结点E
3.返回结点D,D的左右孩子都已经打印完成,可以看成D无左右孩子, 所有打印结点D
4.返回D的双亲结点C,C无左孩子,其右孩子已经打印完成,所有打印结点C
5.返回结点C的双亲结点B,B有右孩子G,G无左孩子,所以遍历其右孩子H,H有左孩子I,I有左孩子J,J无左右孩子,所以打印结点J
6.返回J的双亲结点I,I有右孩子K,K有左孩子L,L有右孩子M,M无左右孩子,所有打印结点M
7.返回结点L,并打印结点L
8.返回结点K,并打印结点K
9.打印结点I
10.打印结点H
11.打印结点G
12.打印结点B
13.打印结点A
后序遍历:FEDCJMLKIHGBA
