【数据结构】务实篇 原

数据结构

名词定义

• 指相互之间存在着一种或多种关系的数据元素的集合+该集合中数据元素之间的关系组成。记为：

   Data_Structure=(D,R)

其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。

 指的是数据的存储形式，常见的有线性结构（数组、链表，队列、栈）【一对一】，

                                                             还有非线性结构（树、图等）。

1> 线性结构中

一个节点至多只有一个头节点，至多只有一个尾节点，彼此连接起来是一条完整的线。

比如：【链表、数组】

shixin tai shuai le

2> 非线性结构中

                      不再是一对一，而变成了一对多（而图则可以是 多对多）

如下图所示：

shixin tai shuai le

可以看到:

• 图中的结构就像一棵倒过来的树，最顶部的节点就是“根节点 (root 节点)”
• 每棵树至多只有一个根节点
• 根节点生出多个孩子节点，每个孩子节点只有一个父节点，每个孩子节点又生出多个孩子
• 父亲节点 (parent) 和孩子节点 (child) 是相对的
• 没有孩子节点的节点成为叶子节点 (leaf)

2.0> 树 的相关术语 

        如 ↑ ：   根节点、父亲节点、孩子节点、叶子节点   

shixinzhang

节点的度（度可以理解为关联度，指和该节点相关联的个数）

一个节点直接含有的子树个数，叫做节点的度。比如上图中的 3 的度是 2，10 的度是 1。

树的度

度就是分支的数目。没有分叉的二叉树节点的度就是0度。如果一个节点只有一个分叉就是1度。两个分叉就是2度的子树.

一棵树中 最大节点的度，即哪个节点的子节点最多，它的度就是 树的度。上图中树的度为 2 .

节点的层次

结点的层次从根开始定义起,根为第一层,根的孩子为第二层,依次累计.

树的高度（叶 →根）

树的高度是从叶子节点开始，自底向上增加。

树的深度（根→叶）

与高度相反，树的深度从根节点开始，自顶向下增加。

整个树的高度、深度是一样的，但是中间节点的高度 和 深度是不同的，比如上图中的 6 ，高度是 2 ，深度是 3。

2.1> 树 的两种实现

由 2> 得知，树是一个递归的概念，从根节点开始，每个节点至多只有一个父节点，有多个子节点，每个子节点又是一棵树，以此递归。

树有两种实现方式：

• 数组
• 链表

树的几种常见分类及使用场景

树，为了更好的查找性能而生。

常见的树有以下几种分类：

• 二叉树
• 平衡二叉树
• B 树
• B+ 树
• 哈夫曼树
• 堆
• 红黑树

百度百科  树