树的介绍（C语言版）

前言

        在数据结构中树是一种很重要的数据结构，很多其他的数据结构和算法都是通过树衍生出来的，比如：堆，AVL树，红黑色等本质上都是一棵树，他们只是树的一种特殊结构，还有其他比如linux系统的文件系统就是一棵树。下面让我们一起来学习一下树的结构和特点吧！

1.树的概念

        树是一种非线性的数据结构，它是由n（n >= 0）个有限的节点组成的具有层次结构的集合，把它叫做树，是因为它看起来像一颗倒挂的树，也就是说它根朝上，而叶子朝下的。

        》有一个特殊的节点 称为根节点，根节点没有前驱节点

        》除了根节点外，其余节点被分为M（M>0）个相互不想交的集合T1，T2，T3,...Tm,其中每一个集合Ti（1 <= i <=m）又是一颗结构与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有多个后继。

        》因此树是递归定义的

       

 

 

注意：树的结构中，子树之间不能有交集，否则就不是树形结构

2.与树相关

         

        节点的度：一个节点含有子树的个数，例如上图中A的度为6，D的度为1。

        叶子节点或者终端节点：度为零的节点被称为叶子结点。例如H，I，P，Q。

        非终端节点或者分支节点：度不为零的节点，上图中的：B，C，D,E...

        双亲节点或者父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点。

        孩子节点或者子节点： 一个节点含有的子树的根节点称为该节点的子节点，如上图的B是A的孩子节点。

        兄弟节点：具有相同父亲节点的节点互称为兄弟节点。

        树的度：一棵树中，最大节点的度称为树的度，如上图树的度为6.

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

        树的高度或者深度：树中节点的最大层次，如上图树的高度为4.

        堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H，I互为堂兄弟。

        节点的祖先：从根到该节点所经分支上的所有节点，如上图，A是所有节点的祖先。

        子孙：以某节点为根的子树中的任意一节点都称为该节点的子孙。如上图A节点是所有节点的子孙。

        森林：由M棵互不相交的树的集合称为森林。

3.树的表示方法

        树的结构相对线性表就复杂多了，要存储起来很麻烦，既要保存值域，也要保存节点与节点之间的关系，实际中树的表示方法有很多种，如：双亲表示法，孩子表示法 ，孩子双亲保护法以及孩子兄弟保护法。在这里介绍最简单的孩子兄弟保护法。

typedef int DataType;

struct Node

{

        struct Node* _firstChild1;//第一个孩子节点

        struct Node* _pNextBrother;//指向其下一个兄弟节点

        DataType _data;//节点中的数据域

};

          

4.树的应用

         树可以表示文件系统的目录树结构，如图：