[数据结构]-[树结构]知识点：树的定义、二叉树、线索二叉树、树的存储结构、哈夫曼树。

部分图片与知识点转载于：http://www.cnblogs.com/skywang12345/p/3576328.html

1.树

0.结构

线性结构：线性表、栈、队列、串、数组、广义表。

非线性结构：树和二叉树、图、网。

1.定义

树是n（n≥0）个结点的有限集。

n=0时为空树。

n>1时，有且仅有一个称为该树的根的结点。

树1

2.特殊术语

1.若一个结点有子树，那么该结点称为子树根的“双亲”，子树的根是该结点的“孩子”。

2.有相同双亲的结点互为“兄弟”。同一层号的结点称为“堂兄弟”。

3.一个结点的所有子树上的任何结点都是该结点的子孙。从根结点到某个结点的路径上的所有结点都是该结点的祖先。

4.结点的度：结点拥有的子树的数目。
5.叶子（终端节点）：度为零的结点。
6.分支结点：度不为零的结点。
7.树的度：树中结点的最大的度。

8.n度树：度为n的树。

9.层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。
树的高度：树中结点的最大层次。

10.树的深度：各结点层的最大值。

11.无序树：如果树中结点的各子树之间的次序是不重要的，可以交换位置。
有序树：如果树中结点的各子树之间的次序是重要的, 不可以交换位置。
12.森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

3.树结构的特点

线性结构 树型结构
第一个数据元素（无前驱） 根结点（无前驱）
最后一个数据元素（无后继） 多个叶子结点（无“后继”）
其他数据元素（1前驱，1后继） 其他数据元素（1前驱，多后继）

2.二叉树

1.定义和术语

二叉树是是n（n≥0）个结点的有限集，或是空树，或由一个根节点和两棵分别为左子树和右子树的互不相交的二叉树构成。

特点：

1.每个结点之多有两棵子树。

2.子树有左右之分，不能颠倒次序。

树2

2.性质

1.二叉树第i层上的结点数目最多为2的i-1次方 (i≥1).

证明：下面用”数学归纳法”进行证明。
(01) 当i=1时，第i层的节点数目为2^{i-1}=2^{0}=1。因为第1层上只有一个根结点，所以命题成立。
(02) 假设当i>1，第i层的节点数目为2^{i-1}。这个是根据(01)推断出来的！
下面根据这个假设，推断出”第(i+1)层的节点数目为2^{i}”即可。
由于二叉树的每个结点至多有两个孩子，故”第(i+1)层上的结点数目” 最多是 “第i层的结点数目的2倍”。即，第(i+1)层上的结点数目最大值=2×2^{i-1}=2^{i}。
故假设成立，原命题得证！

2.深度为k的二叉树至多有2^k-1个结点(k≥1).

证明：在具有相同深度的二叉树中，当每一层都含有最大结点数时，其树中结点数最多。利用”性质1”可知，深度为k的二叉树的结点数至多为：
2^0+2^1+…+2^(k-1)=2^k-1
故原命题得证！

3.包含n个结点的二叉树的深度至少为log2 (n+1)

证明：根据”性质2”可知，高度为h的二叉树最多有2{h}–1个结点。反之，对于包含n个节点的二叉树的高度至少为log2(n+1)。

4.叶子的数目 = 度为2的结点数+1，即：n0 = n2 +1

证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)=”0度结点数(n0)” + “1度结点数(n1)” + “2度结点数(n2)”。由此，得到等式一。
(等式一) n=n0+n1+n2
　 另一方面，0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。
(等式二) n=n1+2n2+1
由(等式一)和(等式二)计算得到：n0=n2+1。原命题得证！

3.满二叉树

1.定义

深度为k，且有2^k-1个结点的二叉树。

2.性质

1.n个结点的满二叉树的深度 = log2(n+1)

2.左小孩为偶数，右小孩为奇数。

3.结点i的左小孩是2i，结点i的右小孩为2i+1，结点i的双亲为i/2向下取整。

4.结点i的层号 = log2i向下取整+1 = log2(i+1)向上取整

树3

4.完全二叉树

1.定义

一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。

树4

2.性质

1.除了最后一层缺一些节点，其余都是满的。（叶子节点只可能出现在层次最大或次大的两层上）

2.满二叉树一定是完全二叉树，反之不一定。

3.n个结点的完全二叉树深度为：log2n向下取整+1.

4.

(1) 若结点i = 1，则该结点为二叉树的根，无双亲，否则，编号为i/2向下取整的结点为i双亲结点。

(2) 若2i>n，则i结点没有左孩子，否则，编号为2i的结点为i左孩子结点。

(3) 若2i+1>n，则i结点没有右孩子，否则，编号为2i+1的结点为i右孩子结点。

5.二叉树的存储结构

顺序存储or链式存储？

1.顺序存储

使用一维数组存储二叉树，没有结点按0表示，表示为“虚节点”。

缺点：占地方

2.链式实现

树5

