数据结构-树与二叉树

发布日期: 2023-10-07

更新日期: 2024-01-30

文章字数: 6.5k

树的定义和基本术语

树的定义：树是一种递归定义的数据结构，它包含一个根结点和若干个子树。当树的结点数为0时，称为空树；当树的结点数大于0时，除了一个特定的根结点外，其余的结点被分成m个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

1-1

非空树的特性：

有且仅有一个根节点。
没有后继的结点称为“叶子结点”（或终端结点）。
有后继的结点称为“分支结点”（或非终端结点）。
除了根结点外，任何一个结点都有且仅有一个前驱结点。
每个结点可以有0个或多个后继结点。

树结点之间的关系描述

1-2

根据1-2图可以得出结点之间的关系描述：

祖先结点：对于”你”结点到”爷爷”结点都是祖先结点，即结点的所有前驱结点为祖先结点。
子孙结点：对于”爷爷”结点，所有后继结点都是子孙结点，即对于一个结点所有后继结点都是子孙结点。
双亲节点（父结点）：对于”你”结点，”父亲”结点即为父结点，即对于一个结点的直接前驱结点为父结点。
孩子结点：对于”父亲”结点来说，”你“结点与”F”结点都是”父亲”结点的孩子结点，即对于一个结点的直接后继结点。
兄弟结点：对于”你”结点来说，”F”结点即是兄弟结点，即对于一个结点同属于一个直接前驱结点的结点则为兄弟结点。
堂兄弟结点：对于”你”结点来说，“F”、“G”、“H”、“I”、“J”都是堂兄弟结点，即对于一个结点属于同一层的结点都为堂兄弟结点。
两个结点之间的路径（从上往下）与路径长度：对于”爷爷”结点到“你”结点即为一条路径，且路径长度为2，即对于一个结点向下搜寻到一个结点，且经过的边数为路径长度。

结点、树的属性描述

1-3

根据1-3图可以得出结点、树的属性描述：

结点的层次（默认从1开始）（深度）：从上往下数，可得图1-3的深度为4。
结点的高度：从下往上数，以E为基点，结点高度为2，若以B为基点，结点高度为3。
树的高度（深度）：总共的层数，可得图1-3树的高度为4。
结点的度：根据有几个分支来定，若以B为基点，因有E，F两个分支，所以结点的度为2。以D为基点，有H，I，J三个分支，所以结点的度为3。
树的度：各结点的度的最大值，1-3图中结点的最大的度也就3，所以树的度就是3。
有序树和无序数：有序树在逻辑上看，树中结点的各子树从左往右是有次序的，不能互换。如1-2图，交换位置会导致意思发生变化。无
无序树在逻辑上看，树中结点的各子树从左往右是无次序的，可以互换，如1-3图，交换后意义并不会受到任何影响。

森林与树的概念

森林。森林是m(m>=0)（m=0则为空森林）棵互不相交的树的集合，如1-4所示。

1-4

而将所有森林中的所有树上加上一个根结点，则会又变成一个树的整体，如1-5所示。

1-5

树的性质

结点数 = 总度数+1，+1是加上根节点。
度为m的树与m叉树的区别：

度为m的树 1-6所示	m叉树 1-7所示
任意结点的度`<=m`（最多m个结点）	任意结点的度`<=m`（最多m个结点）
至少有一个结点度=m（有某个结点有m个直接后继结点）	允许所有结点的度都`<m`
一定是非空树，至少有m+1个结点	可以是空树

1-6

1-7

度为m的树第i层至多有$$m^{i-1}$$个结点$$i\geqslant 1$$，m叉树也同理

1-8

如1-8所示，因为度为m的树的性质为一个基点结点最多有m个结点，所以若为度为1的树，则至多有$$m^0$$个结点，若度为2，则至多有$$m^2$$个结点，以此类推。

高度为h的m叉树至多结点数

计算公式（等比数列求和，首项为1，公比为m）：
$$
\sum_{i=0}^{h-1}{m^i}=m^0 + m^1 + {\cdots} + m^{h-1} = \frac{m^{h}-1}{m-1}
$$
研究了一段时间才发现以上所用的等比数列求和不是常用的而是另外一个，上方结果是根据后面的公式得出,等比求和公式(q为公比)：
$$
S=\frac{a_1(1-q^n)}{1-q}=\frac{a_nq-a_1}{q-1}
$$

