[数据结构——lesson8.树]

引言

学习目标

1.树的概念及结构

1.1树的定义

1.2树的基本概念

1.3 树的表示

(1)双亲表示法

(2)孩子表示法

(3)左孩子右兄弟表示法

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

结束语：

引言

之前我们学习了栈和队列数据结构，接下来我们学习一种新的数据结构——树

学习目标

为什么要学习为什么要学习非线性结构 ---- 树（Tree）
数的定义和基本概念
树的表示
树的实际应用
树的性质

为什么要学习非线性结构 ---- 树（Tree）

线性结构的优缺点

在线性结构中，无论是顺序存储，还是链式存储，线性表均有其优缺点：

顺序表优点：
1：顺序存储可以在 O(1) 的时间内找到特定次序的元素（下标的随机访问）
2：CPU 高速缓存，命中率较高
顺序表缺点：
1：顺序存储在，数据中间、头部的插入和删除元素需要挪动大量元素，需要时间O(n)
2: 顺序存储时，会出现空间不足，只能进行空间的扩容（异地扩容代价比较大）

链表优点：
1：在任意位置进行数据的插入和删除的效率高，所需时间为O(1)
2: 按需申请空间和释放，不存在扩容
链表的缺点：
1：在寻找特定次序的元素需要从链表头部向后查找，需要时间O(n)
2： CPU高速缓存，命中率低

其实链表和顺序表是一个互补的数据结构

优化方案 ----- 树（Tree）

树形结构：很好的结合了顺序表和链表的优点，可以在O(logn)的时间内完成查找、更新、插入、删除等操作，在实际的应用中，很多算法可以借助于树形结构高效的实现很多功能。

树的讲解流程

此时此刻大家肯定很想了解什么是树，在本篇博客中，并不能把所有树的结构在此篇文章中进行详细的介绍，我会通过步步延申的方式去讲解树。
树 ➡ 二叉树➡ 搜索二叉树 ➡ 平衡搜索二叉树 (AVL树和红黑树) ➡ M叉多叉平衡搜索树 (B树和B+树)

1.树的概念及结构

1.1树的定义

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

为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

有一个特殊的结点，称为根结点，根结点没有前驱结点
除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
因此，树是递归定义的。

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

1.2树的基本概念

我们根据这棵树来介绍一下树的基本概念

节点的度：一个节点含有的子树的个数称为该节点的度，比如说节点1的度为2
叶节点或终端节点：度为0的节点，比如说4，5，6节点
非终端节点或分支节点：度不为0的节点，比如说2，3节点
双亲结点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。比如说2是4，5的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点，比如说4，5是 2的子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点，比如说4，5就是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度，比如说上面这棵树的度为2
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
树的高度或深度：树中节点的最大层次，比如说上面这棵树的高度为3
堂兄弟节点：双亲在同一层的节点互为堂兄弟，比如说5，6节点
节点的祖先：从根到该节点所经分支上的所有节点，比如说1就是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙，比如说所有节点都是1的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林

1.3 树的表示

我们有三种方法表示上面这棵树：

(1)双亲表示法

双亲表示法是用顺序表，也就是数组对树进行表示的。即用顺序表存储各个节点的数据，并且同时存储其双亲节点的下标。

注意：根节点没有双亲节点，所以特别记为-1。

声明如下：

如下图所示：

存储方式如下：

说明：

因为根节点没有父节点，将其父节点数组下标设置为-1，根节点存储在顺序表的第1个位置。
数据元素2、3、4的父节点为0，父节点数组下标为0，分别存储在顺序表的2、3、4个位置。
数据元素5、6的父节点为1，父节点数组下标为1，分别存储在顺序表的第5、6个位置。
数据元素7的父节点为3，父节点数组下标为3，存储在顺序表的第7个位置。

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10
typedef int DataType;
typedef struct TreeNode
{DataType data;int parent;
}Node;typedef struct ParentTree
{// 数据结构的树节点Node Tnode[MAXSIZE];int n;		//当前节点个数
}Ptree;// 初始化树
void TreeInit(Ptree* ptree, int x, int parentIndex) 
{if (ptree->n >= MAXSIZE) {printf("Tree is full!\n");return;}ptree->Tnode[ptree->n].data = x;ptree->Tnode[ptree->n].parent = parentIndex;ptree->n++; // 增加节点计数  
}

双亲表示法的特点：

优点：快速查找一个结点的父结点（直接通过parent字段获取），结构简单，空间开销小（仅需存储值和一个索引）。
缺点：查找子结点时效率低（需遍历整个数组，判断哪些结点的parent等于当前结点的索引），不适合频繁查找子结点的场景。

(2)孩子表示法

树的孩子表示法就是采用顺序表与链表结合的形式，用顺序表存储树的值与链表的头节点，而链表的头节点存储其孩子节点在顺序表中的下标，若没有则记为空(NULL)。

