数据结构之树的概念以及结构

数据结构之树的概念以及结构

1.树的概念

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

叫树的原因是因为它看起来像是一颗倒挂的树，只不过是根朝上，叶朝下

1. 树的一个特殊节点叫做根节点 ，根节点没有前驱节

2. 除了根节点之外，其余节点被分割M个互不相交的集合T1，T2......,而每个集合都是与树结构相同的子树，每个子树都有属于它自己的‘根节点’，可以有0个或多个后继。

3. 由此可以看出来树的定义是递归的！

子树与子树之间是不能有交集的，否则就不是树的结构！

2.树的相关概念

在·

1. 节点的度：一个节点所含有的子树的个数称为该节点的度！例如A的度就是6，因为A有6个子树

度的概念是相对于节点而言的，每个节点都有属于它的度！子树要整体的去看（或者直接看该节点的分支有几个）例如E包括它以下的所有节点都是属于A的一颗子树！但是I，还有J以下的所有节点是属于E的两颗子树！

2. 叶节点或终端节点：度为0的节点就是叶节点（终端节点），例如H,I,P,Q,K,L.......

3. 非终端节点或者分支节点：度不为0的节点 ，与叶节点（终端节点）相对的概念。例如：E,J,F,G.....

4. 父节点或双亲节点：含有子节点的节点就是其子节点的父节点（双亲节点）。

父节点与子节点身份同时存在不冲突！例如E是，I,J这两个节点的父节点，又是A的子节点！

5. 子节点或孩子节点：一个节点含有的子树的节点称之为该节点的子节点

说实话这句话说的挺绕的，其实就是这个节点上面连着一个节点，这就是上面那个节点的子节点

6. 兄弟节点：有同一个父节点的节点彼此之间就是兄弟节点

有同一个爸就是兄弟！

7. 树的度：一棵树中，最大节点的度称之为该树的度。例如上面的树的度就是6.

每个节点都有属于它自己的度！而其中最大的那个度就是该树的度！（那个度不一定存在于根节点！）

8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推

从根节点开始数起！是下面概念的基础

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

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

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

再例如E是 I,J,P,Q的祖先，但是不是K,L的祖先，因为E的分支没有经过K.L。

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

子，父，祖先，子孙这几个概念互不冲突，可以同时存在于一个节点，只是可能对象不一样！

13. 森林：由m（m>0）棵互不相交的树的集合称为森林；

应用并查集

3.树的结构

关于树的结构的定义有

struct TreeNode
{
int date;
struct TreeNode* child1;
struct TreeNode* child2;
struct TreeNode* child3;
struct TreeNode* child4;
// ........
}

这种结构的坏处在定义繁琐！在不知道度的情况下很麻烦！

除非给了固定的度的大小！

#define N 5
struct TreeNode
{
int date;
struct TreeNode* children[N];
int childsize;
}//这种结构是类似于静态的顺序表！但是这样很浪费！

在上面的基础上进一步改进

struct TreeNode
{
int date;
//用一个顺序表存储孩子节点的指针！
struct TreeNode** children;//为什么要二级指针呢？因为要存储数据是数组的指针，所以要二级指针数组来存储！
int childsize;
int childcapacity;
}

但是的上面的所有结构都不是最优解！

虽然更加的直观！但是还是不够方便！

所以引入了一种新结构！左孩子右兄弟！

typedef int DateType;
struct TreeNode
{
struct TreeNode* Child;// 第一个孩子结点
struct TreeNode* brother;// 指向其下一个兄弟结点
DateType date;//存储数据！
}

如图：A指向它的第一个孩子B，因为A没有兄弟则兄弟指向空！

然后再B指向它的第一个孩子，然后指向它的兄弟C

......

这样子就可以通过兄弟找兄弟！

该结构的运用！

void printTree(struct TreeNode* parent)
{
if(parent == NULL)
return;
struct TreeNode* cur = parent;
while(cur)
{
printf("%d",cur->date);//先访问当前节点
printTree(cur->child);//访问自孩子节点
cur = cur->brother//再访问兄弟节点！
}
}

初次之外还有一个双亲表示法

这种方式方便找祖先！

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