树

树结构的形状很像现实生活中一棵倒置的大树。树结构是由一堆节点和边组成的具有层级关系的非线性数据结构。树顶部的节点被称为根节点，它通常是搜索、遍历等操作的起始位置。树结构在很多地方都有应用，比如操作系统中的文件结构。

在使用树结构需要我们掌握一些基础概念，便于学习交流使用。常见的树的概念有:

根节点(Root):树的最顶层节点。

父节点(Parent Node):节点沿着边往上一层的节点称为该节点的父节点。

子节点(Child Node):节点沿着边往下一层的节点称为该节点的子节点。

兄弟节点(Sibling):同一个父节点的子节点互为兄弟节点。

边(Edge):父节点和子节点之间连接，形成边。

叶子节点(Leaf):没有子节点的节点称为叶子节点。

子树(Subtree):以某个子节点为根节点的树分支。

节点的深度(Depth):是指从根节点到该节点的距离。

节点的高度(Height):该节点到叶子节点的最长距离。

树的高度(Height of tree):根节点到叶子节点的最长距离。

节点的层级(Level):该节点的父节点数量+1。

节点的度(Degree):该节点的子节点数量

二叉树

每个节点最多有两个子节点的树被称为二叉树。在给定的二叉树中，任何级别的最大节点数为 $2^{i-1}$，其中 $i$ 是级别编号

满(完美)二叉树(perfect binary tree):每个节点都有 $0$ 个或 $2$ 个子节点，所有的叶子节点都在同一层。除叶子节点以外，所有内部节点都必须有两个子节点。

完全二叉树(complete binary tree):完全二叉树除了最后一层之外的所有层次都被填满，最后一层有的位置只有左节点。注意，完美二叉树是特殊的完全二叉树

顺序存储:用数组结构来表示二叉树。定义一个数组，用于存储树的所有节点。树中的节点数决定了数组的大小。数组的第一个位置存储根节点。如果一个节点存储在第 $i$ 位置那么它的左子节点和右子节点分别存储在第 $2i$ 和第 $2i+1$ 位置。

struct node{
  [数据类型] data;//数据
  int left,right;//左孩子编号、右孩子编号
}