C 语言中树结构定义和使用

Question

一、树的定义

树（Tree）是 n（n>=0）个节点的有限集。当 n=0 时成为空树，在任意一棵非空树中：

• 有且仅有一个特定的称为根（Root）的节点
• 当 n>1 时，其余节点可分为 m（m>0）个互不相交的有限集 T1 T2 T3 ... Tm，其中每个集合本身又是一棵树，并且称为根的子树（SubTree）。

二、节点分类

节点拥有的子树数称为节点的度（Degree），树的度取树内各节点的度的最大值。

• • 度为 0 的节点称为叶节点或终端节点
  • 度不为 0 的节点称为分支节点或非终端节点，除根节点外，分支节点也称为内部节点。

节点之间的关系

节点的子树的根称为节点的孩子（Child），相应的，该节点称为孩子的双亲（Parent），同一双亲的孩子之间互称为兄弟（Sibling）。

节点的祖先是从根到该节点所经分支上的所有节点。

节点的层次

节点的层次（level）从根开始起，根为第一层，根的孩子为第二层。

其双亲在同一层的节点互为堂兄弟。

树中节点的最大层次称为树的深度(depth)或高度。

其他概念

如果将树中节点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

三、树的存储结构

说到存储结构，就会想到我们前面章节讲过的顺序存储和链式存储两种基本结构。

对于线性表来说，很直观就可以理解，但对于树这种一对多的结构，我们应该怎么办呢？

要存储树，简单的顺序存储结构和链式存储结构是不能的。不过如果充分利用他们各自的特点，完全可以间接地来实现。

这里要介绍三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

双亲表示法

双亲表示法，言外之意就是以双亲作为索引的关键词的一种存储方式。

我们假设以一组连续空间存储树的节点，同时在每个节点中，附设一个指示其双亲节点在数组中位置的元素。

也就是说，每个节点除了知道自己是谁之外，还知道他的双亲在哪。

//树的双亲表示节点结构定义

#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct PTNode{
  ElemType data;//节点数据
  int parent;//双亲位置
}PTNode;

typedef struct{
  PTNode nodes[MAX_TREE_SIZE];
  int r;//根的位置
  int n;//节点数目·
}PTree

这样的存储结构，我们可以根据某节点的parent指针找到他的双亲节点，所用的时间复杂度是 O(1)，索引到 parent 的值为-1时，表示找到了树节点的根。

可是，如果我们要知道某个节点的孩子是什么？那么需要遍历整个树结构。

这真的麻烦，能不能改进以下呢？我们只需稍微改变以下结构即可：

那现在我们又比较关心他们兄弟之间的关系呢？

孩子表示法

我们这次换个角度来考虑，由于树中每个节点可能有多棵子树，可以考虑用多重链表来实现。

双亲孩子表示法

那只找好孩子找不到双亲貌似还不够完善，那么我们合并上一讲的双亲孩子表示法：

parent_child.c

#define MAX_TREE_SIZE = 100
typedef char ElemType;
//孩子节点
typedef struct CTNode{
  int child;/孩子节点的下标
  struct CTNode *next;//指向下一个孩子节点的指针
} *ChildPtr;

//表头结构
typedef struct{
  ElemType Data;//存放在树中的节点的数据
  int parent;//存放双亲的下标
  ChildPtr firstchild;//指向 第一个孩子的指针
}CTBox;

//树结构
typedef struct{
  CTBox node[MAX_TREE_SIZE];//节点数组
  int r,n;
};

四、二叉树

因为二叉树使用范围最广，最具有代表意义，因此我们重点讨论二叉树。

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

二叉树的特点

每个节点最多有两棵子树，所以二叉树中不存在度大于2的节点。（注意：不是都需要两棵子树，而是最多可以是两棵，没有子树或者有一棵子树也都是可以的。）

左子树和右子树是由顺序的，次序不能颠倒。

即使树中某节点只有一棵子树，也要区分它是左子树还是右子树，下面是完全不同的二叉树：

二叉树的五种基本形态

• 空二叉树
• 只有一个根节点
• 根节点只有左子树
• 根节点只有右子树
• 根节点既有左子树又有右子树

特殊二叉树

• 斜树 要么往左斜，要么往右斜
• 满二叉树 在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层，这样的二叉树称为满二叉树。

• 完全二叉树 对一棵具有n个节点的二叉树按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点位置完全相同，则这棵二叉树称为完全二叉树。

二叉树的性质

在二叉树的第i层上至多有2^(i-1)个节点(i>=1)

深度为k的二叉树至多有2^k-1个节点

对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2则n0 = n2+1

具有n个节点的完全二叉树的深度为[log2 n]+1

如果对一棵有n个节点的完全二叉树（其深度为[log2 n] +1）的节点按层序编号，对任一节点 i(1<=i<=n) 有以下性质：

二叉树的存储结构

