树和二叉树的概念

笑起来很干净

文章目次

媒介

陆连续绝的,我们曾经教完了序次表,链表,栈战行列等线性的数据构造,现在天专次要引见的便是树形的数据构造,战线性数据构造一样,我们先引见甚么是树形构造和树的特性

树的观点

树是一种非线性的数据构造，它是由n（n>=0）个有限结面构成一个具有层次干系的汇合。把它叫做树是果
为它看起去像一棵倒挂的树，也便是道它是根晨上，而叶晨下的
以下图所示:

上面是引见树的一些经常使用术语观点,专主先上一张图,便利各人辨别各个术语

根结面:出有单亲节面的结面,好比结面A.
孩子节面或子节面：一个节面露有的子树的根节面称为该节面的子节面； 如B是A的孩子节面
单亲结面若一个节面露有子节面，则那个节面称为其子节面的女节面,如A是B的女节面
节面的度:一个节面露有的子树的个数称为该节面的度； 如A的度为6
叶节面或末端节面度为0的节面称为叶节面, 如B、C、H、I等节面为叶节面
非末端节面或分收节面度没有为0的节面； 如D、E、F、G等节面为分收节面
兄弟节面具有不异单亲节面的节面互称为兄弟节面； 如I,J是兄弟结面,K,L,M是兄弟结面,H,I没有是兄弟结面
树的度一棵树中，最年夜的节面的度称为树的度； 如树的度为6(由于A的度是一切结面中度最年夜的,成果为6)
节面的层次从根开端界说起，根为第1层，根的子节面为第2层，以此类推；
树的下度或深度树中节面的最年夜层次； 如上里的树的下度为4(即具有四层)
节面的先人从根到该节面所经分收上的一切节面；如上图：A是一切节面的先人
子孙以某节面为根的子树中任一节面皆称为该节面的子孙。如上图：一切节面皆是A的子孙

树的暗示

前里俭朴引见了树的观点,可是树究竟结果是逻辑构造,我们念要完成它,该怎样做呢?最经常使用的是借助链表,用孩子兄弟暗示法停止归纳树构造.以下图:

结面的代码构建以下:

typedef int DataType;
typedef struct node
{
struct node* child; //指背左孩子结面
struct node* brother; //挨个指背兄弟结面
DataType data; //存储当前结面数据
}node;

复造代码

树构造正在实践中的使用

树构造正在实践糊口中使用最多的便是文件构造,以下表示图:

两叉树的观点

契合树的观点,但特性是树的度最年夜只能为2,也便是道每一个结面的子节面最多只能有两个.

两叉树特性:

每一个结面最多有两棵子树，即两叉树没有存正在度年夜于2的结面。
两叉树的子树有阁下之分，其子树的次第不克不及倒置。

特别的两叉树

谦两叉树

**观点:**每层的结面皆抵达最年夜值,且第n层的结面数量契合公式2^(n-1),层数是从1开端数

完整两叉树

观点: 关于层数(n>=2)的树,其n-1层契合谦两叉树,第n层结面数量必需从左背左皆契合222...1特征,即有且只要1个单结面,地位处于开端,该单结面必然是左孩子结面.

两叉树性子

若划定根节面的层数为1，则一棵非空两叉树的第n层上最多有2^(n-1) 个结面.
若划定根节面的层数为1，则深度为h的两叉树的最年夜结面数是2^h- 1(该公式由等比数列乞降获得).
若划定根节面的层数为1，具有n个结面的谦两叉树的深度h=Log2(n+1)
尽情一颗两叉树,假定度为0的结面数量为n0,度为2的结面数量为n1,则合意 n0= n1+1;

两叉树的存储构造

序次存储

即用数组停止存储,正在逻辑构造上是两叉树,正在物理构造上是一个数组,用数组的下标停止暗示每一个结面,从0开端,以下图:

序次存储的特性:

只合用两叉树,由于两叉树请求即便空结面也存储,以是空间没有会华侈,可是其他树构造便会形成严峻空间华侈

序次存储两叉树普通合用于堆排序

链式存储

链式存储有两种:

两叉链:具有三个域,别离是阁下指针域战数据域,阁下指针域别离指背左孩子战左孩子
三叉链:具有四个域,别离是阁下指针域和单亲域战数据域,阁下指针域同上,单亲域指背单亲节面.

表示图以下:

两叉链结面构建代码:

typedef int DataType;
typedef struct node
{
struct node* leftchild;
struct node* rightchild;
Datatype data;
};

复造代码

三叉链结面构建代码:

typedef int DataType;
typedef struct node
{
struct node* leftchild;
struct node* rightchild;
Datatype data;
};

复造代码

熟悉树构造的习题锻炼

1. 某两叉树共有 399 个结面，此中有 199 个度为 2 的结面，则该两叉树中的叶子结面数为（）
A 没有存正在如许的两叉树
B 200
C 198
D 199
2.以下数据构造中，没有合适接纳挨次存储构造的是（）
A 非完整两叉树
B 堆
C 行列
D 栈
3.正在具有 2n 个结面的完整两叉树中，叶子结面个数为（）
A n
B n+1
C n-1
D n/2
4.一棵完整两叉树的节面数位为531个，那末那棵树的下度为（）
A 11
B 10
C 8
D 12
5.一个具有767个节面的完整两叉树，其叶子节面个数为（）
A 383
B 384
C 385
D 386

复造代码

谜底:

B,缘故原由两叉树中 叶子结面数量 = 度为2结面数量 + 1

C,由于序次构造的长处是 尾删尾插便利,可是行列用的更多的是 头插头删

A,一颗谦两叉树的结面数量是2n-1,如今一切结面是2n,相等于正在谦两叉树后增长了一个结面.以是为n

B,2^9的成果是512,是一个谦两叉树,531比512多19个结面,以是下度是10.

B,前9层是谦两叉树结面有512,盈余255叶节面,可是那255个结面有254个结面有单亲,即有127个度为2结面,然后前8层的结面皆是度为2结面,2^8-1便是255,以是度为2的结面为255+127=382,那末剩下的结面为767-382=385(包罗叶节面战一个度为1结面),以是谜底是384

免责声明：假如进犯了您的权益，请联络站少，我们会实时删除侵权内乱容，感谢协作！

树和二叉树的概念

浏览过的版块