树·c++

树（Tree） 是一种非线性的数据结构，它由若干个 节点（Node） 组成，并通过 边（Edge） 相互连接。树的结构类似于现实中的树，其中 根节点（Root Node） 位于顶部，而其他节点则以分支的方式连接在根节点下面，形成分层结构。

树结构具有以下特点：

1. 根节点： 树的顶部节点，没有父节点。

2. 节点： 除了根节点外，每个节点都有且只有一个父节点，并可以有零个或多个子节点。

3. 子节点： 一个节点的直接下属节点。

4. 父节点： 一个节点的直接上级节点。

5. 叶节点： 也叫孩子节点，是指父亲节点的一个下属

6. 分支： 节点与其子节点之间的连接，用于表示节点之间的关系。

7. 路径： 从根节点到某个节点的所有连续分支所组成的序列。

8. 深度（Depth）： 节点在树中的层数，根节点为第一层，依次递增。

9. 高度（Height）： 树中节点的最大深度。

在树中还有一种树叫 二叉树 ，是指一个父亲节点最多有2个叶节点 ，二叉树又分为普通二叉树、满二叉树、完全二叉树：

1. 普通二叉树： 普通二叉树又分为只有左子树、只有右子树和普通二叉树，只有左子树 是指只有左子树，没有右子树， 只有右子树 是指只有右子树，没有左子树

2. 满二叉树： 满二叉树是指一个二叉树在一定的高度内这个二叉树是满的（指没有空这的结点位置）

3. 完全二叉树： 完全二叉树是指一个满二叉树中只能有最后一层的还得是右边的结点，不能是左边的结点，这叫满二叉树

树的存储分为链式存储和顺序存储：

1. 顺序存储： 顺序存储是用数组模拟，适用于满二叉树和完全二叉树，但复杂度较高，如果树的分枝比较稀疏，建议使用链式存储
2. 链式存储： 链式存储是用和链表差不多的存储方式存储的，链式存储适用于稀疏图，是每个结点都会记住自己的左孩子和右孩子的名字,链式存储定义框架如下：

const int N=1e4+10;	//这里根据题目要求修改
struct node
{int lchild,rchild;	//这里是左孩子和右孩子
}a[N];

树的遍历分为bfs和dfs：

1. dfs： 深度优先搜索，有三种， 先序遍历、中序遍历、后序遍历 ，先序遍历是先遍历根，在遍历左子树和右子树，中序遍历是先遍历左子树，在遍历根和右子树，后序遍历是先遍历左子树，在遍历右子树和根

2. bfs： 广度优先搜索，也叫 层序遍历 ，是一层一层的遍历