高度为h的m叉树至少结点数

高度为h的m叉树至少有h个结点，即每个结点只有一个直接后继结点。

高度为h、度为m的树至少有h+m-1个结点，由于度为m的树至少有一个结点的直接后继有m个，所以让其他结点都只有一个直接后继结点，加上有一个为m的结点然后再减去1即可得出。

1-9

具有n个结点的m叉树的最小高度

具有n个结点的m叉树的最小高度$$\log_m(n(m-1)+1)$$。

高度最小的情况–所有结点都有m个孩子，假设m叉树的高度为h，但没到最大结点树，可得公式：
$$
\frac{m^{h-1}-1}{m-1}<n\leqslant \frac{m^h-1}{m-1}
$$
同乘$$m-1$$，并同时$$+1$$得：
$$
m^{h-1}<n(m-1)+1\leqslant m^h
$$
对等式同时取对数$$\log_m$$得：
$$
h-1<\log_m(n(m-1)+1)\leqslant h
$$
所以对中间取整就可得m叉树的最小高度：
$$
h_{min} = \lceil \log_m(n(m-1)+1) \rceil
$$

二叉树

二叉树的基本概念

二叉树是n（$$n\geqslant 0$$）个结点的有限集合：

或者为空二叉树，即n=0。

或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。

二叉树特点：每个结点至多有两颗子树，左右子树不能颠倒（二叉树是有序树）。

几个特殊的二叉树

满二叉树

一颗高度为h，且含有$$2^h-1$$个结点的二叉树，即每个子树都有两个子分支。如图2-1所示

2-1

特点：

只有最后一层有叶子结点
不存在度为1的结点
按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1，结点i的父节点为[i/2]（[]为取整符号），即结点7的左孩子为2i=14，右孩子为2i+1=15，而父节点为[i/2]=3。

完全二叉树

当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点意义对应时，即可删除编号最后几位的结点，但最后一层仍然能从左往右编号且中间不会出现空结点，称为完全二叉树，若完全二叉树某结点只有一个后继结点那一定是左后继结点。如图2-2所示

2-2

特点：

只有最后两层可能有叶子结点
最多只有一个度为1的结点
按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1，结点i的父节点为[i/2]（[]为取整符号），即结点7的左孩子为2i=14，右孩子为2i+1=15，而父节点为[i/2]=3。
$$i\leqslant [n/2]$$为分支结点，$$i\geqslant [n/2]$$为叶子结点。

二叉排序树

具有以下性质的二叉树：

左子树上所有结点的关键字均小于根结点的关键字；

右子树上所有结点的关键字均大于根结点的关键字；

左子树和右子树又各是一颗二叉排序树。

2-3

平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。

2-4

二叉树的性质

若有一颗非空二叉树中度为0、1和2的结点个数分别为$$n_0 、n_1、n_2$$，则$$n_0 = n_2 + 1$$（$$n_0$$叶子结点比$$n_2$$二分支结点多一个）。
二叉树第i层至多有$$2^{i-1}$$各结点。
高度为h的二叉树至多有$$2^h-1$$个结点（满二叉树）。

完全二叉树的性质

具有n个（n > 0）结点的完全二叉树的高度h为$$[log_2(n+1)]$$或$$[log_2n]+1$$

推导过程：

设高为h的满二叉树共有$$2^h-1$$个结点，高为h-1的满二叉树共有$$2^{h-1}-1$$个结点，则有：
$$
2^{h-1}-1<n\leqslant 2^h-1
$$
加+1得：
$$
2^{h-1} < n+1 \leqslant 2^h
$$
再取$$\log_2$$：
$$
h-1<\log_2(n+1) \leqslant h
$$
则对$$\log_2(n+1)$$向上取整得$$[log_2(n+1)]$$。

另一个式子推导过程：

高为h-1的满二叉树共有$$2^{h-1}-1$$个结点，高为h的完全二叉树至少$$2^{h-1}$$个结点，至多有$$2^h-1$$。

则有：
$$
2^{h-1}\leqslant n < 2^h
$$
取$$log_2$$得：
$$
h-1\leqslant \log_2n<h
$$
得$$h=[log_2n+1]$$。

