树结构数据存储

‘壹’ 数据结构学习——树(Tree)

数据结构学习——树(Tree)

树是一种重要的非线性数据结构，它模拟了自然界中树的形态，具有层次性和分支性。以下是关于树的详细解析：

一、概述

1. 树结构

   树结构之所以称之为树结构，是因为它的长相就是一种树状结构。每一棵树都有一个主干（根节点），每个主干可以分为许多子干（子节点），每个子干又可以分为许多孙子干（孙节点），以此类推。

   

   优点：便于查找某个节点的所有子节点。

   缺点：需要额外的存储空间来存储孩子链表，且查找父节点需要遍历所有节点。

2. 兄弟表示法

   每个节点拥有两类参数：一类用于存储自身数据，另一类存储兄弟节点（即同层次的其他节点）。

   优点：便于查找某个节点的所有兄弟节点。

   缺点：无法直接表示上级和下级节点关系，通常需要结合其他表示法使用。

3. 总结

   在日常开发中，可以根据具体的应用场景选择合适的树表示法。不同的表示法可以相互组合，以充分利用各自的优点并弥补彼此的不足。

通过以上内容的学习，可以深入理解树这种数据结构的基本概念、特点、术语以及存储结构，为后续的数据结构学习和算法实现打下坚实的基础。

‘贰’ 数据库物理结构中，存储着哪几种形式的数据结构

数据库物理结构中，主要存储着以下几种形式的数据结构：

1. 记录的存储方式：

   • 顺序存储：数据按照一定顺序连续存储在磁盘或内存中。
   • B树结构存储：一种平衡树结构，用于存储和检索大量有序数据，具有良好的平衡性和查找效率。
   • Hash方法存储：通过哈希函数将数据映射到特定的存储位置，实现快速查找。

2. 索引的组织方式：索引是数据库中用于加速数据检索的数据结构，如B+树索引、哈希索引等，它们以不同的方式组织数据以提高查询效率。

3. 数据存储记录结构：这包括数据在物理存储介质上的具体表示形式，如定长记录、变长记录等，以及记录之间的关联方式。

4. 压缩存储和加密存储：

   • 压缩存储：为了减少存储空间，数据在存储前可能会进行压缩处理。
   • 加密存储：为了保证数据的安全性，数据在存储时可能会进行加密处理。

这些数据结构共同构成了数据库的物理存储模式，决定了数据在数据库内部的表示方式和存储方式。

‘叁’ 数据结构——树

一、树的概念

树是区别于线性表的另一种数据结构，其本质是结点的有限集。树的定义包含以下两点：

• 有且仅有一个特定的称为根（root）的结点。
• 当结点数量大于1时，其余结点可分为若干个互不相交的有限集，其中每个集合也可以看作一棵树，称之为根的子树。

1. 度（结点的分类）

• 结点拥有的子树的数量称为该结点的度。
• 树的度则是这棵树中度最多的结点的度的值。

例如，在图中，B结点的度为1（因为它只拥有一颗子树D），而D的度为3（因为它拥有G、H、I三颗子树）。A结点的度则取决于它拥有的子树数量。

2. 结点之间的关系

• 结点的子树的根称之为该结点的孩子（child结点）。
• 该结点衍生出来的结点称之为该结点的父母（parent结点）。
• 由同一个结点衍生出的同一层结点互相称之为兄弟（sibling）。
• 由同一个结点之下的所有结点称之为子孙。

3. 树的层与深度

• 结点的层次从根算起，根为第一层，根的孩子为第二层，以此类推。
• 一棵树的深度是树中结点层次最大的值，也称为树的高度。

二、树的存储结构

双亲孩子表示法：

• 把树中的所有结点的值依次组成一个单链表。
• 每个结点定义三个域：数据域、父母指针域、长子（第一个孩子）指针域。
• 如果长子有兄弟，则指针域指向下一个存储兄弟位置的指针域，否则为空。

三、二叉树

1. 二叉树的定义

• 二叉树由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成（二叉树是递归定义）。

2. 二叉树的特点

• 每个结点最多有两颗子树。
• 左子树与右子树有顺序，即使一棵树中只有一个子树，也需要判断是左子树还是右子树。

3. 一些特殊的二叉树

• 斜树：所有结点都只有左子树或所有结点都只有右子树的二叉树称为斜树（斜树类似于单链表）。
• 满二叉树：如果一棵二叉树的所有分支结点都存在左右子树，并且所有的叶子结点都在同一层，则称之为满二叉树。
• 完全二叉树：如果每个结点按层序编号与相同层数的满二叉树编号一致，则这棵树称为完全二叉树。

4. 二叉树的性质

• 在二叉树的第n层上最多有2^(n - 1)个结点。
• 深度为k的二叉树至多有2^k - 1个结点。
• 一颗二叉树的叶子结点数为n，度为2的结点数量为m，则n = m + 1。
• 具有n个结点的完全二叉树深度为log2n + 1。
• 对于一颗结点数量为n的完全二叉树，n为树的深度，i为按树的层为结点编号，则有：

  若i = 1，则此结点为根结点。

  若i > 2^n，则此结点的左孩子不存在。

  若i结点存在右孩子，则右孩子序号为2i + 1。

5. 二叉树的存储结构

• 顺序存储结构：将二叉树中的每一个结点按照满二叉树的层次序号进行编号，将空着的编号留空，将结点中的数据存入数组对应编号中。但这种方法浪费存储空间，只适用于完全二叉树。
• 二叉链表：每个结点定义两个指针域，分别是lchild（左孩子）和rchild（右孩子）。这种方法适用于任意二叉树。

6. 二叉树的遍历

• 前序遍历：按照根结点->左子树->右子树的顺序遍历。
• 中序遍历：按照左子树->根结点->右子树的顺序遍历。
• 后序遍历：按照左子树->右子树->根结点的顺序遍历。
• 层序遍历：按照一层一层从左到右的顺序依次遍历树。

以下是各遍历方法的图示：

递归遍历的核心思想是理解递归，通过递归或栈的思想可以实现二叉树的遍历。

‘肆’ 怎样在 MySQL 表中存储树形结构数据

一般比较普遍的就是四种方法：

（具体见 SQL Anti-patterns这本书）Adjacency List：

每一条记录存parent_idPath Enumerations：

每一条记录存整个tree path经过的node枚举Nested Sets：

每一条记录存 nleft 和 nrightClosure Table：

维护一个表，所有的tree path作为记录进行保存。各种方法的常用操作代价见下图