C++：树
树的概念：
所谓“树”是输就结构的一种，树大概可以分为两大类： 有根树 和 无根树 有根树使有一个确定的根节点，反之为无根树
· 子节点：从树根开始，通过树边向下扩展的节点
· 中间节点：两个节点之间的节点
· 叶节点/叶子：不能再向下延伸的节点
对于有根树而言：
· 祖先：从根结点到该结点的路径上的所有结点
·兄弟：同一双亲结点的孩子结点间互称兄弟结点
·节点的度：一个节点含有的子树的个数称为该节点的度
·树的高度：数中所有结点的层次的最大值
·堂兄弟：父节点在同一层的节点互为堂兄弟
·子树：以某节点为根的子树中任一节点都称为该节点的子树
·森林：由两棵以上互不相交的树的集合称为森林
树的分类：
·无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
·有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
·二叉树：每个节点最多含有两个子树的树称为二叉树；
·完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
·平衡二叉树/AVL树：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
·霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
·排序二叉树/二叉查找树:也称二叉搜索树、有序二叉树）；
·B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树
树的性质：
1. 对于有根树而言，除根结点以外，其余节点仅有一个父节点
2. n个节点的树仅有n-1条边
3. 树不存在换的连通图
4. 树的任意两个节点之间仅有议题哦简单路径
树的储存
1.有根树的父亲表示法：
这种方法类似于并查集，使用了（对于有根树而言，除根结点以外，其余节点仅有一个父节点）的性质。首先创建一个数组，数组下标代表节点，记录的数据表示其父节点
例:
fath[100];
void link (int i,int j)
{
fath[x] = y;
}
int main(){
link(1,-1); //父节点不存在父亲
link(2,1); //表示2节点的父亲为1
link(3,1);
link(4,3);
return 0;
}
其表示的树如下：
有根树的图存储方法：
树是一种特殊的图，所以也可以用图的方法来储存：邻接矩阵和邻接表
1.邻接矩阵：定义一个n*n的二维数组，类型既可以是bool也可以是int,下面张图以int类型展示了如何用邻接矩阵来储存有根树：
用邻接矩阵储存的代码如下：
int map[5][5];
void link(int x,int y)
{
map[x][y] = 1;
}
2.邻接表：
代码如下：
int m;
int f[100];
int t[100];
int n[100];
void link(int x,int y){
t[m++] = y;
n[m] = f[x];
f[x] = m;
}
使用std::vector
vector<int>l[100];
void link(int x,int y)
{
l[x].push_back(y);
}
希望对你有帮助~~~
