树是一种非线性数据结构，形态上和自然界中的倒挂的树很像，而数据结构中树根向上树叶向下。

什么是树？

01 、定义

树是由n（n>=0）个元素节点组成的有限集合，当n=0时，称为空树。

对于非空树应满足以下要求：

(1)有且仅有一个根节点；

(2)当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

标签：游戏攻略