二叉树是一种特殊的树，由于他的特殊性，使得用顺序存储结构或链式存储结构都能简单实现。

二叉树的顺序存储结构就是用一维数组存储二叉树中的各个节点，并且节点的存储位置能体现节点之间的逻辑关系。

这下看出完全二叉树的优越性了吧，由于他的严格定义，在数组直接能表现出逻辑。

当然对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是也可以按照完全二叉树编号方式修改一下，把不存在的节点用^代替即可。

但是考虑到一种极端的情况，回顾一下斜树，如果是一个右斜树，那么会变成这样

既然顺序存储方式的适用性不强，那么我们就要考虑链式存储结构了。二叉树的存储按照国际惯例来说一般也是采用链式存储结构的。

二叉树的每个节点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTTree;

五、二叉树的遍历

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

二叉树的遍历次序不同于线性结构，线性结构最多也就是分为顺序、循环、双向等简单的遍历方式。

树的节点之间不存在唯一的前驱和后继这样的关系，在访问一个节点后，下一个被访问的节点面临着不同的选择。

二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为以下四种：

第一种：前序遍历

若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。

第二种：中序遍历

若树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。

第三种：后序遍历

若树为空，则空操作返回，否则从左到右先叶子后节点的方式遍历访问左右子树，最后访问根节点。

第四种：层序遍历

若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对节点逐个访问。

六、二叉树的建立和遍历算法

题目要求：建立二叉树并输出每个字符所在的层数。如图：

#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;

typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


//创建一棵二叉树,约定用户遵照前序遍历的方式输入数据
void createBiTree(BiTree *T){
  char c;
  scanf("%c",&c);

  if(' ' == c){//说明此子树不存在
    *T = NULL;
  }else{
    *T = (BiTNode *)malloc(sizeof(BiTNode));
    (*T)->data = c;
    createBiTree(&(*T)->lchild);//左子树
    createBiTree(&(*T)->rchild);//右子树
  }
}

//访问二叉树节点的具体操作
void visit(ElemType c,int level){
  printf("%c位于第%d层\n",c,level);
}
//遍历二叉树
void PreOrderTraverse(BiTree T,int level){
  if(T){
    visit(T->data,level);
    PreOrderTraverse(T->lchild,level+1);
    PreOrderTraverse(T->rchild,level+1);
  }
}

int main(){
  int level = 1;
  BiTree T = NULL;

  createBiTree(&T);

  PreOrderTraverse(T,level);
  return 0;
}

七、线索二叉树

为什么需要线索二叉树呢？

我想正如程序员发觉单链表并不总能满足他们设计的程序某些要求的时候，发明了双向链表来弥补一样，线索二叉树也是在需求中被创造的！

那普通二叉树到底有什么缺陷让我们发指呢？

主要是浪费时间和空间，我们具体分析下如何个浪费法：

数序题：请问以下有多少个 "^"？总共浪费了多少字节？(32bit的机器)

由于一个指针占用四个字节，一共有10个空指针，一共浪费了40个字节

脑筋急转弯：我们知道通过对二叉树的约定遍历方式，可以得到一个固定的遍历顺序，那么请问那种遍历方式可以节省"^"所浪费的空间？（利用"^"记录该节点的前驱后继）

没错，中序遍历可以拯救地球

上图经过中序遍历后结果是：H D I B E A F C G

我们发现粗体的节点都是刚才的"^"造成浪费的节点，利用中序遍历刚好他们处于字符中间，可以很好的利用"^"来存储前驱和后继的指针。

不过好事总是多磨的，我们是有主观意识所以就可以很容易想到哪些节点可以利用存放前驱后继。

上图经过中序遍历后的结果是：F D G B A C E

B和C只有一个空闲的指针位置，如果是这样的话我们就面临一个问题：机器怎么识别到底存放指针还是线索？

没错，它需要一丁点的提示，为此我们将已经定义好的结构进行“扩容”：

ltag为0时指向该节点的左孩子，为1时指向该节点的前驱。

rtag为0时指向该节点的右孩子，为1时指向该节点的后继。

#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;
//线索存储标志位
//Link(0)：表示指向左右孩子的指针
//Thread(1)：表示指向前驱后继的线索
typedef enum {Link,Thread}PointerTag;

typedef struct BiThrNode{
  char data;
  struct BiThrNode *lchild,*rchild;
  PointerTag ltag;
  PointerTag rtag;
}BiThrNode,*BiThrTree;

//全局变量，始终指向刚刚访问过的节点
BiThrTree pre;

//创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
void CreateBiThrTree(BiThrTree *T){
  char c;

  scanf("%c",&c);
  if(' ' == c){
    *T = NULL;
  }else{
    *T = (BiThrNode *)malloc(sizeof(BiThrNode));
    (*T)->data = c;
    (*T)->ltag = Link;
    (*T)->rtag = Link;

    CreateBiThrTree(&(*T)->lchild);
    CreateBiThrTree(&(*T)->rchild);
  }
}

