数据结构–树

          树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。

这是一颗树

树的特点： ①每个节点有零个或多个子节②没有父节点的节点称为根节点；   ③每一个非根节点有且只有一个父节点；   ④除了根节点外，每个子节点可以分为多个不相交的子树；

树结构的名词解释如下：

树结构

1、节点：树中的一个独立单元，包含一个数据元素及诺干个指向其他子树的分支。例如，A、B、C等都是节点。

2、节点的度：节点拥有的子树数称为节点的度，例如A的度是3，C的度为0，B的度为3.

3、树的度：树的度是树内各个节点度的最大值，例如，上图中的度为3.

4、叶子：度为0 度节点称为叶子或者终端节点，例如：E、F、K、L、M、H、I、J都是叶子节点。

5、非终端节点：度不为0的节点或者分支节点，除根节点以外的非终端节点也称为内部节点。

6、双亲和孩子：节点的子树的根称为该节点的孩子，相应的该节点称为孩子的双亲，例如：B的双亲是A，B的孩子有E、F、G

7 、兄弟：同一个双亲的孩子节点称为兄弟节点，例如：B、C、D互为兄弟。

8、树的层次：节点的层次从根开始定义起，根为第一层，根的孩子为第二层，树中任何一层次等于双亲节点的层次加1.

9、有序树和无序树： 如果将树的节点的各子树看成从左到右是有序的（即不能互换）则称为该树为有序树；否则是无序树，在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。

10、节点的高度：节点到叶子节点的最长路径（边数）。

11、节点的深度：根节点到这个节点所经历的边的个数。

12、节点的层数： 节点的深度-1。

13、数的高度：根节点的高度。

定义：二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

普通二叉树

由二叉树定义以及图示分析得出二叉树有以下特点：

1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。

2）左子树和右子树是有顺序的，次序不能任意颠倒。

3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树的性质：

1）在二叉树的第i层上最多有2i-1个节点 。（i>=1）

2）二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）

3）n0=n2+1  n0表示度数为0的节点数，n2表示度数为2的节点数。

4）在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。

5）若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：

  a. 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;b. 若 2i>n，则该结点无左孩子，  否则，编号为 2i 的结点为其左孩子结点；c. 若 2i+1>n，则该结点无右孩子结点，  否则，编号为2i+1 的结点为其右孩子结点。

二叉树类型：

1、斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

2、满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

3、完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1

二叉树的存储方式：

1顺序存储：（数组）

满二叉树

顺序存储

2链式存储：（链表）

链式存储节点结构

链式存储结构

二叉树的遍历方式：

二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。

遍历示意图

1.前序遍历：通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

输出结果为：ABDHIEJCFG

2.中序遍历：从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。

输出结果为：HDIBJEAFCG

3.后序遍历：从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。

输出结果为：HIDJEBFGCA

4层序遍历：按照树的层次自上而下的遍历二叉树。

输出结果为：ABCDEFGHIJ

算法的实现转下一篇。二叉树的遍历