数组和二叉树

数组的存储地址

矩阵的压缩存储

稀疏矩阵——三元组顺序表

树

定义

树是n个节点的有限集。n=0时称为空树。在任意一颗非空树中：

• 有且仅有一个特定的称为根（root）的结点。
• 当n>1时，其余结点可分为m（m>0）个互不相交的有限集t1、t2……，其中每一个集合本身优势一颗树并称为根的子树（SubTree）。
• 树的结点包含一个数据元素及若干指向其子树的分支。
• 结点拥有的子树数称为结点的度。
• 度为0的结点称为叶子（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。
• 除根结点之外，分支结点也称为内部结点。
• 树的度是树内各结点的度的最大值。
• 结点的子树的根称为该结点的孩子，相应的，该结点称为孩子的双亲。同一个双亲的孩子之间互称兄弟。
• 结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都成为该结点的子孙。

结点的层次从根开始，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟，树中结点的最大层次称为树的深度或者高度。

• 有序树——从逻辑上看，树中结点的各子树从左至右是有次序的，不能互换。
• 无序树——从逻辑上看，树中结点的各子树从左至右是无序的，可以互换。

森林

森林是m(m>=0）棵互不相交的树的结合。对树中的每个结点而言，其子树的集合即为森林。

树的应用场景

1. 文件系统
2. 数据库索引
3. 决策树
4. 网络路由
5. 表达式树
6. 堆
7. 哈夫曼编码树
8. 二叉搜索树

二叉树

二叉树的定义

二叉树是一种每个结点最多有两个子结点的树结构。二叉树的子树有左右之分，其次序不能任意颠倒。

深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树的编号从1至n的结点一一对应时，称之为完全二叉树。

完全二叉树是一种特殊的二叉树，其定义是：除了最后一层外，所有层的结点都达到了最大结点数，并且最后一层的结点是从左到右依次排序的。

二叉树的性质

二叉树的遍历

1.先序遍历

步骤：

1. 访问当前根节点。
2. 递归遍历左子树。
3. 递归遍历右子树。

2.中序遍历

步骤：

1. 递归遍历左子树。
2. 访问当前根结点。
3. 递归遍历右子树。

3.后续遍历

步骤：

1. 递归遍历左子树。
2. 递归遍历右子树。
3. 访问当前根结点。

最优二叉树（赫夫曼树）

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。