//中序遍历线索化
void InThreading(BiThrTree T){
  if(T){
    InThreading(T->lchild);//递归左孩子线索化

    //节点处理
    if(!T->lchild){//如果该节点没有左孩子，设置ltag为Thread，并把lchild指向刚刚访问的节点
      T->ltag = Thread;
      T->lchild = pre;
    }
    if(!pre->rchild){
      pre->rtag = Thread;
      pre->rchild = T;
    }
    pre = T;

    InThreading(T->rchild);//递归右孩子线索化
  }
}
InOrderThreading(BiThrTree *p,BiThrTree T){
  *p = (BiThrTree)malloc(sizeof(BiThrNode));
  (*p)->ltag = Link;
  (*p)->rtag Thread;
  (*p)->rchild = *p;
  if(!T){
    (*p)->lchild = *p;
  }else{
    (*p)->lchild = T;
    pre = *p;
    InThreading(T);
    pre->rchild = *p;
    pre->rtag = Thread;
    (*p)->rchild = pre;
  }
}
int main(){
  BiThrTree P,T = NULL;

  CreateBiThrTree(&T);

  InOrderThreading(&p,T);
  return 0;
}

八、树、森林及二叉树的相互转换

在这一章节开始我们是从一棵普通的树开始介绍，在满足树的条件下可以是任意状态，一个节点可以有任意多个孩子，这样对树处理显得要复杂很多。

所以我们研究除了一些条条框框的限定，如：二叉树，完全二叉树，满二叉树等。

那么这时候你就会想，如果所有的树都像二叉树一样方便处理就好了。

普通树转换为二叉树

步骤如下：

1、在树中所有的兄弟节点之间加一连线

2、对每个节点，除了保留与其长子的连线外，去掉该节点与其他孩子的连线

森林到二叉树的转换

1、先将森林中的每一棵树变为二叉树（方法同上）

2、再将各二叉树的根节点视为兄弟从左至右连在一起。

二叉树到树、森林的转换

若节点 x 是其双亲的左孩子，则把 x 的的右孩子，右孩子的右孩子,...，都与 y 用线连起来。

去掉所有双亲到右孩子之间的连线

树与森林的遍历

树的遍历分为两种方式：一种是先根遍历，另一种是后根遍历。

先根遍历：先访问树的根节点，然后再依次先根遍历根的每一棵子树。

后根遍历：先依次遍历每棵子树，然后再访问根节点。

EFBGCHIJDA

森林的遍历也分为前序遍历和后序遍历，其实就是按照树的先根遍历和后根遍历依次访问森林的每一个树。

我们惊人的发现：树、森林的前根（序）遍历和二叉树的前序遍历结果相同，树、森林的后根（序）遍历和二叉树的终须遍历结果相同

九、赫夫曼树

在数据膨胀、信息爆炸的今天，数据压缩的意义不言而喻。谈到数据压缩，就不能不提赫夫曼(Huffman)编码，赫夫曼编码是首个实用的压缩编码方案，即使在今天的许多知名压缩算法里，依然可以见到赫夫曼编码的影子。

另外，在数据通信中，用二进制给每个字符进行编码时不得不面对的一个问题是如何使电文总长最短且不产生二义性。根据字符出现的频率，利用赫夫曼编码可以构造出一种不等长的二进制，使编码后的电文长度最短，且保证不产生二义性。

介绍赫夫曼编码之前，我们必须介绍赫夫曼树

什么叫做赫夫曼树呢？我们先来看一个例子。

以下程序在效率上有什么问题呢？

if(a<60){
  printf("不及格");
}else if(a<70){
  printf("及格");
}else if(a<90){
  printf("良好");
}else{
  printf("优秀");
}

如果我们把判断流程改为以下，效果可能有明显的改善

我们先把这两棵二叉树简化成叶子节点带权的二叉树（注：树节点间的连线相关的数叫做权，weight）。

节点的路径长度：从根节点到该节点的路径上的连接数

树的路径长度：树中每个叶子节点的路径长度之和

节点带权路径长度：节点的路径长度与节点权值的乘积

树的带权路径长度：WPL(Weighted Path Length) 是树中所有叶子节点的带权路径长度之和

WPL的值越小，说明构造出来的二叉树性能越优

那么现在的问题是，如何构造出最优的赫夫曼树呢？

十、赫夫曼编码

我们已经谈了赫夫曼树的基本原理和构造方式，二赫夫曼编码可以很有效的压缩数据（通常可以节省20%～90%的空间，具体压缩率依赖于数据的特性）

名词解释

定长编码

像ASCIIA编码（约定用8位来表示一个字符）

变长编码

单个编码的长度不一致，可以根据整体出现频率来调节

前缀码

所谓的前缀码，就是没有任何码字是其他码字的前缀