数据结构第六章要点归纳

1.树的基础知识点

1.1 树的相关概念

结点拥有的子树数称为节点的度（Degree）。
度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支节点。
除根节点之外，分支节点也称为内部结点。
树的度是树内部各结点的度的最大值。
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
森林是 $m (m \geq 0)$ 棵互不相交的树的集合。

1.2 树的存储结构

双亲表示法
孩子表示法
孩子兄弟表示法

1.3 二叉树的相关概念

斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都只有右子树的二叉树叫右斜树。这二者统称为斜树。
满二叉树：在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为 $i (1 \leq i \leq n)$ 的节点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
完全二叉树的特点：

（1）叶子结点只能出现在最下两层。

（2）最下层的叶子一定集中在左部连续位置。

（3）倒数二层，若有叶子结点，一定都在右部连续位置。

（4）如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。

（5）同样结点数的二叉树，完全二叉树的深度最小。

1.4 二叉树的存储结构

顺序存储结构
二叉链表

2.二叉树5个基本性质及灵活应用

二叉树的定义：二叉树(Binary Tree)是n(n≥0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

2.1 性质1

在二叉树的第i层上至多有 $2^{i - 1}$ 个结点（ $i \geq 1$ ）。

2.2 性质2

深度为k的二叉树至多有 $2^{k} - 1$ 个结点（ $k \geq 1$ ）。

2.3 性质3

对任何一棵二叉树T，如果其终端结点数为 $n_{0}$ ，度为2的结点数为 $n_{2}$ ，则 $n_{0} = n_{2} + 1$ 。

2.4 性质4

具有n个结点的完全二叉树的深度为 $⌊ l o g_{2} n ⌋ + 1$ （ $⌊ x ⌋$ 表示不大于x的最大整数）。

2.5 性质5

如果对一棵有 $n$ 个结点的完全二叉树（其深度为 $⌊ l o g_{2} n ⌋ + 1$ ）的结点按层序编号（从第1层到第 $⌊ l o g_{2} n ⌋ + 1$ 层，每层从左到右），对任一结点 $i (1 \leq i \leq n)$ 有：

如果 $i = 1$ ，则节点 $i$ 是二叉树的根，无双亲；如果 $i \geq 1$ ，则其双亲是节点 $⌊ \frac{i}{2} ⌋$ 。
如果 $2 i > n$ ，则结点 $i$ 无左孩子（结点i为叶子节点）；否则其左孩子是结点 $2 i$ 。
如果 $2 i + 1 > n$ ，则结点 $i$ 无右孩子；否则其右孩子是结点 $2 i + 1$ 。

3.二叉树遍历（基础知识掌握）

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

3.1 前、中、后序遍历

3.2 二叉树的建立

3.3 线索二叉树

3.3.1 对于一个有 $n$ 个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是 $2 n$ 个指针域。而 $n$ 个结点的二叉树一共有 $n - 1$ 条分支线数，也就是说，其实是存在 $2 n - (n - 1) = n + 1$ 个空指针域。

           A
         /   \
        B     C
       / \   / \
      D   E F   G
     / \ /
    H  I J 
         图3-1

3.3.2 如上图，中序遍历得到HDIBJEAFCG这样的字符，可以知道，结点I的前驱是D，后继是B，结点F的前驱是A，后继是C。

3.3.3 指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树(Threaded Binary Tree)。

3.3.4 其实线索二叉树，等于是把一棵二叉树转变成了一个双向链表，这样对我们的插入删除结点都带来了方便。

3.3.5 对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

3.3.6 在每个节点再增设两个标志域ltag和rtag，只存放0或1数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。结点结构如下：

lchild	ltag	data	rtag	rchild

其中：

ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
rtag为0时指向该结点的右孩子，为1时指向该结点的后继。
因此对于图3-1的二叉链表图可以修改为图3-2的样子。

             0A0
          /       \
        0B0       0C0
       /   \     /   \
     0D0   0E1 1F1   1G1
     / \    /
   1H1 1I1 1J1 
            图3-2

3.4 线索二叉树结构实现

线索化的过程就是在遍历的过程中修改空指针的过程。
中序遍历线索化的递归函数代码如下：

BiThrTree pre;	/* 全局变量，始终指向刚刚访问过的节点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p){
  if(p){
    InThreading(p->lchild); /* 递归左子树线索化 */
    
    if(!p->lchild){				/* 没有左孩子 */
      p->LTag=Thread;				/* 前驱线索 */
      p->lchild=pre;				/* 左孩子指针指向前驱 */
    }
    if(!pre->rchild){				/* 前驱没有右孩子 */
      p->RTag=Thread;				/* 后继线索 */
      p->rchild=p;				/* 前驱右孩子指针指向后继（当前结点p） */
    }
    pre=p;		/* 保持pre指向p的前驱 */
    
    InThreading(p->rchild); /* 递归右子树线索化 */
  }
}

有了线索二叉树后，我们对它进行遍历时发现，其实就等于是操作一个双向链表结构。
和双向链表结构一样，在二叉树线索链表上添加一个头结点，如图3-3所示，并另其lchild域的指针指向二叉树的根节点（图中的a），其rchild域的指针指向中序遍历时访问的最后一个结点（图中的b）。
反之，令中序序列中的第一个结点H的lchild域指针和最后一个结点的rchild域指针均指向头结点。这样定义的好处就是我们既可以从第一个节点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

        头指针->| |0#1| | 
              a/      | 
             0A0      |
          /       \   |b
        0B0       0C0 |
       /   \     /   \|
     0D0   0E1 1F1   1G1
     / \    /
   1H1 1I1 1J1 
            图3-3

遍历代码如下：

/* T指向头结点，头结点左链lchild指向根节点，头结点右键rchild指向中序遍历的 */
/* 最后一个结点。中序遍历二叉线索链表表示的二叉树T */
Status InOrderTraverse_Thr(BiThrTree T){
  BiThrTree p;
  p = T->lchild;			/* p指向根结点 */
  while(p != T){			/* 空树或遍历结束时，p==T */
    while(p->LTag==Link)	/* 当LTag==0时循环到中序序列第一个结点 */
      p = p->lchild;
    printf("%c", p->data);	/* 显示结点数据，可以更改为其他对结点操作 */
    while(p->RTag==Thread && p->rchild!=T){
      p = p->rchild;
      printf("%c", p->data);
    }
    p = p->rchild;		/* p进至其右子树根 */
  }
  return OK;
}

相当于是一个链表的扫描，所以时间复杂度为O(n)。

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

4.二叉树遍历算法应用

算法都在二叉树的应用和二叉排序树噢！

5.树遍历算法应用

树转换为二叉树
森林转换为二叉树
二叉树转换为树
二叉树转换为森林

5.1 树的遍历

两种方式

一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树。
另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点。
比如图5-1中的树，它的先根遍历序列为ABEFCDG，后根遍历序列为EFBCGDA。

5.2 森林的遍历