对于完全二叉树，可以由结点数n推出度为0、1和2得结点个数为$$n_0 、n_1、n_2$$。

完全二叉树最多只有一个度为1的结点，即$$n_1=0或1$$。

$$n_0=n_2+1->n_0+n_2$$一定是奇数。

二叉树的存储结构

二叉树的顺序存储

即用线性表来存储二叉树。

#define MaxSize 100
struct TreeNode{
    ElemType value; //结点中的数据元素
    bool isEmpty; //结点是否为空
}

顺序存储比较适合完全二叉树，其他类型会导致存储空间浪费

顺序存储的几个基本操作：

查询第i个结点的左后继结点：2i
查询第i个结点的右后继结点：2i+1
查询第i个结点的父节点：**[i/2]**
查询第i个结点的层次：$$[log_2(n+1)]$$或$$[log_2n]+1$$

二叉树的的链式存储

即用链表来存储二叉树。

#define ElemType int
typedef struct BiTNode{
    ElemType data;  //数据域
    struct BiTNode *lchild,*rchild;  //左右孩子指针
}BiTNode,*BiTree;

在含有n个结点的二叉链表中，含有n+1个空链表。

二叉树链式操作基本实现（以二叉排序树为例）

插入一个结点

bool InsertBiTNode(BiTNode *root, ElemType e)
{
  // 通过递归来找要插入的结点
  //  若要插入的数大于根结点，则放在右子树
  if (e > root->data)
  {
    if (root->rchild == NULL)
    {
      BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
      if (p == NULL)
        return false;
      p->data = e;
      p->lchild = NULL;
      p->rchild = NULL;
      root->rchild = p;
      return true;
    }
    else
    {
      InsertBiTNode(root->rchild, e);
    }
  }
  else if (e < root->data)
  {
    if (root->lchild == NULL)
    {
      BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
      if (p == NULL)
        return false;
      p->data = e;
      p->lchild = NULL;
      p->rchild = NULL;
      root->lchild = p;
      return true;
    }else{
      InsertBiTNode(root->lchild, e);
    }
  }
  else
  {
    return false;
  }
}

二叉树的遍历

二叉树的先中后序遍历

先序遍历：先访问根节点，再访问左节点，最后访问右结点。

中序遍历：先访问左节点，再访问根节点，最后访问右节点。

后序遍历：先访问左结点，在访问右节点，最后访问根节点。

先序遍历代码实现

// 先序遍历 访问顺序为根左右
void PreOrder(BiTNode *B)
{
  if (B != NULL)
  {
    visitNode(B);        // 访问结点并进行操作
    PreOrder(B->lchild); // 递归左节点
    PreOrder(B->rchild); // 递归右结点
  }
}

中序遍历代码实现

// 中序遍历 访问顺序为左根右
void InOrder(BiTNode *B)
{
  if (B != NULL)
  {
    InOrder(B->lchild); // 递归左节点
    visitNode(B);        // 访问结点并进行操作
    InOrder(B->rchild); // 递归右结点
  }
}

后序遍历代码实现

// 后序遍历 访问顺序为左右根
void PostOrder(BiTNode *B)
{
  if (B != NULL)
  {
    PostOrder(B->lchild); // 递归左节点
    PostOrder(B->rchild); // 递归右结点
    visitNode(B);        // 访问结点并进行操作
  }
}

层次遍历

层次遍历是从上到下按照层来对二叉树进行遍历，如图3-1所示。

3-1

层次遍历的代码实现

要进行层次遍历，需要借助一个队列。首先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。完成入队后出队，访问出队结点，如此反复，直至队列为空。

// 层次遍历 按层访问
void LevelOrder(BiTNode *B){
  SqQueue *Q;
  //获取出队元素
  BiTNode *popEl;
  Q = InitSqQueue(); //初始化队列
  //将根节点入队
  EnSqQueue(Q,B);
  while (!SqQueueEmpty(Q))
  {
    popEl =  PopSqQueue(Q);
    //出队后访问元素
    visitNode(popEl);
    //若左节点不为空将左结点入队
    if(popEl->lchild !=NULL)
      EnSqQueue(Q,popEl->lchild);
    //若右节点不为空将右结点入队
    if(popEl->rchild !=NULL)
    EnSqQueue(Q,popEl->rchild);
  }
  
}

