【落羽的落羽 数据结构篇】树、二叉树

一、树

1. 树的概念和结构

之前我们学习了线性表，今天我们再来接触一种全新的数据结构——树。
树是一种非线性的数据结构，它是有有限个结点组成的一个具有层次关系的结构。把它称为树是因为它看起来就像一棵倒挂的树，根朝上而叶朝下。

现实中的树：

树形结构：

关于数据结构树：

• 它有一个根结点，根结点没有前驱结点，如上图的A就是这棵树的根结点。
• 除根结点外，其余结点被分为有限个互不相交的集合，每一个集合都是一棵子树，每棵子树有且只有一个前驱结点，可以没有后继或多个后继结点。因此，树是递归定义的。
• 子树不能有交集，否则就不是树形结构。
• 一棵有n个结点的树有n - 1条边

2. 树的相关术语

• 父结点/双亲结点：若一个结点有子结点，则这个结点是其子节点的父结点。如上图，A是B、C、D、E的父结点，C是H的父结点。

• 子结点/孩子结点：若一个结点含有子树，则子树的根结点称为该结点的子结点。如上图，B、C、D、E是A的子结点，K是F的子结点。

• 结点的度：一个结点有几个孩子，它的度就是多少。如上图，A的度是4，C的度是2，M的度是0。

• 树的度：一棵树中，所有结点的度中的最大值就是这棵树的度。如上图，这棵树的度是6。

• 叶子结点/叶节点/终端节点：度为0的结点。如上图，K、G、L、M、N、D、I、O都是叶子结点。

• 分支结点/非终端结点：度不为0的结点。如上图，A、B、C、E、F、H、J都是分支结点。

• 兄弟结点：具有相同父结点的结点互称为兄弟结点。如上图，B、C、D、E互称为兄弟结点，I、J互称为兄弟结点。

• 结点的层次：从根结点开始定义，根结点在第1层，根结点的子结点在第2层，以此类推。如上图，D在第2层、N在第4层。

• 树的高度/深度：树中结点的最大层次。如上图，这棵树的高度为4。

• 路径：从一个结点到另一个结点的结序列，结点之间只能通过父子关系连接、如上图，A到L的路径为A-C-H-L，G到O的路径为G-C-A-E-J-O。

• 结点的子孙：以一个结点为根结点的子树中的所有结点都称为该结点的子孙。如上图，除A外所有结点都是A的子孙，I、J、O都是E的子孙。

• 结点的祖先：从根结点到一个结点所经分支上的所有结点称之为该节点的祖先。如上图，A是除自己外所有结点的祖先，A、B、F都是K的祖先。

• 森林：若干棵互不相交的树的集合称为森林。

二、二叉树

1. 概念与结构

在树形结构中，我们最常用的就是二叉树。二叉树由根结点、左子树、右子树组成，或者为空。
二叉树的特点是：

• 二叉树的度一定不大于2，也就是二叉树的每一个结点的子结点不多于2个。
• 二叉树的子树有左右之分，次序不能颠倒。
  

2. 满二叉树

满二叉树是二叉树的特殊情形。一个二叉树如果每一层的结点数都达到最大值，它就是满二叉树。也就是除叶子结点外每一个结点都有两个子结点。不难计算，如果一个满二叉树的高度为k，则它的结点总数是2^k -1（等比数列求和）

3. 完全二叉树

完全二叉树是由满二叉树引出来的。
我们首先要知道二叉树中结点的编号方式：从上到下，从左到右。从第一层开始从左到右从0开始依次编号，第一层编完第二层从左到右编号……直到所有结点编号完。

对于有n个结点的二叉树，若每一个结点都与深度相同的满二叉树的编号从0到n的结点一一位置对应，这个二叉树就是完全二叉树，满二叉树也是完全二叉树。
也可以理解为：完全二叉树的每一层结点个数达到最大，最后一层不一定达到最大，且结点是从左到右依次排列的。
比如，以下这些都是完全二叉树：

4. 二叉树的性质

• 非空二叉树的第i层上最多有2^i-1个结点
• 深度为h的二叉树的结点数不多于2^h-1
• 具有n个结点的满二叉树的深度为log₂(n+1)

5. 二叉树的存储结构

二叉树既可以用顺序结构存储，也可以用链式结构存储，我们之后都要学习。

本篇完，感谢阅读