目录

前言

树的定义

树和线性表的异同

相同点

不同点

链式树图解

树的一些专属词 

树的分类 

根据分支数量

根据作用(或者说有序性)

树的表示方式

孩子表示法

长子兄弟表示法

父亲兄弟表示法


前言

接下来就是数据结构的第二大板块:树

之前的第一板块:线性表中的顺序表和链表已经更完。但由于队列和栈是特殊的线性表,既然特殊,实际上就普通的顺序表和链表也能实现,加上队列和栈可直接STL实现。

故由此,先暂时跳过队列和栈的实现(实际上队列和栈的实现也是仿STL的)

笔记(1)为顺序表仿STL的实现,笔记(2)为链表的实现,笔记(3)为队列的仿STL实现,笔记(4)为栈的仿STL实现,而本篇笔记(5)则介绍树形结构

树的定义

是一种数据结构,它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树

就像这样,这就是一个树形结构。

树和线性表的异同

相同点

树和线性表都有顺序存储和链式存储。

树和线性表都是动态存储

树的顺序存储和顺序表类似,通过下标来存储数据,通过长度来存储位置

树的链式存储和链表类似,通过指针来存储数据和位置

不同点

树和线性表最大的不同就是,树形结构是一对多,而线性表则是一对一

由于链式树是最常用的树,下面以链式树和链表做对比

链表有多个节点,每个节点有两个存储位置:一个存储数据,另一个存储下一个节点的地址

而链式树也是多个节点,但是,链式树每个节点是多个存储位置,第一个存储数据,而另外的所有都是存储下一个节点的地址,也就是说,链式树的“下一个”节点有多个,如果“下一个”节点有且最多有2个,我们把这样的树称为二叉树

链式树图解

树的一些专属词 

节点(Node):将树结构拆分成不可再分的每一个最小结构,该结构称为节点。

根(root):最上面的那一个节点又被称为根节点,简称根

空树:当树结构不存在节点时,该树又被称为空树 

孩子节点:一个节点,如果他有后续节点,那么他的所有后续节点,都被称为他的孩子节点

父亲节点:同理,这样的节点又被称为:他所有孩子节点的父亲节点

兄弟节点:如果该节点和另外一个节点,他们有共同的父亲节点,他们他们互相称为兄弟节点

堂兄弟节点:如果该节点和另外一个节点,他们的父亲为兄弟节点,那么他们互相称为堂兄弟节点

爷爷节点,孙子节点等等一些,就像我们人际关系这么样来定义的。

度:一个节点的孩子节点个数,又被称为该节点的的度

树的度:所有节点中最大的的度,称为该树的度

叶子节点:度为0的节点称为叶子节点,就像树一样,树枝到头了就是叶子了。

分支节点:度不为0的节点称为分支节点,就像树枝分叉一样。

森林:由一个或多个或0个互不相交树结构,合起来称为森林结构

树的层次:从根开始,根为第一层,让他的子节点就是第二层,再子节点就是第三层....

树的高度:树的最大层次,被称为树的高度

树的宽度:树每一层中最多的节点数称为该树的宽度

所以,链式树是这么来定义的:

typedef struct TNode{
    char data;//数据域
    TNode* FirstChild;//指向第一个孩子节点
    TNode* SecondChild;//指向第二个孩子节点
    TNode* ThridChild;//指向第三个孩子节点
    TNode* FourthChild;//指向第四个孩子节点
    .....
    TNode* NthChild;//指向第n个孩子节点
}Tree;

树的分类 

根据分支数量

可分为:

二叉树:每一个节点最多拥有两个孩子节点,例如:搜索树,红黑树

三叉树:每一个节点最多拥有三个孩子节点

多叉树:每一个节点最多可拥有多余三个孩子节点

根据作用(或者说有序性)

无序树:父亲节点和孩子节点的数值(data)没有特定的关系

有序树:父亲节点和孩子节点的数值(data)有特定的关系,例如:搜索树:任意一个节点,他的data必须大于左孩子data,而小于右孩子data。排序树:任意一个节点,他的data必须大于所有子节点的data。

树的表示方式

孩子表示法

就和刚才一样,每个节点有多个指针域,每个指针指向某个孩子节点,若没有孩子节点,那么即为空指针(NULL)

typedef struct TNode{
    char data;//数据域
    TNode* FirstChild;//指向第一个孩子节点
    TNode* SecondChild;//指向第二个孩子节点
    TNode* ThridChild;//指向第三个孩子节点
    TNode* FourthChild;//指向第四个孩子节点
    .....
    TNode* NthChild;//指向第n个孩子节点
}Tree;

二叉树,三叉树即为这样的表示方法。

二叉树图解:

 

但是对于多叉树,这样来表示或许太麻烦了,需要一一的来列举,并且当数据量过大的时候,我们是无法做到枚举的。所以诞生了长子兄弟表示法和父亲兄弟表示法。

长子兄弟表示法

顾名思义,即每个节点有两个指针域,第一个指向长子节点,第二个指向兄弟节点

typedef struct TNode{
    char data;//数据域
    TNode* FirstChild;//指向第一个孩子节点(或者说长子节点)
    TNode* NextBrother;//指向下一个兄弟节点
}Tree;

如果说,他没有孩子节点,那么tree->FirstChild即为空指针(NULL)。同理,如果没有下一个兄弟,那么tree->NextBrother也为空指针(NULL)

长子兄弟表示法其结构美观,误差小。所以也是树的最常用的表示方法

父亲兄弟表示法

和长子兄弟法类似,每个节点有两个指针域,第一个指向父亲节点,第二个指向兄弟节点。

但是由于会有多个孩子节点指向同一个父亲,处理起来有时候比较麻烦,但不可否认,在特定情况下使用,效果可能比长子兄弟表示法好。