由遍历序列构造二叉树

想通过遍历序列来构造二叉树必须包含中序遍历，才能确定构造出唯一的二叉树，总共的构造方法有：

前序+中序遍历序列构造
后序+中序遍历序列构造
层序+中序遍历序列构造

前序+中序遍历序列构造

前序遍历是根左右，所以前序的第一个结点一定是根节点，然后就可以根据中序结点来找出根结点的左右子树有哪些，从而构造出二叉树。

例：

前序遍历序列为：A D B C E

中序遍历序列为：B D C A E

由前序可知A为根节点，再由中序得知左子树由BDC构成，右子树仅有E。

再看左子树的BDC，由于在前序结点中D在B之前D为左子树的根结点，B为左结点，C为右结点就成功构造出了唯一的二叉树。

4-1

后序+中序遍历序列构造

后序遍历是左右根顺序，所以后序遍历的最后一个结点一定是根结点，然后再根据中序结点来寻找左右子树。

例：

后序遍历序列： E F A H C I G B D

中序遍历序列： E A F D H C B G I

根据后序可得根结点为D，再根据中序可得左子树元素由EAF，右子树元素有HCBGI。

对EAF进行拆分，根据后序可得A在最后方说明A为根节点，再根据中序E为左子树，则F为右子树，就可获得完整的左子树。

对HCBGI进行拆分，由后序可得根结点为B，再根据中序可得左子树为HC，右子树为GI。

在对HC进行拆分，由后序可得C为根节点，再根据中序得，H为左子树。

最后对GI进行拆分，由后序可得G为根节点，再根据中序可得，I为右子树。即可构造出唯一二叉树。

4-2

层序+中序遍历序列构造

后序遍历是从上往下根据层顺序，所以层序遍历的第一个结点一定是根结点，然后再根据中序结点来寻找左右子树。

例：

层序遍历序列： A B C D E

中序遍历序列： A C B E D

根据层序可得A为根节点，再由中序可得左子树为空，右子树有CBED。

分析CBED，由层序得B为根节点，中序得C为以B为根节点的左子树，ED则为右子树。

分析ED，由层序得D为根节点，中序得E为D的左子树。最后成功构造唯一二叉树。

4-3

线索二叉树

线索二叉树的基本概念

线索二叉树就是在传统二叉树上添加直接前驱和直接后继指针，来使二叉树能更块的查找到结点的前驱和后继。通过ltag和rtag来表示是否存在左右结点，当ltag==1时表示lchild指向前驱结点，ltag==0时表示lchild指向左孩子，rtag同理。

线索二叉树的存储结构

typedef struct ThreadNode{
  ElemType data;  //数据元素
  struct ThreadNode *lchild, *rchild;  //左、右孩子指针
  int ltag,rtag;  //左、右线索标志
}ThreadNode;

中序线索二叉树的构造

二叉树的线索化使将二叉链表中的空指针改为指向前驱或后继的线索。因此线索化就是要在遍历的时候进行。

代码实现

// 通过中序遍历对二叉树进行线索化
void InThread(ThreadNode *p, ThreadNode **pre)
{
  if (p != NULL)
  {
    InThread(p->lchild, pre);
    //中序遍历线索化处理部分
    if (p->lchild == NULL)
    {
      p->lchild = *pre;
      p->ltag = 1;
    }
    if (*pre != NULL && (*pre)->rchild == NULL)
    {
      (*pre)->rchild = p;  //建立前驱结点的后继线索
      (*pre)->rtag = 1;
    }
    *pre = p;
    //中序遍历线索化结束
    InThread(p->rchild, pre);
  }
}
//在此调用
void CreateInThread(ThreadNode *T)
{
  ThreadNode *pre = NULL;
  if (T != NULL)
  {
    InThread(T, &pre);
    //中序遍历最后一个结点肯定没有右孩子，所以直接设为null
    pre->rchild = NULL;
    pre->rtag = 1;
  }
}

先序和后序线索化逻辑类似就不再过多赘述。

树、森林

树的存储结构

树的存储方式有多种，即可采用顺序存储结构，又可采用链式存储，这里介绍3种常用的存储结构。

双亲表示法（顺序存储）

这种存储结构采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。

5-1

将图5-1以双亲表示法存储到内存中应以图5-2形式来存储。

