本文所说的“树”,特指“带标号的有限有根有序树”
参考教材:《数据结构》,刘大有
编程语言: C++
目录
一、树
(一)定义
1.树
2.森林
(二)相关概念
1.子树
2.父亲、儿子、兄弟、祖先、后裔
3.叶子结点与非叶子结点
4.层数、深度、高度
(三)树的表示
1.树形表示法
2.其他表示方法
二、二叉树
(一)定义
(二)性质
(三)操作
1.二叉树的存储
2.二叉树的遍历
3.二叉树的创建
一、树
(一)定义
1.树
树是由n(>=0)个节点的组成的具有层次关系的有限集合T。当n=0时,称为空树。
在非空树(n>=1)中,①该有限集合的每个元素被称为节点 ②有一个特别标出的节点被称为根节点,记为root(T) ③其余节点被分成若干不相交的的非空集合 
讯享网,且
又都是树。

有序树
若将树中每个节点的各个子树看成是从左到右有次序的(不能互换),则称该树为有序树
举个例子,对于有序树而言,树1和树2是不同的树。对于无序树而言,树1和树2是相同的。
2.森林
一个森林是0棵或多棵不相交的非空树的集合(并且通常是一个有序的集合)
树与森林的关系
删除一棵树的根,就得到一个森林;给一个森林增加一个根节点,就得到了一棵树
(二)相关概念
以如下的树为例:

1.子树
子树也是树,只不过子树的概念是相对于某一个结点而言的。例如,对于结点A,它有三棵子树:由结点BEI组成的子树、由结点CFG组成的子树、由结点DF组成的子树。而对于结点C,它有两棵子树:子树F、子树G
2.父亲、儿子、兄弟、祖先、后裔
父亲、儿子、兄弟、祖先、后裔说的都是结点与结点之间的关系,其中
父亲 :每一个结点都是它子树的根的父亲。例如,结点A是结点B、C、D的父亲
儿子 :一个结点的子树的根是这个结点的儿子。例如,结点F和G是结点C的儿子
兄弟 :同一个父亲的儿子是兄弟。例如,结点B、C是结点D的兄弟
祖先 :每一个结点都是它子树的所有结点的祖先。例如,结点A是结点B、C、D、E、F、G、H、I的祖先;结点B是结点E、I的祖先
后裔 :对于某一个结点,它所有子树的每一个结点都是它的后裔。例如,结点B、C、D、E、F、G、H、I是结点A的后裔
3.叶子结点与非叶子结点
结点的度(次数)
一个结点的儿子的个数称为该结点的度或次数。例如,结点A的度是3,结点I的度是0
树的度
所有结点的度的最大值称为树的度,度为k的树称为k元树。例如,上面所说的树度为3,是三元树
叶子结点
度为0的结点称为叶子结点或终端结点,即叶子结点的儿子的个数为0。例如,结点F、G、H、I都是叶结点
非叶子结点
叶子结点以外的所有结点称为非叶子结点(或非终端结点、分支结点)
4.层数、深度、高度
还是以这棵树为例:

结点的层数
根的层数为0,其余结点的层数为其父结点的层数加1。例如,A结点的层数为0,C结点的层数1,F结点的层数为2
在其它教材中,一般把根结点的层数定为1
路径
结点序列
(其中
是
的父结点)称为结点
到结点
的路径,路径经过的边数称为路径长度
结点的深度
根到结点的路径长度,称为该结点的深度。例如,B结点的深度为1,C结点的深度为1,E结点的深度为2
树的深度
树的所有结点深度的最大值,称为树的深度。例如,该树的深度为3
结点的高度
结点到叶结点的最长路径的长度,称为该结点的高度。例如,B结点的高度为2,C结点的高度为1,A结点的高度为3
树的高度
根结点的高度,称为树的高度。例如,该树的高度为3
树的高度等于树的深度
如果把根节点的层数设为0,则结点的深度等于其层数
(三)树的表示
1.树形表示法
包括树根在上的表示和树根在下的表示。其中树根在上的表示又称为倒置树,是树最常用的表示方法


2.其他表示方法
嵌套集合表示法


