双亲表示法

在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。

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

#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;

孩子表示法

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

/*树的孩子表示法结构定义*/

#define MAX_TREE_SIZE 100

typedef  struct  CTNode   {    /*孩子结点*/

      int child;

      struct  CTNode  *next;

}  *ChildPtr;

stypedef 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;

这个表示法最大的好处就是把一颗复杂的树变成一颗二叉树

二叉树

定义：

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

特点：

·每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。

·左子树和右子树是有顺序的，次序不能任意颠倒。

·即使树中某结点只有一颗子树，也要区分它是左子树还是右子树。

特殊二叉树

1、斜树

所有的结点都是只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

2、满二叉树

在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

3、完全二叉树

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

二叉树的性质

性质1：在二叉树的第i层上至多有2的i-1次方个结点(i>=1)。

性质2：深度为k的二叉树至多有2的k次方-1个结点(k>=1)。

性质3：对任何一颗二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。

性质4：具有n个结点的完全二叉树的深度为|log2 n| + 1(|x|表示不大于x的最大整数)。

性质5：

如果对一颗有n个结点的完全二叉树的结点按层序编号，对任一结点i（1<=i<=n）有：

1、如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲结点是|i/2|。

2、如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。

3、如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。

二叉树的存储结构

二叉链表

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

以下是二叉链表的结点结构定义代码

/*二叉树的二叉链表结点结构定义*/

typedef struct BiTNode {/*结点结构*/

        TElemType  data;/*结点数据*/

        struct  BiTNode  *lchild,  *rchild;/*左右孩子指针*/

}  BiTNode, *BiTree;

遍历二叉树

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

二叉树遍历方法

1、前序遍历

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

2、中序遍历

规则是若树为空，则空操作返回，否则从根结点开始，中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。

3、后序遍历

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

4、层序遍历

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

前序遍历算法

/*二叉树的前序遍历递归算法*/

void PreOrderTraverse(BiTree T) {

       if(T ==NULL)

            return;

       printf("%c",T->data);/*显示结点数据，可以更改为其他对结点操作*/

       PreOrderTraverse(T->lchild);/*再先序遍历左子树*/

       PreOrderTraverse(T->rchild);/*最后先序遍历右子树*/

}

中序遍历算法

/*二叉树的中序遍历算法*/

void  InOrderTraverse(BiTree T) {

        if(T == NULL)

                 return;

         InOrderTraverse(T->lchild);

         printf("%c",T->data);

          InOrderTraverse(T->rchild);

}

后序遍历算法

/*二叉树的后序遍历算法*/

void  PostOrderTraverse(BiTree  T) {

         if(T == NULL)

                 return;

          PostOrderTraverse(T->lchild);

          PostOrderTraverse(T->rchild);

           printf("%c",T->data);

}

推导遍历结果

·已知前序遍历序列和中序遍历序列，可以唯一确定一颗二叉树。

·已知后序遍历序列和中序遍历序列，可以唯一确定一颗二叉树

·已知前序和后序遍历，不能唯一确定一颗二叉树

树转换为二叉树

将树转换为二叉树的步骤如下：

1、加线。在所有兄弟结点之间加一条线

2、去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。

3、层次调整。以树的根结点为轴心，将整颗树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

森林转换为二叉树

1、把每棵树转换为二叉树

2、第一棵二叉树不动，从第二棵二叉树开始，依次把最后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有二叉树连接起来后就得到了由森林转换来的二叉树。

二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，步骤如下：

1、加线。若某结点的左孩子结点存在，则将这个左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。

2、去线。删除原二叉树中所有结点与其右孩子结点的连线。

3、层次调整。使之结构层次分明。

二叉树转换为森林

1、从根结点开始，若有孩子存在，则把右孩子结点的连线删除，直到所有右孩子连线都删除为止，得到分离的二叉树。

2、再将每棵分离后的二叉树转换为树即可。

赫夫曼树

定义

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。

树的路径长度就是从树根到每一结点的路径长度之和。

结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。带权路径长度WPL最小的二叉树称作赫夫曼树。

构造赫夫曼树的赫夫曼算法描述：

1、根据给定的n个权值{w1,w2,...,wn}构成n棵二叉树的集合F={T1,T2,...,Tn},其中每棵二叉树Ti中只有一个带权为wi根结点，其左右子树均为空。

2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

3、在F中删除这两棵树，同时将新得到的二叉树加入F中。

4、重复2和3步骤，直到F只含一棵树为止。这棵树便是赫夫曼树。

赫夫曼编码

一般地，设需要编码的字符集为{d1,d2,...,dn},各个字符在电文中出现的次数或频率集合为{w1,w2,...,wn},以d1,d2,...,dn作为叶子结点，以w1,w2,....,wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。