5-2

除了根结点指向-1外，其余parent都应指向父节点的数组下标。

存储结构描述：

//树的结点定义
typedef struct{
  ElemType data; //数据元素
  int parent; //双亲位置域
}PTNode;

//树类型定义
typedef struct{
  PTNode nodes[MAX_TREE_SIZE]; 
  int n; //结点数量
}PTree;

孩子表示法（顺序+链式存储）

孩子表示法是将每个结点的孩子结点都用单链表连接起来形成一个线性结构，此时n个结点就有个孩子链表。

将图5-1的树来用孩子表示法存储就可得图5-3。用一个firstChild链表来存储结点的第一个孩子结点，后可通过第一个孩子来找到后序结点。

5-3

存储结构描述：

//孩子表示法
typedef struct CTNode{
  int child; //孩子结点在数组中的位置
  struct CTNode *next; //下一个孩子结点
}CTNode;

typedef struct{
  ElemType data;
  CTNode *firstChild; //第一个孩子
}CTBox;

孩子兄弟表示法（链式存储）

又称二叉树表示法，即以二叉链表作为树的存储结构。共包含三部分内容：结点值、指向结点第一个孩子结点的指针，以及指向结点下一个兄弟结点的指针。

存储结构描述：

//孩子兄弟表示法
typedef struct CSNode{
  ElemType data;
  struct CSNode *firstchild,*nextsibling; //左指针指向第一个孩子，右指针指向该结点的兄弟结点
}CSNode;

树、森林与二叉树的转换

由于二叉树和树都可以用二叉链表作为存储结构，因此二叉链表作为媒介可以将树和二叉树进行转换。

树转换成二叉树的规则：

每个结点左指针指向它的第一个孩子，右指针指向它在树中相邻右兄弟（孩子兄弟表示法）。

森林转二叉树也是同理，不过不像树根节点没有兄弟，根结点的兄弟就是相邻的树。

二叉树转成树的规则：

从树的根节点根据树的层序来恢复，若有左孩子代表是树的第一个孩子结点，若有右节点，代表是树的第一个孩子结点的兄弟结点，以此类推。

由于树的深度遍历和广度遍历与二叉树的先序遍历和中序遍历相似就不再过多赘述

树与二叉树的应用

哈夫曼树和哈夫曼编码

哈夫曼树的定义

结点的权：有某种现实意义的数值称为结点的权。

结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积。如图6-1到权值为3的带权路径长度为$$3*3=9$$的。

树的带权路径长度：树中所有叶结点的带权路径之和（WPL,Weighted Path Length）。
$$
WPL = \sum^n_{i=1}w_il_i
$$

6-1

在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最优二叉树。

哈夫曼树的构造

给定n个权值的结点，构造哈夫曼树的算法如下：

将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
构造一个新结点，从F中选取两棵根结点权值最小的数作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根节点的权值之和。
从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
重复2、3步骤，直到F中只剩下一棵树为止。

例：

6-2

将6-2中权值最小的两个结点（a和c或a和e）合成一个树，并将合成结点的权值相加作为根节点的权值，即到图6-3。

6-3

然后再将合成的树与新的权值最小的结点进行组合，获得一个新树。

6-4

如此往复即可合成一个哈夫曼树。

6-5

注：

每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
哈夫曼树的结点总数为2n-1。
哈夫曼树中不存在度为1的结点。
哈夫曼树并不唯一，但带权路径长度WPL必然相同且最优。

哈夫曼编码

在数据通信中为了更高效的传播数据，可使用可变长度编码来对频率高的字符赋以短编码，而对频率低的字符用长编码，起到压缩数据的效果。而在这中就可以使用哈夫曼树来进行编码。

例：

假设有1组A,B,C,D需要传播，且A出现10次，B出现8次，C出现80次，D出现2次。此时A的权值就是10，B的权值为8，C的权值为80，D的权值为2。就可以根据权值来构造哈夫曼树，来寻求WPL最优，由此可以构造出图6-6的哈夫曼树，并将左子树路径设为0，右子树设为1。

6-6

则若想要传播数据A、B、C、D相应的二进制为：

A:10 B:111 C:0 D:110。

即可完成数据传送，且$$WPL=801+102+32+83=130$$。

并查集

