树
树一种抽象类型数据,用来模拟具有树状结构性质的数据集合。它是由多个有限节点组成一个层次关系的集合。特点:
- 每个节点有0个或者多个子节点
- 没有父节点的节点称之为根节点
- 每个非根节点有且只有一个根节点
术语
- 节点的度:一个节点含有的
子树的个数
称为该节点的度 - 树的度:
最大的节点的度
称之为数的度 - 叶结点或终端节点:
度为零
的节点 - 父节点:含有子节点的节点上级
- 子节点:一个节点还有的子树的根节点称为该节点的子节点
- 兄弟节点:具有相同父节点的节点
- 节点的层次:根节点为第一层,其子节点为第二层,类推
- 树的高度或者深度:节点最大层次
- 堂兄弟节点:父节点在同一层次的节点
- 森林:由多个树互不相交的树的集合称为森林
树的种类
- 无序树:任意节点的子节点之间没有任何的顺序关系,称之为无序树,也叫自由树
- 有序树:子节点之间由顺序关系
- 二叉树:每个节点最多含有两个子树的树
- 完全二叉树:若一棵树的深度为d,除去第d层外,其他各层的节点数目达到了最大值,且第d层所有节点从左向右连续紧密的排列的二叉树
- 满二叉树:所有层的节点数达到了最大数
- 平衡二叉树:当且仅当任何节点之间的
两颗子树的高度差不大于1
的二叉树 - 排序二叉树:二叉搜索树,二叉查找树,性质:任何节点左边的数比节点上的数小,右边比节点上的数大
- 霍夫曼树:用于信息编码
- $B$树/$B^+$树:在
MySQL
的索引中使用
- 二叉树:每个节点最多含有两个子树的树
树的存储
- 顺序存储:将数据结构存储在固定的数组中,遍历上有一定的优势,占空间
- 链式存储
应用场景
- HTML文件
- 路由协议
- mysql索引
- 文件目录的目录结构
- AI算法都是树搜索,比如决策树
二叉树
每个节点最多只有两个子节点,左子树和右子树,性质:
- 第i层上最多$2^(i-1)$个节点
- 深度为k的二叉数最多有$2^k-1$个节点
- 具有n个节点的完全二叉树的深度必为$log2(n+1)$
- 叶结点数为$N_0$,深度为2的节点总数为$N_2$,则$N_0=N_2+1$
树的遍历
深度遍历的三种遍历顺序:
子节点中必须先左后右
- 前序遍历:根—>左—>右
- 中序遍历:左—>根—>右
- 后序遍历:左—>右—>根
二叉树的确定
根据三种遍历方式的两种来确定二叉树,其中必须给定中序遍历的结果
1 | # 二叉树中元素添加 |
树的遍历图解
在给出数的顺序反推树结构的时候,必须给定$\color{red}{中序}$,下面👇的栗子根据先序和中序确定一棵树: