2020-07-26

作者: 未时日 | 来源:发表于2020-07-26 18:07 被阅读0次

1.树的概念

1.1 树的定义

自由树：
$T_{f} = (V, E)$ $(V=\{v_{21}, v_{2}, ...v_{n}\}$ $E=\{(v_{i}, v_{j})|v_{i},v_{j}\in V, 1 \leq i,j \leq n \})$ ，其中，集合 $E$ 的元素个数为 $n-1$ , $(v_{i}, v_{j})$ 称为边或分支, $T_{f}$ 为连通图
有根树:
$T=\begin{cases}\phi,\qquad n=0\\ \{r,T1, T2, T3,...,T_{m}\}, \qquad n>0 \end{cases}$
$n=0$ 时称为空树， $T_{1},T_{2},...T_{m}$ 称为子树
根节点没有前驱，除此之外每个节点有且只有一个前驱；所有节点有零个或多个后继
目录结构、集合文氏图、凹入表表示、广义表表示

1.2 常见术语

结点：包含数据项和其他结点的分支
度：拥有子树的个数,树的度是结点的最大度
叶结点：度为0的点，终端结点
分支节点：除叶结点以外的点，非终端节点
子女节点：若结点 $x$ 有子树，子树的根结点即 $x$ 的子女
父结点：结点 $x$ 为其子女结点的父结点
兄弟结点：同一父结点的子女护卫兄弟
祖先结点：对结点 $x$ ，根结点到这个结点唯一路径上的任意结点
子孙结点：子女结点的子女
层次：根到该结点的子树个数，记根结点为层次为1，子结点层次为父结点加1
深度：最远结点的层次，空树为0，自顶向下
高度：叶结点高度为1，其父结点的高度为最高子女高度+1，树的高度为根结点高度，自底向上，数值上与深度相等。
有序树、无序树：各棵子树能够交换，例如有序树中 $T_{1}, T_{2}...$ 被称为第一棵子树、第二棵子树...
森林： $m \geq0$ 棵互不相交的树，树 $\to$ 森林：删去一棵非空树的根结点（空森林也是森林）森林 $\to$ 树：增加一个结点，让每一棵树的根结点都称为这个结点的子女结点

1.3 树的性质

结点数等于度数和加1
度为 $m$ 的树第 $i$ 层至多有 $m^{i-1}个结点$
高度为 $h$ 的 $m$ 叉树（度为 $m$ )至多有 $\sum_{i=1}^hm^{i-1}=\frac{(m^{h}-1)}{(m-1)}$
设度为 $m$ 的树（ $m$ 叉树）结点个数为 $n$ ,由上一个性质，我们推出：
$\begin{gathered} n \leq\,\frac{(m^{h}-1)}{m-1}\\ \qquad h \geq \lceil\log_{m}(n(m-1)+1)\rceil \end{gathered}$

2.二叉树

2.1 二叉树定义

$T= \begin{cases} \phi \qquad n=0\\ \{r, \,T_{l}, \,T_{r} \} \qquad n \geq 1 \end{cases}$
树的度至多为2（即最多两个子女结点），左右子树能交换（有序的）

2.2 二叉树的性质

第 $i$ 层至多 $2^{i-1}$ 个结点
高为 $k$ 至多 $2^{k}-1$ 个结点，至少 $k$ 个结点（每层一个）
考虑两个等式:
$\begin{gathered} n = n_{0} + n_{1} + n_{2} \\ e = n-1 = n_{1} + 2 * n_{2} \end{gathered}$
故有: $n_{0} = n_{2} +1$
满二叉树：每一层都达到最大结点个数；完全二叉树：每一个结点都与具有相同高度的满二叉树对应（上面 $k-1$ 层是满的，仅第 $k$ 层从右向左却若干个)
$n$ 个结点的完全二叉树最小深度为 $\lceil \log(n+1)\rceil$
对于完全二叉树，编号为 $1,2,3...n$ ,结点 $i$ 的父结点编号为 $\lfloor\frac{n}{2}\rfloor$ ,结点 $i$ 的左子女结点为 $2*i$ ,右子女结点为 $2*i+1$ ，(检查结点是否超过 $n$ ),深度 $\lfloor\log(i)\rfloor + 1$

3.二叉树存储

3.1 二叉树数组表示

适用场景：二叉树大小和形态不发生剧烈动态变化
将二叉树存储在一组连续的存储单元（即数组内），要体现树的逻辑结构。
完全二叉树数组存储：自顶向下，自左向右顺序编号为 $1,2,3,4...,n$ ,按照这个序列把完全二叉树放入一维数组中（根结点在索引为 $1$ 处）。这种方式最简单、最省存储空间
一般二叉树存储：仿照完全二叉树编号，遇到空子树时假定有子树编号。这样的做法会浪费存储空间（eg.只有右子树）

3.2 二叉树的链表表示

适用一般二叉树，变化剧烈
二叉树的每一个结点可以有两个分支，分别指向左、右子树，因此至少有三个域，分别存放结点的数据、左右子女结点指针。很方便的找到子女结点，但找到父结点很困难
为了找到父结点，可以再加一个父指针域，称为三叉链表
对于 $n$ 个结点的二叉链表中，共有 $2*n$ 个指针域，由于二叉树中共有 $n -1$ 条边，故二叉链表中有 $n+1$ 个空指针域，同理，三叉链表中有 $n+2$ 个空指针域（根结点的父结点域为空）
这两种链表形式都可以是静态链表结构，即把链表存放在一个一维数组中，每个一维数组元素是一个结点，包括三个域：数组域、左子女域、右子女域，还可以增加父指针域，指针域指向数组中的下标：
```
                   A
                  /  
                 B
                / \
               C   D
                  /
                 E
```
index data Parent LeftChild RightChild

0 A -1(root) 1(B) -1(NULL)

1 B 0(A) 2(C) 3(D)

2 C 1(B) -1(NULL) -1(NULL)

3 D 1(B) 4(E) -1(NULL)

4 E 3(D) -1(NULL) -1(NULL)

index	data	Parent	LeftChild	RightChild
0	A	-1(root)	1(B)	-1(NULL)
1	B	0(A)	2(C)	3(D)
2	C	1(B)	-1(NULL)	-1(NULL)
3	D	1(B)	4(E)	-1(NULL)
4	E	3(D)	-1(NULL)	-1(NULL)

4.二叉树的遍历及应用

概述

二叉树遍历是指遵从某种次序，遍历二叉树中所有的结点，使得每个结点访问且只访问一次，且不破坏树的数据结构,产生的结构是一个线性队列。
考虑自身、左右三个结点的顺序，总共的遍历方式有 $A_{3}^{3}= 6$ 种，规定先左后右，共有三种方式。常见的遍历方式有先序（NLR）、中序（LNR）、后序（LRN）三种。

三种遍历算法

递归访问

/*先序遍历*/
void PreOrder(BiTNode* T){
  if(T!=NULL){
    visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
  }
}
/*中序遍历*/
void InOrder(BitNode* T){
  if(T!=NULL){
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
  }
}
/*后序遍历*/
void PostOrder(BitNode* T){
  if(T！=NULL){
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T);
  }
}

先序非递归遍历

2020-07-26

1.树的概念

1.1 树的定义

1.2 常见术语

1.3 树的性质

2.二叉树

2.1 二叉树定义

2.2 二叉树的性质

3.二叉树存储

3.1 二叉树数组表示

3.2 二叉树的链表表示

4.二叉树的遍历及应用

概述

三种遍历算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读