数据结构之树的概念以及结构
1.树的概念
树是一种非线性的数据结构，是由n（n>=0）有限节点的组成的一个具有线性关系的集合。
叫树的原因是因为它看起来像是一颗倒挂的树，只不过是根朝上，叶朝下
- 树的一个特殊节点叫做根节点 ，根节点没有前驱节
- 除了根节点之外，其余节点被分割M个互不相交的集合T1，T2......,而每个集合都是与树结构相同的子树，每个子树都有属于它自己的‘根节点’，可以有0个或多个后继。
- 由此可以看出来树的定义是递归的！
子树与子树之间是不能有交集的，否则就不是树的结构！
2.树的相关概念
在·
- 节点的度：一个节点所含有的子树的个数称为该节点的度！例如A的度就是6，因为A有6个子树
度的概念是相对于节点而言的，每个节点都有属于它的度！子树要整体的去看（或者直接看该节点的分支有几个）例如E包括它以下的所有节点都是属于A的一颗子树！但是I，还有J以下的所有节点是属于E的两颗子树！
- 叶节点或终端节点：度为0的节点就是叶节点（终端节点），例如H,I,P,Q,K,L.......
- 非终端节点或者分支节点：度不为0的节点 ，与叶节点（终端节点）相对的概念。例如：E,J,F,G.....
- 父节点或双亲节点：含有子节点的节点就是其子节点的父节点（双亲节点）。
父节点与子节点身份同时存在不冲突！例如E是，I,J这两个节点的父节点，又是A的子节点！
- 子节点或孩子节点：一个节点含有的子树的节点称之为该节点的子节点
说实话这句话说的挺绕的，其实就是这个节点上面连着一个节点，这就是上面那个节点的子节点
- 兄弟节点：有同一个父节点的节点彼此之间就是兄弟节点
有同一个爸就是兄弟！
- 树的度：一棵树中，最大节点的度称之为该树的度。例如上面的树的度就是6.
每个节点都有属于它自己的度！而其中最大的那个度就是该树的度！（那个度不一定存在于根节点！）
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
从根节点开始数起！是下面概念的基础
- 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
- 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
再例如E是 I,J,P,Q的祖先，但是不是K,L的祖先，因为E的分支没有经过K.L。
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
子，父，祖先，子孙这几个概念互不冲突，可以同时存在于一个节点，只是可能对象不一样！
- 森林：由m（m>0）棵互不相交的树的集合称为森林；
应用并查集
3.树的结构
关于树的结构的定义有
structTreeNode
{
intdate;
structTreeNode*child1;
structTreeNode*child2;
structTreeNode*child3;
structTreeNode*child4;
// ........
}
这种结构的坏处在定义繁琐！在不知道度的情况下很麻烦！
除非给了固定的度的大小！
#define N 5
structTreeNode
{
intdate;
structTreeNode*children[N];
intchildsize;
}//这种结构是类似于静态的顺序表！但是这样很浪费！
在上面的基础上进一步改进
structTreeNode
{
intdate;
//用一个顺序表存储孩子节点的指针！
structTreeNode**children;//为什么要二级指针呢？因为要存储数据是数组的指针，所以要二级指针数组来存储！
intchildsize;
intchildcapacity;
}
但是的上面的所有结构都不是最优解！
虽然更加的直观！但是还是不够方便！
所以引入了一种新结构！左孩子右兄弟！
typedefintDateType;
structTreeNode
{
structTreeNode*Child;// 第一个孩子结点
structTreeNode*brother;// 指向其下一个兄弟结点
DateTypedate;//存储数据！
}
如图：A指向它的第一个孩子B，因为A没有兄弟则兄弟指向空！
然后再B指向它的第一个孩子，然后指向它的兄弟C
......
这样子就可以通过兄弟找兄弟！
该结构的运用！
voidprintTree(structTreeNode*parent)
{
if(parent==NULL)
return;
structTreeNode*cur=parent;
while(cur)
{
printf("%d",cur->date);//先访问当前节点
printTree(cur->child);//访问自孩子节点
cur=cur->brother//再访问兄弟节点！
}
}
初次之外还有一个双亲表示法
这种方式方便找祖先！
4.树在实际中的运用（表示文件系统的目录树结构）