并查集是一种简单的集合表示。它支持以下三种操作：

Initial(S)：将集合S中的每个元素都初始化为只有一个单集合的子集合。
Union(S,Root1,Root2)：把集合S中的Root2并入子集合Root1。
Find(S,x)：查找集合S中单元素x所在的子集合，并返回集合的根结点。

并查集可以使用树的双亲表示法，用双亲表示法可以很好的找到元素属于哪个集合和合并集合。并查集本身用一个int[]即可实现。

并查集的结构定义如下：

#define SIZE 100
int UFSets[SIZE];

在UFSets[SIZE]集合中根节点和结点数通过负数来进行表示。

例：$$S_1={0,6,7,8}\quad S_2={1,4,9}\quad S_3={2,3,5}\quad$$

使用UFSets[SIZE]来表示则为[-4,-3,-3,2,1,2,0,0,0,1]。

集合中的元素为数组的下标，而数组的实际内容为集合的双亲。UFSETS[0]的-4则代表集合1中有4个元素且为根结点，UFSETS[1]的-3代表集合2有3个元素且为根节点，以此可以推出所有结点所在的位置。

Find操作：

// 传入的x为元素，即并查集中的数组下标
int Find(int S[], int x)
{
  while (S[x] >= 0)
    x = S[x];
  return x;
}

Union操作：

// 将两树合并，并横向合并不增加树的高度 root为数组下标
void Union(int S[], int Root1, int Root2)
{
  if(Root1==Root2) return;
  
  if (S[Root2] > S[Root1]) //Root2结点数更少
  {
    S[Root1]+=S[Root2]; //累加结点数
    S[Root2] = Root1; //小树合并到大树 将S数组中Root1的下标值赋值给S[Root2]
  }else{
    S[Root2]+=S[Root1]; //累加结点数
    S[Root1] = Root2; //小树合并到大树 将S数组中Root2的下标值赋值给S[Root1]
  }
}

对Find操作进行优化

对于长度过长的树，可以进行压缩路径来使树的高度不超过O(a(n))。a(n)是一个增长很缓慢的函数。

压缩路径具体实现：先通过循环找到根节点，后将所有搜索经过的结点都指向根节点即可。

6-7

代码实现：

//x为数组下标 
int Find(int S[],int x){
    int root = x;
    while(S[root]>=0) //循环找到根
        root = S[root];
   while(x!=root){ //压缩路径
       int t = S[x]; //保存x的父节点
       S[x] = root; //将x直接挂到根节点下
       x = t;
   }
    return root;
}

LsWorld

http://example.com/2023/10/07/shu-ju-jie-gou-shu-yu-er-cha-shu/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 LsWorld !

数据结构

电路-电阻电路的等效变换

2023-10-10 电路

电路

数据结构-串

2023-10-05 数据结构

数据结构串

数据结构-树与二叉树

树的定义和基本术语

树结点之间的关系描述

结点、树的属性描述

森林与树的概念

树的性质

度为m的树与m叉树的区别：

度为m的树第i层至多有$$m^{i-1}$$个结点$$i\geqslant 1$$，m叉树也同理

高度为h的m叉树至多结点数

高度为h的m叉树至少结点数

具有n个结点的m叉树的最小高度

二叉树

二叉树的基本概念

几个特殊的二叉树

满二叉树

完全二叉树

二叉排序树

平衡二叉树

二叉树的性质

完全二叉树的性质

二叉树的存储结构

二叉树的顺序存储

二叉树的的链式存储

二叉树链式操作基本实现（以二叉排序树为例）

二叉树的遍历

二叉树的先中后序遍历

先序遍历代码实现

中序遍历代码实现

后序遍历代码实现

层次遍历

层次遍历的代码实现

由遍历序列构造二叉树

前序+中序遍历序列构造

后序+中序遍历序列构造

层序+中序遍历序列构造

线索二叉树

线索二叉树的基本概念

中序线索二叉树的构造

树、森林

树的存储结构

双亲表示法（顺序存储）

孩子表示法（顺序+链式存储）

孩子兄弟表示法（链式存储）

树、森林与二叉树的转换

树与二叉树的应用

哈夫曼树和哈夫曼编码

哈夫曼树的定义

哈夫曼树的构造

哈夫曼编码

并查集

对Find操作进行优化