树型结构是一类重要的非线性数据结构。以树与二叉树最常用,直观上树是分支关系定义的层次结构。并且在计算机领域也有广泛应用,比如编译程序和数据库系统。
树的定义以及基本用语
定义
树是 n(n>=0) 的有限集。在任意一棵树非空树中
- 有且仅有一个特定根(root)的结点
- 当 n>1 时,其余结点可分为 m(m>0) 个互不相交的有限集,其每一个结合本身又是一棵树,我们称为子树
有点抽象,我用表再尝试叙述一下
根结点 root | 1 | ||
---|---|---|---|
表一 | 1.1(2) | 1.2(3) | 1.3(4) |
1.11(5) | 1.12(6) | 1.31(7) |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|
1 | 1.1 | 1.2 | 1.3 | 1.11 | 1.12 | 1.31 |
左边是树的层次表示,1 表示根结点,1.1 表示其父结点为 1;1.11 表示其父节点为 1.1;这样就表示一个树的层次结构(可以画出树状图更为直观)。
右边是树的一维数组表示,也是计算机存储树的一种方式。在猫猫的理解里,数据的存储无非是连续的存储或者链式存储。所以树是一种逻辑上的结构,我们通过赋予数据一些联系来实现我们想要的功能。
基本术语
- 结点:一个数据元素及其若干指向其子树的分支。
- 结点的度,树的度:结点所拥有的子树的棵树称为结点的度;树中结点度最大值称为树的度。
以表一为例,结点 1(根结点)的度为 3(其子树为 1.1,1.2,1.3);同时这个树的结点也是 3。- 叶子结点,非叶子结点:度为 0,称叶子结点或终端结点;反之为非...或分支结点;除了根节点外,分支结点又称为内部结点。
以表一为例,结点 1.11,1.12 是叶子结点(终端结点),1.1 为非叶子结点(分支结点,有分支,非根结点也是内部结点)。- 孩子兄弟和双亲结点:
一个结点的子树的根称为该结点的孩子结点或子结点;响应的该结点是其孩子结点的双亲结点或父结点。同一双亲结点所有子结点互称为兄弟结点。- 层次堂兄弟结点:
规定树中根节点的层次为 1,其余结点的层次等于其双亲结点的层次加一。若某结点再第 n 层,则其子结点再第 n+1 层,双亲结点再同一层上的所有结点互称为堂兄弟结点。- 结点的层次路径,祖先和子孙:
从根结点开始,到达某结点 p 所经过的所有结点成为结点 p 的层次路径(有且只有一条)。
结点 p 的层次路径上的所有结点(p 除外)称为 p 的祖先。
以某一结点为根的子树中的任意结点称为该结点的子孙结点。- 树的深度:树中结点的最大层次值,又称为树的高,表一的树的深度为 3。
- 有序树和无序树:对于一棵树,若其中每一个结点的子树(若有)具有一定的次序,则该树称为有序树,反之无序树。(二叉树就是有序树,分左右)
- 补充-高度的另一定义:
- 深度:层次数,从上往下
- 高度:规定叶子结点的高度为 1,其双亲结点的高度等于它的高度加一,从下往上。
- 树的高度:等于根结点的高度,即根结点所有子女高度的最大值加一。
- 结点的深度和结点的高度是不同的。
- 树的高度和深度是相等的。
- 森林:是 m(m 大于 0)棵树互不相交的树的集合。若将一棵树的根结点删除,剩余的子树就构成了森林。
- 树的表示形式(图示请自行百度)
- 倒悬树。最常用的表现形式(树状图)
- 嵌套集合。是一些集合的集体,对任何两个集合,或者不相交,或者一个集合包含另一个集合。(类似我们离散中的集合图状表示)
- 广义表形式((A(b,c),D(e,f)))
- 凹入法表示形式(类似数的编目)
树的概念与术语有点多,这也侧面说明其重要性与复杂性。接下来根据这些概念思考
- 所有结点的度之和是多少?
以表一为例,根结点 1 度是 3,1.1 的度是 2,1.2 没有度,1.3 度为 1。其度之和为 3+2+1=6,其结点有 7 个。那么结点为 n 个呢? - 度为 m 的数中第 i 层至多有多少个结点(i>=1)?
- 高度为 h 的 m 叉树至多有多少结点?
- 具有 n 个结点的 m 叉树的最小高度?
好吧猫猫无法将详细的证明过程写出来,这些问题就是树的性质
树的性质
- 树中的结点数等于所有结点的度树之和加 1。
- 度为 m 的树中第 i 层上至多有 m^{i-1} 个结点(i>=1)。
- 高度为 h 的 m 叉树至多有 (m^h-1)/(m-1) 个结点。
- 具有 n 个结点的 m 叉树的最小高度为 [log_m(n(m-1)+1)]。
二叉树的概念以及实现
二叉树的概念
定义
二叉树(binary tree)是另一种树型结构,其特点是每个结点至多有 2 个子树(即二叉树的度不能大于 2),并且二叉树的子树有左右之分,其次序不能任意颠倒。
这里我用表来表示一个简单的二叉树
表二 | 1 | |
---|---|---|
1.1 | 1.2 | |
1.11,1.12 | 1.21,1.22 |
由二叉树的定义可知,有五种基本形式是满足二叉树的
- 空树,空树是树,也是二叉树。
- 只有根结点的树。
- 以表二为例,若一棵树只有结点 1 和 1.1,那么这是右子树为空的二叉树。
- 以表二为例,若一棵树只有结点 1 和 1.2,那么这是左子树为空的二叉树。
- 以表二为例,若一棵树只有结点 1,1.1 和 1.2,那么是左右子树均有的二叉树。
除此之外,二叉树也有满二叉树和完全二叉树的说法。
- 满二叉树:一棵深度为 k 且有 $2^{k}-1$ 个结点(最多结点)的二叉树
- 完全二叉树:若深度为 k 由 n 个结点的二叉树,当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1~n 一一对应,则为完全二叉树。(完全二叉树就是其结点序号对应满二叉树是一样的。)
二叉树的性质
非空二叉树中第 i 层至多有 2^{i-1} 个结点(i>=1)。用数学归纳法证明。
假设我们有一个 i(大于 1) 层的二叉树,那么在这层上至多有 $2^{(i-1)}$。深度为 k 的二叉树最多有 2^k-1 个结点(k 大于等于 1)
由性质一可知,第 i 层的结点数至多有 2^{(i-1)}。
所以总的结点数:$2^0+2^1+……2^{k-1}=2^k-1$。对任何一棵二叉树,其叶子结点的个数为 n_0,度为 2 的结点数为 n_2,则 n_0=n_2+1
理解:
假设一个二叉树叶子结点数为 n_0(度为 0),度为 1 的结点数为 n_1,度为 2 的结点数为 n_2;
所以我们能推出结点总数:N=n_0+n_1+n_2;二叉树有分支数 B(比如根结点后面跟的线就可以看成分支,实际上就是结点的度);
分支数 B 的和等于度之和(不局限与二叉树);
由于树的根结点是没有前驱的,所以一个二叉树的结点总数与分支数存在关系 B=N-1;
由此可以推出 n_0+n_1+n_2-1=2n_2+n_1;所以得到结论 n_0=n_2+1。n 个结点的完全二叉树的深度为 log2^n+1(向下取整)
假设完全二叉树的深度为 k,则根据性质 2 有 $2^{k-1}-1<n<=2^k-1 或 2^{k-1}<=n<2^k$,取对数就可以得到性质 4。
log_{2^{n+1}} 也对对一棵有 n 个结点的完全二叉树按层序自左到右进行编号,则对于编号为 i(1<=i<=n)的结点:
- 若 i 等于 1:则是二叉树的根。若 i》1,则其双亲结点编号是 i。
- 若 2i》n:则结点 i 是叶子结点;若不大于,则 i 结点的孩子结点编号为 2i。
- 若 2i+1》n:则结点 i 无右孩子;否则其右孩子编号为 2i+1
证明是数学归纳法。
理解二叉树的性质对于我们如何实现有指导意义。
二叉树的实现
ps:因为二叉树的顺序没有链式常用,所以我们不做测试,而链式有时间补(鸽)
顺序二叉树结构
#include <stdio.h>
#include <math.h>
#include "Status.c"
#include "Scanf.c"
#define maxtreesize 100
typedef char telemtypesq;//假设顺序二叉树元素均为字符
typedef telemtypesq sqbitree[maxtreesize];//0号单元存储根结点
typedef{
int level;//结点所在层
int order;//结点再本层序号
}position;
初始化,清空与销毁
void initbitreesq(sqbitree T){
int i;
for(i=0;i<maxtreesize;i++) T[i]='\0';//这里用空字符填充
};
void clearbitreesq(sqbitree T){
int i;
for(i=0;i<maxtreesize;i++) T[i]='\0';//这里用空字符填充
};
void destroybitreesq(sqbitree T){
//无,顺序二叉树销毁操作无
};
其函数内代码都是一样的,因为我们初始化一个顺序二叉树在计算机里是用数组,并且赋值都是字符型的空字符,而清空数组元素恰好是对数组数据清空。
判空
Status bitreeemptysq(sqbitree T){
return T[0]=='\0' ? TRUE : FALSE;
};
通过 T[0]就可以知道二叉树是否为空
创建
Status createbitreesq(FILE *fp,sqbitree T){
char ch;
int i=0;
while(Scanf(fp,"%c",&ch)==1&&ch!='\n'){
if(ch=='^') T[i++]='\0';
else T[i++]=ch;
}
return OK;
};//按层序序列构造二叉树
Status createbitreepresq(FILE *fp,sqbitree T,int i){
char ch;
Scanf(fp,"%c",&ch);
if(ch=='^') T[i]='\0';
else{
T[i]=ch;
createbitreepresq(fp,T,2*i+1);
createbitreepresq(fp,T,2*i+2);
}
};//按先序序列构造二叉树
层序序列构造:这里是用 scanf 函数来扫描文本填充到数组(二叉树)里面
先序序列构造:扫描文本后将文本中的 ^
替换为空字符(空格),因为在 c 里面读取到空字符会停止扫描。
树的长度,深度和根结点
int bitreelensq(sqbitree T){
int len;
for(len=maxtreesize;len-1>=0;lem--){
if(T[len-1]!='\0') break;
}
return len;
};
int bitreedepsq(sqbitree T){
int level=0;
while((int)pow(2.level)-1<bitreelensq(T)) level++;
return level;
};
Status rootsq(sqbitree T,telemtypesq *e){
if(bitreeemptysq(T)) return ERROR;
*e=T[1];
return OK;
};
树的长度并不是树的规模,对树进行遍历,若对应下标的值不为空,则跳出循环输出长度值。
树的深度:根据二叉树的性质(深度为 k 的二叉树最多有 $2^k-1$ 个结点(k 大于等于 1)),我们可以通过比较结点数来得到对应的深度。
树的根结点:判断树是否为空,然后直接输出根结点。
返回结点值
telemtypesq valuesq(sqbitree T,position s){
int i=(int)pow(2,s.level-1)+s.order-2;
return T[i];
};//返回树中某位置的结点值
传入树 T 与结点 S,把其树位次信息转为数组信息。,然后返回对应值就可以了。
为某位置结点赋值
Status assignsq(sqbitree T,position s,telemtypesq value){
int i=(int)pow(2,s.level-1)+s.order-2;
if(value=='\0' && (T[2*i+1]!='\0' ||T(2*i+2)!='\0'))
return ERROR;
else if(value!='\0' && T[(i+1)/2-1]=='\0')
return ERROR;
else
T[i]=value;
return OK;
};//为树中某位置的结点赋值
传入二叉树 T 和结点 s,用 value 赋值。
首先转为数组序列表示,然后判断,若该结点的子树不为空,那么不能替换;若替换值不是空,且其父结点不存在,则不能替换(因为替换后一个变成一个没有父结点的结点)。
判断之后进行替换。
输出对应结点数值的父母结点,兄弟结点,孩子结点
telemtypesq parentsq(sqbitree T,telemtypesq e){
int i;
if(T[0]!='\0'){
for(i=0;i<maxtreesize;i++){
if(T[i]==e) return T[(i+1/2-1)];
}
}
return '\0';
};
telemtypesq lchildsq(sqbitree T,telemtypesq e){
int i;
if(T[0]=='\0') return '\0';
for(i=0;i<maxtreesize;i++){
if(T[i]==e) return T[2*i+1];
}
return '\0';
};
telemtypesq rchildsq(sqbitree T,telemtypesq e){
int i;
if(T[0]=='\0') return '\0';
for(i=0;i<maxtreesize;i++){
if(T[i]==e) return T[2*i+1];
}
return '\0';
};
telemtypesq lsibsq(sqbitree T,telemtypesq e){
int i;
if(T[0]=='\0') return '\0';
for(i=0;i<maxtreesize;i++){
if(i%2==0 && T[i]==e) return T[i-1];
}
return '\0';
};
telemtypesq rsibsq(sqbitree T,telemtypesq e){
int i;
if(T[0]=='\0') return '\0';
for(i=0;i<maxtreesize;i++){
if(i%2==0 && T[i]==e) return T[i+1];
}
return '\0';
};
算法思路都是先遍历树,找到对应结点的下标值,然后根据二叉树的特性去输出。
遍历二叉树
void levelordertrasq(sqbitree T,void(Visit)(telemtypesq),int i){
int i;
int len=bitreelensq(T);
for(i=0;i<len;i++){
if(T[i]!='\0') Visit(T[i]);
}
};
void preordertrasq(sqbitree T,void(Visit)(telemtypesq),int i){
if(T[i]!=0){
Visit(T[i]);
preordertrasq(T,Visit,2*i+1);
preordertrasq(T,Visit,2*i+2);
}
};
void inordertrasq(sqbitree T,void(Visit)(telemtypesq),int i){
if(T[i]!=0){
preordertrasq(T,Visit,2*i+1);
Visit(T[i]);
preordertrasq(T,Visit,2*i+2);
}
};
void postordertrasq(sqbitree T,void(Visit)(telemtypesq),int i){
if(T[i]!=0){
preordertrasq(T,Visit,2*i+1);
preordertrasq(T,Visit,2*i+2);
Visit(T[i]);
}
};
遍历二叉树有好几种方法
- 层序遍历:我们通过树的长度去访问树中每一个数据
- 先序遍历:通过根左右的顺序去访问
- 中序遍历:通过左根右的顺序去访问
- 后序遍历:通过左右根的顺序去访问
数据的输出
void printsq(sqbitreesq T){
int i,j,level;
char tmp[maxtreesize][maxtreesize]={};
level=bitreedepsq(T);
for(i=1;i<level;i++)
for(j=1;j<=(int)pow(2,i-1);i++)
tmp[i-1][(int)pow(2,level-1)+(j-1)*(int)pow(2.level-i+1)-1]=T[(int)pow(2,i-1)-1+j-1;
for(i=0;i<level;i++){
for(j=0;j<2*(int)pow(2,level-1)-1;j++){
if(tmp[i][j]!='\0') printf("%c",tmp[i][j]);
else printf(" ");
}
printf("\n");
}
}
传入树 T。函数内设变量存储树的深度,根据深度对应的结点值去填充设置的二位数组 tmp
(其中的数据关系式猫猫不想看了,头大)
其他
其实除了这个简单的顺序二叉树,还有许多其他的不同的结构的二叉树。比如链式存储的二叉树,其实一般用链式二叉树更多,因为可以保证空间不会过多浪费。
还有树,森林的实现,都是坑(鸽)。
树与二叉树的应用
- 二叉查找树:也叫二叉排序树,是根据二叉树的特性进行数据查找的一种算法。
- 平衡二叉树:为了避免树的高度增长,降低二叉排序树的性能,我们要保证左,右子树高度差绝对值不超过 1,将这样的二叉树称为平衡二叉树。
- 哈夫曼树:在许多应用中,树中结点被赋予一个表示某种意义的数值,称为权。从树的根到任意结点的路径长度(经过的边数)与该结点上权值的乘积,称为该结点的带权路径长度。
在含有 n 个带权也结点的二叉树中,其带权路径长度最小的二叉树称为哈夫曼树。
鸽
思考
- 对于任意一棵高度为 5 且 10 个结点的二叉树,若用顺序存储方式,每个结点占据一个存储单元,则其存储单元数量至少是多少?
- 一个具有 1025 个结点的二叉树的高度为多少?
ps: 摸一摸数据结构(目录)
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于