1. 前言
树是一种很重要的数据结构，最初对数据结构的定义就是指对树和图的研究，后来才广义化了数据结构这个概念。从而可看出树和图在数结构这一研究领域的重要性。
树和图重要的原因是，它让计算机能建模出现实世界中更多领域里错综复杂的信息关系，让计算机服务这些领域成为可能。
本文将和大家聊聊树的基本概念，以及树的物理存储结构以及实现。
2. 基本概念
数据结构的研究主要是从 2 点出发：
- 洞悉数据与数据之间的逻辑关系。
- 设计一种物理存储方案。除了存储数据本身还要存储数据之间的逻辑关系，并且能让基于此数据上的算法利用这种存储结构达到事半功倍的效果。
当数据之间存在一对多关系时，可以使用树来描述。如公司组织结构、家庭成员关系……
完整的树结构除了需要描述出数据信息，还需要描述数据与数据之间的关系。树结构中，以节点作为数据的具体形态，边作为数据之间关系的具体形态。
也可以说树是由很多节点以及边组成的集合。
如果一棵树没有任何节点，则称此树为空树。如果树不为空，则此树存在唯一的根节点（root），根节点是整棵树的起点，其特殊之处在于没有前驱节点。如上图值为董事长的节点。
除此之外，树中的节点与节点之间会存在如下关系：
- 父子关系：节点的前驱节点称其为父节点，且只能有一个或没有（如根节点）。节点的后驱节点称其为子节点，子节点可以有多个。如上图的
董事长节点是市场总经理节点的父节点，反之，市场总经理节点是董事长节点的子节点。 - 兄弟关系： 如果节点之间有一个共同的前驱（父）节点，则称这些节点为兄弟节点。如上图的
市场总经理节点和运维总经理节点为兄弟关系。 - 叶节点： 叶节点是没有后驱（子）节点的节点。
- 子树：一棵树也可以理解是由子节点为根节点的子树组成，子树又可以理解为多个子子树组成…… 所以树可以描述成是树中之树式的递归关系。
如下图所示的 T 树 。
可以理解为T1和T2子树组成。
T1、T2又可以认为是由它的子节点为根节点的子子树组成，以此类推，一直到叶节点为止。
树的相关概念：
- 节点的度： 一个节点含有子树的个数称为该节点的度。
- 树的度：一棵树中，最大的节点的度称为树的度。
- 节点的层次：同级的节点为一个层次。根节点为第
1层，根的子节点为第2层，以此类推。 - 树的高（深）度： 树中节点最大的层次。如上图中的树的最大层次为
4。
树的类型：
- 无序树：树中的结点之间没有顺序关系，这种树称为无序树。
- 有序树：树中任意节点的子节点之间有左右顺序关系。如下图，任一节点的左子节点值小于右子节点值。
-
二叉树：如果任一节点最多只有
2个子节点，则称此树结构为二叉树。上图的有序树也是一棵二叉树。 -
完全二叉树：一棵二叉树至多只有最下面两层的节点的子结点可以小于
2。并且最下面一层的节点都集中在该层最左边的若干位置上。 -
满二叉树：除了叶节点，其它节点的子结点都有
2个。如上图中的树也是满二叉树。
3. 物理存储
可以使用邻接矩阵和邻接表的形式存储树。
3.1 邻接矩阵存储
邻接矩阵是顺序表存储方案。
3.1.1 思路流程
- 给树中的每一个节点从小到大进行编号。如下图，树共有
11个节点。
- 创建一个
11X11的名为arrTree的矩阵 ，行和列的编号对应节点的编号，并初始矩阵的值都为0。
- 在树结构中，编号为
1的节点和编号为2、3的节点存在父子关系，则把矩阵的arrTree[1][2]和arrTree[1][3]的位置设置为1。也就是说，行号和列号交叉位置的值如果是1，则标志着编号和行号、列号相同的节点之间有关系。
- 找到树中所有结点之间的关系，最后矩阵中的信息如下图所示。
矩阵记录了结点之间的双向（父到子，子到父）关系，最终看到是一个对称的稀疏矩阵。可以只存储上三角或下三角区域的信息，并可以对矩阵进行压缩存储。
邻接矩阵存储优点是实现简单、查询方便。但是，如果不使用压缩算法，空间浪费较大。
3.1.2 编码实现
现采用邻接矩阵方案实现对如下树的具体存储：
- 节点类型： 用来描述数据的信息。
struct TreeNode{
//节点的编号
int code;
//节点上的值
int data;
};
- 树类型：树类型中除了存储节点（数据）信息以及节点之间的关系，还需要提供相应的数据维护算法。本文仅考虑如何对树进行存储。
class Tree {
private:
int size=7;
vector<TreeNode> treeNodes;
//使用矩阵存储节点之间的关系，矩阵第一行第一列不存储信息
int matrix[7][7];
//节点编号，为了方便，从 1 开始
int idx=1;
public:
Tree() {
}
//初始根节点
Tree(char root) {
cout<<3<<endl;
for(int r=1; r<this->size; r++) {
for(int c=1; c<this->size; c++) {
this->matrix[r][c]=0;
}
}
TreeNode node= {this->idx,root};
this->treeNodes.push_back(node);
//节点的编号由内部指定
this->idx++;
}
//获取到根节点
TreeNode getRoot() {
return this->treeNodes[0];
}
//添加新节点
int addVertex(char val) {
if (this->idx>=this->size)
return 0;
TreeNode node= {this->idx,val};
this->treeNodes.push_back(node);
//返回节点编号
return this->idx++;;
}
/*
* 添加节点之间的关系
*/
bool addEdge(int from,int to) {
char val;
//查找编号对应节点是否存在
if (isExist(from,val) && isExist(to,val)) {
//建立关系
this->matrix[from][to]=1;
//如果需要，可以打开双向关系
//this->matrix[to][from]=1;
}
}
//根据节点编号查询节点
bool isExist(int code,char & val) {
for(int i=0; i<this->treeNodes.size(); i++) {
if (this->treeNodes[i].code==code) {
val=this->treeNodes[i].data;
return true;
}
}
return false;
}
//输出节点信息
void showAll() {
cout<<"矩阵信息"<<endl;
for(int r=1; r<this->size; r++) {
for(int c=1; c<this->size; c++) {
cout<<this->matrix[r][c]<<" ";
}
cout<<endl;
}
cout<<"所有节点信息："<<endl;
for(int i=0; i<this->treeNodes.size(); i++) {
TreeNode tmp=this->treeNodes[i];
cout<<"节点："<<tmp.code<<"-"<<tmp.data<<endl;
//以节点的编号为行号，在列上扫描子节点
char val;
for(int j=1; j<this->size; j++ ) {
if(this->matrix[tmp.code][j]!=0) {
isExist(j,val);
cout<<"/t子节点："<<j<<"-"<<val<<endl;
}
}
}
}
};
测试代码：
int main() {
//通过初始化根节点创建树
Tree tree('A');
TreeNode root=tree.getRoot();
int codeB= tree.addVertex('B');
tree.addEdge(root.code,codeB);
int codeC= tree.addVertex('C');
tree.addEdge(root.code,codeC);
int codeD= tree.addVertex('D');
tree.addEdge(codeB,codeD);
int codeE= tree.addVertex('E');
tree.addEdge(codeC,codeE);
int codeF= tree.addVertex('F');
tree.addEdge(codeC,codeF);
tree.showAll();
}
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/291806.html