1.ADT
#define Nil '#'
typedef char TElemType;
typedef struct BinNode{
    TElemType data;
    struct BinNode *parent;
    struct BinNode *lchild,*rchild;
}BinNode,*BinTree;
2.初始化
void Init(BinTree *T){
    *T = NULL;
}
3.销毁
void Destroy(BinTree *T){
    if(*T!=NULL){//非空树
        if((*T)->lchild!=NULL)//有左孩子
            Destroy(&(*T)->lchild);
        if((*T)->rchild!=NULL)//有右孩子
            Destroy(&(*T)->rchild);
        free(*T);
        *T = NULL;
    }
}
4.判空
bool IsEmpty(BinTree T){
    return T == NULL;
}
5.深度
int Depth(BinTree T){
    if(T==NULL)
        return 0;
    else
        return (int)fmax(Depth(T->lchild),Depth(T->rchild))+1;
}
6.遍历
//前序遍历
void Traverse_PreOrder(BinTree T){
    if(T!=NULL){
        printf("%c",T->data);           //先访问根节点
        Traverse_PreOrder(T->lchild);   //再先序遍历左子树
        Traverse_PreOrder(T->rchild);   //先序遍历右子树
    }
}
//中序遍历
void Traverse_InOrder(BinTree T){
    if(T!=NULL){
        Traverse_InOrder(T->lchild);   //先中序遍历左子树
        printf("%c",T->data);          //访问根节点
        Traverse_InOrder(T->rchild);   //中序遍历右子树
    }
}
//后序遍历
void Traverse_PostOrder(BinTree T){
    if(T!=NULL){
        Traverse_PostOrder(T->lchild);  //先后序遍历左子树
        Traverse_PostOrder(T->rchild);  //再后序遍历右子树
        printf("%c",T->data);           //最后访问根节点
    }
}

非递归遍历用栈，层序遍历用队列。

用层序遍历的好处：非递归，效率高。

7.建树
//根据前序遍历建立二叉树(需要添加空叶子)
void PreOrderInputTree(BinTree *T){
    char ch;
    scanf("%c",&ch);
    if(ch == Nil) //空
        *T = NULL;
    else{
        *T = (BinTree) malloc(sizeof(BinNode));
        (*T)->data = ch;  //生成根节点
        PreOrderInputTree(&(*T)->lchild); //构造左子树
        PreOrderInputTree(&(*T)->rchild); //构造右子树
    }
}

由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。

但由前序和后序不能唯一确定。

6.表达式的前后缀

如果将中缀表达式对应一棵树：

前缀表达式相当于这棵树的前序遍历

中缀表达式相当于中序遍历

后缀表达式相当于后序遍历

7.线索二叉树

1.核心思想：把过多的空链接利用起来，方便遍历。

任意二叉树，空链域的个数总比非空链域还要多。

n个结点的二叉链表共有2n个链域

非空链域有n-1个（n个结点n-1条边）空链域有n+1个

【以上不考虑parent指针，即仅考虑二叉链表实现。】

线索二叉树即：利用这n+1个空链域存放结点的前驱和后继信息。

2.p指向二叉链表中结点，建立线索的规则：

  • 如果p->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。
  • 如果p->rchild为空，则存放指向中序遍历序列中该结点的后继结点。

3.如何区别child域是指向它的孩子还是线索指针？

解决办法：增加两个标志位，使用bool类型或者char型占空间最小。

或使用枚举类型可以增强可读性。（但是会占很多空间）

在此：使用bool型，true->线索，false->孩子

4.线索树的定义

typedef struct TBinNode{
    TElemType data;
    struct TBinNode *lchild,*rchild;
    bool LTag,RTag;
}TBinNode,*TBinTree;

存在前序、中序和后序三种线索二叉树，在此给出中序线索二叉树的实现。

//建树
void PreOrderInputTree(TBinTree *T){//按先序次序输入二叉树中结点的值添加足够的空叶子
    //建立树的时候暂时不添加线索
    TElemType ch;
    scanf("%c",&ch);
    if(ch == Nil)
        *T = NULL;
    else{
        //calloc保证Tag的默认为false
        *T = (TBinTree) calloc(1,sizeof(TBinNode));
        (*T)->data = ch;
        PreOrderInputTree(&(*T)->lchild);
        PreOrderInputTree(&(*T)->rchild);
    }
}
//线索化
TBinTree pre;//全局变量，始终指向刚访问过的结点
void InThreading(TBinTree p){//中序线索化子程序
    if(p!=NULL){
        InThreading(p->lchild);//递归左子树线索化
        if(p->lchild==NULL){//没有左孩子
            p->LTag=true;//前驱线索
            p->lchild=pre;//左孩子指针指向前驱
        }
        if(pre->rchild==NULL){//前驱没有右孩子
            pre->RTag=true;//后继线索
            pre->rchild=p;//前驱右孩子指针指向后继（当前节点p）
        }
        pre=p;//保持pre指向p的前驱
        InThreading(p->rchild);//递归右子树线索化
    }
}
//框架结构和中序遍历一样

注意：

前序、中序线索二叉树相对于后续二叉线索树比较完善，非递归遍历不需要用到栈，而后续二叉线索树可能要用到栈。

3.哈夫曼树

1.相关定义

  • 路径：树中从一个节点到另一个结点之间的分支。
  • 路径长度：结点路径上的分支数目
  • 带权路径长度：路径长度x结点权值
  • 树的路径长度：从树根到每一个叶子结点的路径长度之和
  • 树的带权路径长度（WPL）：树根到每个叶子节点的带权路径长度之和

2.贪心算法构造哈夫曼树

1.按权值大小排序

2.合并两棵权最小的二叉树，并排序。直到最后成为一棵树。

注意：

1.最优树可能不止一棵，但是WPL一定相等。

2.权值大的结点离根近。

贪心算法：

1.通常比较有利于算法编写

2.通常效率较高

3.通常得不到最优解

3.哈夫曼编码

1.将字符按出现频率作为节点的权值

2.利用这些带权节点创建哈夫曼树

3.规定左分支编码为0，右分支编码为1

如：

哈夫曼树