数据结构之二叉树（1）

数据结构之二叉树（1）

一、树

1、树的概念与结构

（1）树是一种非线性的数据结构，由n(n>=0)个有限结点组成一个具有层次关系的集合。

（2）树有一个特殊的结点，叫做根结点，它没有前驱结点。

（3）除根结点外，其余结点都有前驱节点，也叫父结点（双亲结点）。

（4）注意：树形结构中，子树之间不能有交集，否则就不叫树形结构。

2、树形概念图

2、树的相关术语

（1）父结点/双亲结点：若一个节点有子节点，那么这个节点就是该子节点的父节点。

（2）子节点/孩子节点：一个节点含有子树的根节点。

（3）树的度：一棵树中，最长的子节点的个数称为树的度。

（4）兄弟节点：含有相同父节点的节点。

（5）节点的层次：从根节点开始，根为第一层，根的子节点为第二层，以此类推！

（6）森林：由互不相关的多棵树组成森林。

（7）深度/高度：树中节点的最大层次。

3、二叉树：

（1）特点：【1】不存在度>2的节点.

​ 【2】二叉树的子树有左右之分，次序不能颠倒。

注意：二叉树是有序树。

图示：

（2）特殊的二叉树：

【1】满二叉树：二叉树的每一层的节点数都达到最大值2，那么这个二叉树就是满二叉树。（假设一个二叉树的层次为K，那么节点数就是2^K-1）

【2】完全二叉树：对于深度为K的，有n个节点的二叉树，当且仅当每一个节点都与深度为K的满二叉树中1~n的编号一一对应时。

（3）二叉树的存储结构：

​ 【1】顺序结构

​ 【2】链式结构

（3）二叉树的存储结构：

​ 【1】顺序结构

​ 【2】链式结构

★★★★★提示：虽然此篇文稿枯燥乏味，但是却是学好二叉树的基本知识点，需好好掌握！！！