数据结构-树

众所周知，树一直是数据结构的重点，此处摘要不做多介绍

最近一直在循环coldplay的歌，分享一波

介绍

• 前言:树(Tree)是n(n≥0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：

1. 有且仅有一个特定的称为根(Root)的结点
2. 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2…..Tm，其中每一个集合本身又是一棵树，并且称为根的子数(SubTree)

   结点分类

• 树的结点包含一个数据元素以及若干指向其子树的分支。结点拥有的字树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。
• 树的度是树内各结点的度的最大值

  结点间关系

• 结点的子树的根称为该结点的孩子(Child)，相应的，该结点称为孩子的双亲(Parent)

  对于结点来说其父母同体，唯一的一个，所以称为双亲

• 同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所近分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙.

  树的其他相关概念

• 结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。

  若某结点在第I层，则其子树的根就在第I+1层。

• 其双亲在同一层的结点互为堂兄弟。
• 树中结点的最大层次称为树的深度(Depth)或高度

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

• 森林(Forest)是m(m≥0)棵互不相交的树的集合

  对树种的每个结点而言，其子树的集合即为森林。

• 对比线性表与树的结构，它们有很大的不同

1. 线性结构：①第一个数据元素：无前驱；②最后一个数据元素：无后继；③中间元素：一个前驱一个后继
2. 树结构：①根节点：无双亲，唯一；②叶节点：无孩子，可以多个；③中间结点：一个双亲多个孩子

---

树的抽象数据类型

对于线性结构，树的操作就完全不同了

ADT 树(Tree)
Data 树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关系.

Operation
    InitTree(*T):
    DestroyTree(*T):
    CreateTree(*T,definition):
    ClearTree(*T):
    TreeEmpty(T):
    TreeDepth(T):
    Root(T):返回树的根节点
    Value(T,cur_e):cur_e是树T中的一个结点，返回此结点的值
    Assign(T,cur_e,value):给树T的结点cur_e赋值为value
    Parent(T,cur_e):若cur_e是树T的非根结点，则返回它的双亲，否则返回空
    LeftChild(T,cur_e):若cur_e是树T的非叶节点，则返回它的最左孩子，否则返回空
    RightSibling(T,cur_e):若cur_e有右兄弟，则返回它的右兄弟，否则返回空
    InsertChild(*T,&p,i,c):其中p指向树T的某个结点，i为所指结点p的度加上1，非空树c与T不相交，操作结果为插入c为树T中p指结点的第i棵子树
    DeleteChild(*T,*p,i):其中p指向树T的某个结点，i为所指结点p的度，操作结果为删除T中p所指结点的第i棵子树
endADT

---

树的存储结构

• 双亲表示法(在每个结点中，附设一个指示器指示其双亲结点到链表中的位置)

  每个结点除了知道自己是谁之外，还知道它的双亲在哪里,结点结构分为data(数据域，存储结点的数据信息)跟parent(指针域，存储该结点的双亲在数组的下标)

  /*树的双亲表示法结点结构定义*/
  #define MAX_TREE_SIZE 100
  typedef int TElemType;  /*树结点的数据类型，目前暂定为整型*/
  typedef struct PTNode  /*结点结构*/
  {
      TElemType data;  /*结点数据*/
      int parent;  /*双亲位置*/
  }PTNode;
  typedef struct  /*树结构*/
  {
      PTNode nodes[MAX_TREE_SIZE];  /*结点数组*/
      int r,n;
  }PTree;

双亲域，长子域，右兄弟域

根节点的双亲域，长子域，右兄弟域都是-1

• 孩子表示法
  每个结点有多个指针域，其中每个指针指向一棵子树的根节点，我们把这种方法叫做多重链表表示法，不过树的每个结点的度，也就是它的孩子个数是不同的，所以我们可以设计两种反案来解决

1. 一种是指针域的个数等于树的度(树的度是树各个结点度的最大值
   这种方法在树中各结点的度相差很大时，显然是浪费空间的
2. 第二种是每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针域的个数(degree)
   这种方法克服了空间的浪费，对空间利用率是很高了，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗
   思考：能否有更好的方法，既可以减少空指针的浪费又能使结点结构相同？

   我们把每个结点放到一个顺序存储结构的数组中是合理的，但每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表体现它们的关系.
   这就是所谓的孩子表示法

• 孩子表示法:把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中

  /*树的孩子表示法结构定义*/
  #define MAX_TREE_SIZE 100
  typedef struct CTNode /*孩子结点*/
  {
      int child;
      struct CTNode *next;
  }*ChildPtr;
  
  typedef struct /*表头结构*/
  {
      TElemType data;
      ChildPtr firstchild;
  }CTbox;
  
  typedef struct /*树结构*/
  {
      CTBox nodes[MAX_TREE_SIZE];  /*结点数组*/
      int r,n;
  }CTree;

• 双亲孩子表示法

  算是孩子表示法的改进，略过

• 孩子兄弟表示法

  任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟

  /*树的孩子兄弟表示法结构定义*/
  typedef struct CSNode
  {
      TElemType data;
      struct CSNode *firstchild,*rightsib;
  }CSNode,*CSTree;

其实这个表达法最大好处就是把一棵复杂的树变成了一棵二叉树

---

二叉树

• 二叉树的五种基本形态：

1. 空二叉树
2. 只有一个根节点
3. 根节点只有左子树
4. 根节点只有右子树
5. 根节点既有左子树又有右子树

   注意：三个结点的树有两种情况，而三个结点的二叉树有五种形态

• 特殊二叉树

1. 斜树(左斜树跟右斜树)
2. 满二叉树

   注意满二叉树的叶子只能出现在最下一层，单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有叶子都在同一层上

3. 完全二叉树

• 二叉树的性质

1. 在二叉树的第i层上至多有2^i-1^个结点
2. 深度为k的二叉树至多有2^k^-1个结点

   这里要看清楚，很容易把性质1跟性质2弄混

3. 对任意一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
4. 具有n个结点的完全二叉树的深度为(log2n)+1
5. 如果对一棵有n个结点的完全二叉树(其深度为(log2n)+1)的结点按层序编号，对任一节点i(1≤i≤n)有：

• 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]
• 如果2i>n，则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i
• 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1

---

二叉树的存储结构

• 顺序存储:二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，还原成完全二叉树的方法

  考虑一种极端的情况，比如一棵深度为k的右斜树，它只有k个结点，却要分配2^k^-1个存储单元空间，这显然是对存储空间的浪费，所以顺序存储结构一般只用于完全二叉树.

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

  /*二叉树的二叉链表结点结构定义*/
  typedef struct BiTNode  /*结点结构*/
  {
      TElemType data;  /*结点数据*/
      struct BiTNode *lchild,*rchild; /*左右孩子指针*/
  }BiTNode,*BiTree

---

遍历二叉树

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

1. 前序遍历

   /*二叉树的前序遍历递归算法*/
   void PreOrderTraverse(BiTree T)
   {
       if(T==NULL)
           return;
       printf("c%",T->data); 
       PreOrderTraverse(T->lchild);
       PreOrderTraverse(T->rchild);
   }

2. 中序遍历

   /*二叉树的中序遍历递归算法*/
   void InOrderTraverse(BiTree T)
   {
       if(T==NULL)
           return;
       InOrderTraverse(T->lchild);
       printf("c%",T->data); 
       InOrderTraverse(T->rchild);
   }

3. 后序遍历

   /*二叉树的后序遍历递归算法*/
   void PostOrderTraverse(BiTree T)
   {
       if(T==NULL)
           return;
       PostOrderTraverse(T->lchild);
       PostOrderTraverse(T->rchild);
       printf("c%",T->data); 
   }

4. 层序遍历

• 推导遍历结果

1. 已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，求这棵二叉树的后序遍历结果?

   CBEFDA

2. 已知一棵二叉树的中序序列是ABCDEFG，后序序列是BDCAFGE,求前序序列?

   EACBDGF 重要

从这里我们可以得到两个二叉树遍历的性质

1. 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
2. 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树

   已知前序和后序遍历，是不能确定一棵二叉树的，例如已知前序序列ABC和后序序列CBA，我们可以确定A一定是根节点，但接下来我们无法知道哪个结点是左结点和右结点，所以有4种情况

---

二叉树的建立

• 利用扩展二叉树，比如假设二叉树的结点均为一个字符，我们把刚才前序遍历序列AB#D##C##用键盘挨个输入

  /*按前序输入二叉树中结点的值(一个字符)*/
  /* #表示空树，构造二叉链表示二叉树T */
  void CreateBiTree(BiTree *T)
  {
      TElemType ch;
      scanf("%c",&ch);
      if(ch == '#')
          *T=NULL;
      else
      {
          *T=(BiTree)malloc(sizeof(BiTNode));
          if(!*T)
              exit(OVERFLOW);
          (*T)->data=ch; /*生成根节点*/
          CreateBiTree(&(*T)->lchild); /*构造左子树*/
          CreateBiTree(&(*T)->rchild); /*构造右子树*/
      }
  }

其实建立二叉树，也是利用了递归的原理，只不过在原来应该打印结点的地方改成了生成结点，给结点赋值的操作而已，所以如果换成中序和后序遍历的方式，只要调整一下生成结点和构造左右子树的代码顺序即可

---

线索二叉树

我们考虑利用那些空地址，存放指向结点在某种遍历次序下的前驱和后继结点的地址

• 我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树(Threaded Binary Tree)
• 对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化，我们将这棵二叉树中所有空指针域中的lchild改为指向当前结点的前驱，rchild改为指向当前结点的后继
  但是问题没有彻底解决，我们如何知道某一结点的lchild是指它的左孩子还是指向前驱？rchild是指向右孩子还是指向后继？

  这里我们引入两个标志域ltag和rtag，注意ltag和rtag只是存放0或1数字的布尔型变量

  tag为0时指向结点的孩子，为1时指向该结点的前驱/后继

---

线索二叉树结构实现

/*二叉树的二叉线索存储结构定义*/
typedef enum {Link,Thread} PointerTag;  /*Link == 0表示指向左右孩子指针，Thread==1表示指向前驱或后继的线索*/
typedef struct BiThrNode  /*二叉线索存储结点结构*/
{
    TElemType data;  /*结点数据*/
    struct BiThrNode *lchild,*rchild;  /*左右孩子指针*/
    PointerTag LTag;
    PointerTag RTag;
}BiThrNode,*BiThrTree;

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索，由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。

中序遍历线索化的递归函数代码如下：

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

这段代码和二叉树中序遍历的递归代码几乎一样，只不过是将打印结点的功能改成了线索化的功能

有了线索二叉树后，我们对它进行遍历时发现，其实就等于操作一个双向链表结构

遍历的代码如下：

/*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;
}

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

---

树，森林与二叉树的转换

• 转换
• 树与森林的遍历

树的遍历分为两种形式

1. 先根遍历
2. 后根遍历

森林的遍历也分两种

1. 前序遍历
2. 后序遍历

   森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同

---

赫夫曼树及其应用

• 赫夫曼树定义及原理

1. 从树中的一个结点到另一个结点之间的分支构成的两个结点之间的路径，路径上的分支数目称为路径长度
2. 树的路径长度就是从树根到每个结点的路径长度之和。
3. 其中带权路径长度WPL最小的二叉树称为赫夫曼树，也称为最优二叉树.

• 赫夫曼编码
• 若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码

线索二叉树记得回顾理解一下

---