网站设计郑州,做网站服务器软件,知名商城网站建设公司,网站备案信息传树#xff08;Tree#xff09; 是一种非线性的数据结构#xff0c;它由若干个 节点#xff08;Node#xff09; 组成#xff0c;并通过 边#xff08;Edge#xff09; 相互连接。树的结构类似于现实中的树#xff0c;其中 根节点#xff08;Root Node#xff09; 位…树Tree 是一种非线性的数据结构它由若干个 节点Node 组成并通过 边Edge 相互连接。树的结构类似于现实中的树其中 根节点Root Node 位于顶部而其他节点则以分支的方式连接在根节点下面形成分层结构。
树结构具有以下特点 根节点 树的顶部节点没有父节点。 节点 除了根节点外每个节点都有且只有一个父节点并可以有零个或多个子节点。 子节点 一个节点的直接下属节点。 父节点 一个节点的直接上级节点。 叶节点 也叫孩子节点是指父亲节点的一个下属 分支 节点与其子节点之间的连接用于表示节点之间的关系。 路径 从根节点到某个节点的所有连续分支所组成的序列。 深度Depth 节点在树中的层数根节点为第一层依次递增。 高度Height 树中节点的最大深度。
在树中还有一种树叫 二叉树 是指一个父亲节点最多有2个叶节点 二叉树又分为普通二叉树、满二叉树、完全二叉树 普通二叉树 普通二叉树又分为只有左子树、只有右子树和普通二叉树只有左子树 是指只有左子树没有右子树 只有右子树 是指只有右子树没有左子树 满二叉树 满二叉树是指一个二叉树在一定的高度内这个二叉树是满的指没有空这的结点位置 完全二叉树 完全二叉树是指一个满二叉树中只能有最后一层的还得是右边的结点不能是左边的结点这叫满二叉树
树的存储分为链式存储和顺序存储
顺序存储 顺序存储是用数组模拟适用于满二叉树和完全二叉树但复杂度较高如果树的分枝比较稀疏建议使用链式存储链式存储 链式存储是用和链表差不多的存储方式存储的链式存储适用于稀疏图是每个结点都会记住自己的左孩子和右孩子的名字,链式存储定义框架如下
const int N1e410; //这里根据题目要求修改
struct node
{int lchild,rchild; //这里是左孩子和右孩子
}a[N];树的遍历分为bfs和dfs dfs 深度优先搜索有三种 先序遍历、中序遍历、后序遍历 先序遍历是先遍历根在遍历左子树和右子树中序遍历是先遍历左子树在遍历根和右子树后序遍历是先遍历左子树在遍历右子树和根 bfs 广度优先搜索也叫 层序遍历 是一层一层的遍历