相当于对树进行这样的处理：

存储方式如下：

说明：

添加一个数据（插入一个结点）

既要在数组中依次添加新的数据。
也要在其父节点后面用头插法插入。

优缺点：

优点：简单且易于理解，适用于需要频繁查找孩子节点的应用场景。
缺点：不容易直接获取节点的父节点。

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 10
typedef int DataType;
typedef struct ListNode
{int index;struct ListNode* next;
}ListNode;typedef struct TreeNode
{DataType data;ListNode* child;
}TNode;typedef struct Tree
{TNode nodes[MAXSIZE];int n;
}Tree;// 创建一个新的ListNode  
ListNode* createListNode(int index) 
{ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (newNode == NULL){perror("malloc fail:");exit(0);}newNode->index = index;newNode->next = NULL;return newNode;
}// 初始化树  
void TreeInit(Tree* t, DataType x) 
{if (t->n >= MAXSIZE) {printf("Tree is full!\n");return;}t->nodes[t->n].data = x;t->nodes[t->n].child = NULL;  t->n++;
}// 向节点的子链表中添加一个新节点  
void InsertChild(Tree* t, int parentIndex, int childIndex)
{if (parentIndex >= t->n || childIndex >= t->n) {printf("error\n");return;}ListNode* newNode = createListNode(childIndex);if (newNode == NULL){perror("malloc fail:");return; // 内存分配失败  }newNode->next = t->nodes[parentIndex].child;t->nodes[parentIndex].child = newNode;
}

(3)左孩子右兄弟表示法

最常用表示树的的方法就是左孩子右兄弟表示法，即定义两个指针，让左指针指向子节点，右指针指向兄弟节点。如果没有节点，则都指向空（NULL）。

如图所示：

基本原理：在这种表示法中，每个节点包含一个数据域和两个指针域。其中一个指针指向该节点的第一个孩子节点（左孩子），另一个指针指向该节点的下一个兄弟节点（右兄弟）。通过这种方式，可将任意一棵多叉树转化为一棵二叉树来表示。

节点定义：在 C++ 中，可按如下方式定义节点结构：

代码如下：

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;typedef struct TreeNode
{DataType data;struct TreeNode* leftChild;  // 指向左孩子  struct TreeNode* rightBro; // 指向右兄弟  
} TNode;// 创建一个新的树节点
TNode* createTreeNode(DataType x)
{TNode* newNode = (TNode*)malloc(sizeof(TNode));if (newNode == NULL){perror("malloc fail:");exit(0);}newNode->data = x;newNode->leftChild = NULL;newNode->rightBro = NULL;return newNode;
}void InsertChild(TNode* t, DataType x, int isLeftChild) 
{if (t == NULL) {printf("Cannot insert into NULL node\n");return;}TNode* newNode = createTreeNode(x);if (newNode == NULL) {return;}// 如果isLeftChild为1，表示新节点应该作为左孩子插入  if (isLeftChild) {// 如果当前节点还没有右兄弟，则直接将新节点设置为右兄弟if (t->leftChild == NULL) {t->leftChild = newNode;}// 如果当前节点已经有左孩子，则遍历左孩子的右兄弟链表// 找到最后一个右兄弟，并将新节点插入为它的下一个右兄弟else {TNode* tmp = t->leftChild;while (tmp->rightBro != NULL) {tmp = tmp->rightBro;}tmp->rightBro = newNode;}}// 如果isLeftChild为0，表示新节点应该作为右兄弟插入else{// 如果当前节点还没有右兄弟，则直接将新节点设置为右兄弟if (t->rightBro == NULL) {t->rightBro = newNode;}// 如果当前节点已经有右兄弟，则遍历右兄弟链表// 找到最后一个右兄弟，并将新节点插入为它的下一个右兄弟else {TNode* tmp = t->rightBro;while (tmp->rightBro != NULL) {tmp = tmp->rightBro;}tmp->rightBro = newNode;}}
}

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

在linux环境下目录结构就是有一颗树构成，而在Windows环境下，目录许多内容并不交叉，所以是由森林构成。

树的性质（重点）

性质1：树中的节点数等于所有节点度数加 1
从上图可知，有 12 个节点，A的度为：3， B的度为2， C 的度为1， D的度为2， E的度为1， F的度为0， G的度为2， H的度为0 ， I的度为0，J的度为0，K的度0，L的度为0。

由性质 1 可知树的节点个数 = 每个节点的度数 + 1

所以上图树的节点数 = （3+2+1+2+1+0+2+0+0+0+0+0）+1 = 12

性质2：度为 m 的树中第 i 层至多有 m^i-1 个节点（i>=1）

性质3：高度为 h 的 m 叉树至多有 m^h-1/m-1 个节点

性质4：具有n个结点的m叉树的最小高度为⌈logm(n*(m-1)+1)⌉