数据结构 - 树，初探

数据结构 - 树，初探

引用

网易

1.

https://m.163.com/dy/article/JEJ6HIVT0531QNY4.html

树是数据结构中一种重要的非线性结构，它以分支关系定义层次结构，形态上类似于自然界中的倒挂的树。本文将从树的基本定义出发，详细讲解树的相关术语、二叉树的性质及遍历方法，帮助读者全面理解这一数据结构的核心概念。

01、定义

树是由n（n>=0）个元素节点组成的有限集合，当n=0时，称为空树。对于非空树应满足以下要求：

• 有且仅有一个根节点；
• 当n>1时，其余节点可分成m(m>=0)个互不相交的有限集合，其中每一个集合本身又是一棵树，称为根的子树。

从定义中我们可以得到以下结论：

1. 树是分支分层结构；
2. 树中仅有根节点没有父节点；
3. 除根节点外，其余节点有且仅有一个父节点；
4. 树中每个节点，可以有零个或多个子节点；
5. 根节点到任何除自身之外的节点，有且仅有一条路径；

02、术语

1、节点相关

• 根节点：树中仅存在一个根节点，位于树的最顶层，并且其没有父节点；
• 叶节点：叶节点位于树的最末端，其下层没有任何节点。
• 子节点：某个节点的下层节点，相对于该节点叫做子节点；
• 父节点：某个节点的上层节点，相对于该节点叫做父节点；

2、结构相关

• 深度：从根节点到某一节点所经过的边的个数；根节点为0，其子节点为1，自上而下，以此类推。
• 高度：从某一节点到其最远叶节点的边数。树的高度为根节点的高度，所有叶节点高度0，其父节点为1，自下而上，以此类推。
• 层次：指节点所在的层级，根节点为第0层，其子节点为第1层，自上而下，以此类推。
• 子树：在一棵树中，任何一个以某个节点为根节点的树结构。

3、关系相关

• 兄弟节点：拥有共同的父节点的子节点。
• 祖先节点：从根节点到该节点的路径上经历的所有节点，除自身外，包括父节点、祖父节点等。
• 后代节点：该节点的所有下层节点，包括子节点、孙节点等。

4、其他术语

• 树的度：指树的宽度，也可以理解为节点的分支数，即节点的直接子节点数量，所有节点中度的最大值被视为树的度；
• 路径和路径长度：从一个节点到另一个节点经历的所有边的序列即为路径，路径上所有边的个数即为路径长度；
• 森林：指若干棵互不相交的树的集合；

03、二叉树

根据节点个数我们可以把树分成两类：二叉树和N叉树。

• 二叉树：每个节点最多有两个子节点的树；
• n叉树：每个节点最多有n个子节点的树；

其中最常用的就是二叉树，下面我们来详细聊聊二叉树。

1、定义

（1）每个节点最多有两个子节点，分别称为左子节点和右子节点；
（2）左右子节点所构成左子树和右子树也都是二叉树；

2、性质

（1）任意一颗二叉树树，若节点数为n，则边的数量为n-1；
（2）在二叉树中，第i层最多有2^i个节点；
（3）深度为k的二叉树，总节点数最少有2^k个节点，最多有2^(k+1)-1个节点；
（4）在非空二叉树中，如果n0表示叶节点数量，n2表示度为2（即有两个节点）的节点数量，则n0=n2+1；

3、遍历

二叉树遍历指按照特定顺序访问二叉树中所有节点，常用的遍历方式包括：前序遍历、中序遍历、后序遍历和层次遍历。

前序遍历

• 访问顺序：根节点->左子树->右子树
• 步骤：
  1. 访问根结点；
  2. 前序遍历左子树；
  3. 前序遍历右子树。

中序遍历

• 访问顺序：左子树->根节点->右子树
• 步骤：
  1. 中序遍历左子树；
  2. 访问根结点；
  3. 中序遍历右子树。

后序遍历

• 访问顺序：左子树->右子树->根节点
• 步骤：
  1. 后序遍历左子树；
  2. 后序遍历右子树；
  3. 访问根结点；

层次遍历

• 访问顺序：第0层->第1层->……->第n层（每层从左至右依次处理）
• 步骤：
  1. 初始化：创建一个空队列，将根节点加入队列；
  2. 遍历：
• 当队列不为空时：
• 从队列中取出一个节点，并访问该节点的值；
• 如果该节点有左子节点，将左子节点加入队列；
• 如果该节点有右子节点，将右子节点加入队列；
  3. 重复步骤2，直到队列为空；

注：测试方法代码以及示例源码都已经上传至代码库，有兴趣的可以看看。https://gitee.com/hugogoos/Planner