【数据结构课程学习】树：lesson1

🚗1.树的概念：

树是一种非线性的数据结构，有n个有限节点组成一个有层次的集合。它的结构看起来像一颗倒挂的树，根在上面，叶子和枝干朝下。 ●最上面的节点为根节点，根节点没有前驱节点。 ●树是递归定义的。 ●树形结构中，子树是不能相交的，否则就不构成树，也就是除根节点以外，其他的节点只有一个父节点。 ●n个节点的树，有n-1条线。

🚗2.树的相关概念：

树里面的基本名词的意思： ●节点的度：一个节点的子树称为节点的度，也就是看该节点有几个子节点。A节点的度为6，B节点的度为0，F节点的度为3。 ●叶节点或终端节点：度为0的节点为叶节点，也就是像叶子一样没有分支。B，C，H，I，P，Q，K，L，M，N全部都是叶节点。 ●父节点：一个节点含有子节点，那么称该该节点是此子节点的父节点。A是B的父节点。 ●子节点：一个含有子树的根节点，该子树的节点为根节点的子节点。P为J的子节点。 ●兄弟节点：有相同父节点的节点为兄弟节点。B，C为兄弟节点。 ●树的度：树里面最大节点的度为树的度。A的度为6，其他的都小于6，所以树的度为6。 ●节点的层次：根为第一层，根的子节点是第二层。下图中有四层。 ●树的高度或深度：树中节点的最大层次，节点的最大层次为4，所以树的高度为4。 ●根节点是所以节点的祖先，所以节点是根节点的子孙。 ●堂兄弟节点：父节点在同一层的节点为兄弟节点。K和N为堂兄弟节点。 ●森林：由两棵以上互不相加的树的集合组成森林。

🚗3.树的表示：

根据之前我们学的数据结构，实现任何一种数据结构，最起码也要有存储数据，并且能找到每个节点这两个基本的功能。

⛷方法一： 因为前面有树的度这一个概念，也就是说，假如一棵树的度为N，任何一个节点的子节点最多有N个，所以我们定义节点结构的时候，就只需要定义一个指针数组，指针数组的大小为N，把指向这个节点的所以子节点的指针存在指针数组里面。虽然这样可以实现树，但是会存在空间浪费，在有些情况下，空间浪费会非常大，如下图：树的度为4，但是除了E节点以外，其他节点里面的指针数组都是空的，但是也为他们开辟了N个指针大小的空间，这样就浪费空间了，如果节点更多，那么浪费的空间该是多么大啊！

⛷方法二（左孩子右兄弟法）： 也就是说，一个节点里面，一个指针存着子节点的最左边的子节点，一个指针存着右兄弟的指针。左孩子可以在节点的层中移动，右兄弟可以在同一层遍历，这样就可以找到每一个节点，这种方法也不会存在空间浪费，每个节点一直都是两个指针，也不像第一种方法一样，定义一个指针数组。

typedef int DataType;
struct Node
{
 struct Node* firstChild1; // 第一个孩子结点
 struct Node* pNextBrother; // 指向其下一个兄弟结点
 DataType data; // 结点中的数据域
};

🚗4. 树在实际中的运用（表示文件系统的目录树结构）

太好玩了，爱玩！