嵌套括号表示法
(A(B(E(I))),C(F,G),D(H))
此外还有凹入表示法等表示方法
二、二叉树
(一)定义
二叉树的递归定义
二叉树是结点的有限集合,它或者是空集,或者由一个根及两棵不相交的称为这个根的左右子树的二叉树组成
辨析 | 二叉树和度为2的树的区别
二叉树是特殊的度为2的树,并且二叉树和度为2的树都是有序树。它们的区别在于当一个结点只有一棵子树时,是否指明该子树是左子树还是右子树
例如,度为2的树认为树1和树2是相同的树;而二叉树认为它们是不同的,树1是只有一棵左子树的二叉树,树2是只有一棵右子树的二叉树
(二)性质
1. 从定义出发,我们可以得知二叉树具有以下性质:
- 每个结点最多有两个儿子
- 每个结点的子树都有左右之分(即便该结点只有一棵子树)
2. 二叉树树第i层至多有
个结点(假设根节点所在层数为0)
3. 高度(深度)为k的二叉树至多有
个结点
4. 设T是由n个结点组成的二叉树,其中叶结点的个数为
,度为2的结点的个数为
,则有
满二叉树
高度为k,具有
个结点的非空二叉树是满二叉树
完全二叉树
一棵包含n个结点高度为k的二叉树T,当按层次顺序编号T的所有结点,对应于一棵高度为k的满二叉树中编号由1至n的那些结点时,T被称为完全二叉树
满二叉树是特殊的完全二叉树
满二叉树的每个非叶结点都有两个子节点,叶结点只出现在最下面一层;
完全二叉树最下面两层结点的度可以小于2,叶结点可以出现在最下面两层
5.对于具有n个结点的完全二叉树,如果按层次顺序给每个结点从0到 n-1编号,则编号为i的结点

(三)操作
1.二叉树的存储
二叉树的存储包括顺序存储和链接存储两种方式
1)顺序存储
所谓顺序存储,其实就是用数组来存储二叉树
一般情况下,数组保存的是二叉树的层次序列。例如,对于下图所示的二叉树:

我们可以使用一个数组T去存储该二叉树(如下图)

char T[10]={'A','B','C','D','E','F','G','H','I','J'};
讯享网
优点
顺序存储的优点是简单、占用空间较小,我们可以通过数组的下标随机访问二叉树的任何一个结点,同时我们可以通过计算找到某一个结点的父结点及左右儿子
例如,对于某个结点T[i]:

缺点
对于完全二叉树,使用顺序存储非常方便;但对于非完全二叉树,如果使用顺序存储的方式,我们需要添加一些虚结点,把非完全二叉树当成完全二叉树来存储。例如:


讯享网char T[10]={'A','B','C','#','E','F','G','#','#','J'};
如果二叉树的结点个数较少,将它转变为完全二叉树又需要添加很多虚结点,这时采用顺序存储的方式将造成极大的空间浪费
因此,只有完全二叉树或者近似完全二叉树,才比较适合顺序存储
2)链接存储
对于顺序存储的方式,由于我们使用数组保存了二叉树的层次序列,自然而然也就保存了二叉树的结构(结点之间的相对位置关系)
二叉链表
如果使用链接存储的方式,我们需要增加两个字段Left、Right来存储结点之间的位置关系,单个结点的结构如下:

struct Node{ Node *Left; Node *Right; char Data; };
其中Left用来保存指向该结点左儿子的指针,Right用来保存指向该结点右儿子的指针

三叉链表
有时为了方便访问结点的父亲,我们会使用三叉链表来存储二叉树,三叉链表结点的结构如下:

其中Parent是指向该结点的父亲的指针
2.二叉树的遍历
在学习创建二叉树之前,我们不妨先学习二叉树的遍历,因为二叉树的创建可以借助二叉树的遍历算法完成
先根(中根、后根、层次)遍历二叉树得到的结点序列,称为先根序(中根、后根、层次)列
例如,对于下图所示的二叉树,其
- 先根序列为ABDFCE
- 中根序列为BFDAEC
- 后根序列为FDBECA
- 层次序列为ABCDEF
1)先根遍历
步骤为:①访问根、②遍历左子树、③遍历右子树
先根遍历递归算法
讯享网#include <iostream> using namespace std; struct Node{ Node *left; Node *right; char data; Node():left(nullptr),right(nullptr),data('#'){} }; /*先根遍历*/ void preOrder(Node * root){ //递归出口 if(root==nullptr) return; //访问根 cout<<root->data; //遍历左子树 preOrder(root->left); //遍历右子树 preOrder(root->right); } int main() { char t[20]="AB#DFCE"; int i=0;//计数器 Node *root=nullptr; root=createTree(t,&i); preOrder(root); return 0; }
2)中根遍历
步骤为:①遍历左子树、②访问根、③遍历右子树
中根遍历递归算法
/*中根遍历*/ void inOrder(Node * root){ //递归出口 if(root==nullptr) return; //遍历左子树 inOrder(root->left); //访问根 cout<<root->data; //遍历右子树 inOrder(root->right); }
3)后根遍历
步骤为:①遍历左子树、②遍历右子树、③访问根
后根遍历递归算法
讯享网/*后根遍历*/ void postOrder(Node * root){ //递归出口 if(root==nullptr) return; //遍历左子树 postOrder(root->left); //遍历右子树 postOrder(root->right); //访问根 cout<<root->data; }
4)层次遍历
层次遍历即按照二叉树的层数从小到大,同一层中从左到右的顺序访问二叉树的所有结点
//队列 class Queue{ public: Queue():font(-1),rear(0),q_count(0){ for(int i=0;i<q_size;i++){ q[i]=nullptr; } } //入队 void qIn(Node *p){ if(q_count>=q_size){ //队列满了 cout<<"Queue overflow!"<<endl; return; } if(q_count==0){ //队列为空 font=rear; } q[rear]=p; rear=(rear+1)%q_size; q_count++; } //出队 Node *qOut(){ if(q_count==0){ //队列为空 return nullptr; } Node *p=q[font]; font=(font+1)%q_size; q_count--; return p; } int q_count;//队列中的元素个数 private: const int q_size=20;//队列大小 Node *q[20];//q在逻辑上是一个环状队列 int font;//队列的头部,也是将要出队的元素的位置 int rear;//下一个元素入队的位置 }; /*层次遍历*/ void levelOrder(Node * root){ if(root==nullptr){ return; } Queue q; q.qIn(root);//入队 while(q.q_count>0){ Node *p=q.qOut(); cout<<p->data; if(p->left!=nullptr){ q.qIn(p->left); } if(p->right!=nullptr){ q.qIn(p->right); } } }
上面我们只说了先根(中根、后根)遍历的递归算法,非递归算法请看这篇博客——《数据结构 | 二叉树 先根、中根、后根遍历的非递归算法》
3.二叉树的创建
前面我们说了,二叉树的创建可以借助二叉树遍历算法的思想来完成,现在我们先思考一个问题——只根据先根序列,能唯一确定一棵二叉树吗?
显然是不能的。为了解决这个问题,我们在先根序列中加入一些特殊的符号(比如'#')来表示空指针的位置,例如对于下图所示的二叉树,其先根序列为ABDFCE,改造后的序列为AB#DFCE

讯享网#include <iostream> using namespace std; struct Node{ Node *left; Node *right; char data; Node():left(nullptr),right(nullptr),data('#'){} }; /*创建二叉树*/ Node * createTree(char t[20],int *num){ char ch=t[(*num)]; (*num)++; if(ch=='#'){ return nullptr; } //创建根结点 Node *p=new Node(); p->data=ch; //创建左子树 p->left=createTree(t,num); //创建右子树 p->right=createTree(t,num); return p; } int main() { char t[20]="AB#DFCE"; int i=0;//计数器 Node *root=nullptr; root=createTree(t,&i); return 0; }
注意,由于createTree 函数是采用递归算法书写的,为了顺序读入改造后的先根序列,需要额外使用一块计数器空间(例如,上面代码中main函数的int i)
拓展
- 根据先根序列和中根序列,能唯一确定一棵二叉树
- 根据后根序列和中根序列,也能唯一确定一棵二叉树
- 但是根据先根序列和后根序列,不能唯一确定一棵二叉树





版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/81267.html