数据结构——5.树

5.1.1 树的定义

树形式化定义：T={D,R}。D是包含n个节点的有限集合。当n=0时为空树，否则关系R满足以下条件：

有且仅有一个节点对于关系R来说没有前驱节点，称作根节点。

除根节点外，每个节点有且仅有一个前驱节点。

D中每个节点可以有零个或多个后继节点。

5.1.2树的基本术语

1、节点的度与树的度：

树中一个节点的子树的个数成为该节点的度。树中各节点的度的最大值称为树的度，通常将度为m的树成为m次树或m叉树。

2、分支节点与叶节点：

度不为零的节点称为非终端节点，又叫分支节点。度为零的节点称为终端节点或叶节点。

度为1的节点称为单分支节点；度为2的节点称为双分支节点。

3、路径与路径长度：

两个节点之间的节点序列称为路径。

路径长度等于路径所通过的节点数目减一。

4、有序数和无序树：

若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。

5、森林：

n个互不相交的树的集合称为森林。

5.1.3 树的性质

性质1 树中的节点数等于所有节点的度数加1。

性质2 度为m的树中第i层上至多有m^(i-1)个节点(i>=1)。

性质3 高度为h的m次树至多有 (m^h - 1)/(m-1)个节点。

性质4 具有n个节点的m次树的最小高度为

5.1.4 树的基本运算

查找、插入或删除、遍历。

主要的遍历方法：

先根遍历：若树不空，则先访问根节点，然后依次先根遍历各棵子树。

后根遍历：若树不空，则先依次后根遍历各棵子树，然后访问根节点。

层次遍历：若树不空，则自上而下、自左至右访问树中每个节点。

注意：先根和后跟遍历算法都是递归的。

5.1.5 树的存储结构

1、双亲存储结构：每一个节点都有一个指针指向双亲位置。

2、孩子链存储结构：每个节点都有一组指针指向一棵子树。

3、孩子兄弟链存储结构：每个节点都有三个域，数据元素域、第一个孩子节点指针域、一个兄弟节点指针域。

5.2.1 二叉树的定义

满二叉树：高度为h的二叉树恰好有2^h-1个节点。

完全二叉树：在一棵二叉树中

最多只有下面两层的节点的度数小于2

并且最下面一层的叶节点都依次排列在该层最左边的位置上。

完全二叉树实际上是对应的满二叉树删除叶节点层最右边若干个节点得到的。

5.2.2 二叉树性质

性质1 非空二叉树上叶节点数等于双分支节点数加1。

性质2 非空二叉树上第i层上至多有2^(i-1)个节点。

性质3 高度为h的二叉树至多有2^h-1个节点。

性质4 完全二叉树性质：

若i<(n/2)，则编号为i的节点为分支节点，否则为叶节点。

除树根节点外，若一个节点的编号为i，则它的双亲节点的编号为i/2。

若编号为i的节点有左孩子节点，则左孩子节点的编号为2i；

若编号为i的节点有右孩子节点，则右孩子节点的编号为2i+1。

5.3.1 二叉树的顺序存储结构

对于完全二叉树来说，顺序存储是十分合适的。

对于非完全二叉树来说，浪费空间惊人。

在顺序存储结构中，找一个节点的双亲和孩子都很容易。

5.3.2 二叉树的链式存储结构

二叉链比较节省存储空间。占用的存储空间只与树中节点个数有关。

在二叉链中，找一个节点的孩子很容易，但找其双亲不方便。

//二叉树查找一个元素的算法
BTNode *FindNode(BTNode *b,ElemType x){
    BTNode *p;
    if(b==NULL) return NULL;
    else if (b->data==xx) return b;
    else {
        p=FindNode(b->left,x);
        if(p!=NULL) return p;
        else return FindNode(b->right,x);
    }
}

//求树的高度
int BTNodeDepth(BTNode *b){
    int ldep,rdep;
    if(b==NULL) return 0;   //空树
    else{
        ldep = BTNodeDepth(b->left);    //求左子树的高度
        rdep = BTNodeDepth(b->right);   //求右子树的高度
        return ldep>rdep?(ldep+1):(rdep+1);
    }
}

5.4.1 二叉树遍历

//先序遍历的递归算法 NLR
void PreOrder(BTNode *b){
    if(b!=NULL){
        printf("%c",b->data);   //访问根节点
        PreOrder(b->left);
        PreOrder(b->right);
    }
}
//中序遍历的递归算法 LNR
void InOrder(BTNode *b){
    if(b!=NULL){
        PreOrder(b->left);
        printf("%c",b->data);   //访问根节点
        PreOrder(b->right);
    }
}
//后序遍历的递归算法 LRN
void PostOrder(BTNode *b){
    if(b!=NULL){
        PreOrder(b->left);
        PreOrder(b->right);
        printf("%c",b->data);   //访问根节点
    }
}

//层次遍历算法，从上到下，从左到右遍历
/*思路：使用一个队列,时间复杂度为O(n)
1.将根节点进队
2.队不空时循环：从队列中拿出一个节点*p，访问它；
    若它有左孩子节点，将左孩子节点进队
    若它有右孩子机电，将右孩子节点进队。*/
void LevelOrder(BTNode *b){
    BTNode *p;
    BTNode *qu[MaxSize];    //定义环形队列，存放节点指针
    int front,rear;
    front = rear = 0;   //置队列为空队列
    rear++;
    qu[rear]=b;
    while(front!=rear){     //队列不为空循环
        front=(front+1)%MaxSize;
        p=qu[front];        //队头出队列
        printf("%c",->data);    //访问节点
        if(p->left!=NULL){      //有左孩子时将其进队
            rear = (rear+1)%MaxSize;
            qu[rear] = p->left;
        }
        if(p->right!=NULL){     //有右孩子时将其进队
            rear = (rear+1)%MaxSize;
            qu[rear] = p->right;
        }
    }
}

5.5.1 二叉树3种递归遍历算法的应用

例5-1

假设二叉树采用二叉链存储结构存储，设计一个算法，计算一棵给定二叉树的所有节点个数。

int Nodes(BTNode *b){
    int num1,num2;
    if(b==NULL) return 0;
    else
        return Nodes(b->left)+Nodes(b->right)+1;
    //先左子树，再右子树，再加1，后序遍历的思想
    //三者顺序不同，递归的方式也不同
}

例5-2

假设二叉树采用二叉链存储结构存储，设计一个算法，计算一棵给定二叉树的所有叶子结点个数。

int LeafNodes(BTNode *b){
    int num1,num2;
    if(b==NULL) return 0;
    else if(b->left==NULL && b->right==NULL)
        return 1;
    else{
        num1 = LeafNodes(n->left);
        num2 = LeafNodes(b->right);
        return (num1+num2);
    }
    //先左子树，再右子树，再相加，后序遍历的思想
    //三者顺序不同，递归的方式也不同
}

例5-3

假设二叉树采用二叉链存储结构，设计一个算法把二叉树b复制到二叉树t中。

void Copy(BTNode *b,BTNode *&t){
    if(b==NULL) t=NULL;
    else{
        t=(BTNode*)malloc(sizeof(BTNode));
        t->data = b->data;			//复制一个根节点*t
        Copy(b->left,t->left);		//递归复制左子树
        Copy(b->right,t->right);	//递归复制右子树
    }
}
void Copy(BTNode *b,BTNode *&t){
    if(b==NULL) t=NULL;
    else{
        t=(BTNode*)malloc(sizeof(BTNode));
        t->data = b->data;          //复制一个根节点*t
        Copy(b->left,t->left);      //递归复制左子树
        Copy(b->right,t->right);    //递归复制右子树
    }
}

例5-4

设二叉树采用二叉链存储结构，设计一个算法把二叉树b的左、右子树进行交换。要求不破坏元二叉树。

void Swap(BTNode *b,BTNode *&t){
    if(b==NULL) t=NULL;
    else{
        t=(BTNode*)malloc(sizeof(BTNode));
        t->data = b->data;          //复制一个根节点*t
        Swap(b->left,t->right);     //递归交换左子树
        Swap(b->right,t->left); //递归交换右子树
    }
}

例5-5

假设二叉树采用二叉链存储结构，设计一个算法Level()求二叉树b中值为x的节点的层次。

解：设Level(b,x,h)返回二叉树b中data值为x的节点的层次，其中h表示b所指节点的层数。

当在二叉树b中找到data值为x的节点，返回其层次；若没有找到，则返回0。

递归算法一定要先设计递归模型，确定终结条件。

int Level(BTNode *b,ElemType x,int h){
    if(b==NULL) return 0;   //空树时返回0
    else if(b->data==x) return h;   //找到节点时
    else {
        int l=Level(b->left,h+1);   //在左子树中查找
        if(l==0)        //左子树中未找到时在右子树中查找
            return Level(b->right,x,h+1);
        return l;
    }
}

5.5.2 层次遍历算法的应用

例5-6

假设二叉树采用二叉链存储结构，设计一个算法输出从根节点到每个叶子节点的逆路径。

5.6.1线索二叉树

相关概念：

采用某种方法遍历二叉树的结果是一个节点的线性序列。
修改空链域改为存放指向节点的前趋和后继节点的地址。
这样的指向该线性序列中的“前趋”和“后继”的指针，称作线索。
创建线索的过程称为线索化。
显然线索二叉树与采用的遍历方法相关，有先序线索二叉树、中序线索二叉树和后序线索二叉树。
在节点的存储结构上增加两个标志位来区分这两种情况：

左标志ltag：0表示left指向左孩子节点，1表示left指向前趋节点，即左线索

右标志rtag：0表示right指向右孩子节点，1表示right指向后继节点，即右线索

为了方便线索设计，在线索二叉树中再增加一个头结点。

5.6.2 线索化二叉树

建立某种次序的线索二叉树过程：

- 以该遍历方法遍历一棵二叉树。

- 在遍历的过程中，检查当前访问节点的左、右指针域是否为空：

如果左指针域为空，将它改为指向前趋节点的线索；

如果右指针域为空，将它改为指向后继节点的线索；

前驱、后继节点与遍历方式有关。

建立线索二叉树的目的：

对二叉树中序遍历，递归算法：时间复杂度均为O(n)，空间复杂度均为O(h)
对二叉树中序遍历，非递归算法：时间复杂度均为O(n)，空间复杂度均为O(h)
对中序线索二叉树中序遍历，时间复杂度均为O(n)，空间复杂度均为O(1)

建立中序线索二叉树的算法：

CreatTherad(b)算法：对以二叉链存储的二叉树b进行中序线索化，并返回线索化后头节点的指针root。

Thread(p)算法：对以*p为根节点的二叉树子树的中序线索化。

二叉树中序序列的开始节点是根节点的最左下节点，尾节点是根节点的最右下节点。

在中序遍历中：

p总是指向当前线索化的节点。
pre作为全局变量，指向刚刚访问过的节点。
pre是p的中序前趋节点，p是pre的中序后继节点。

TBTNode
TBTNode *pre;   //全局变量
TBTNode *CreatThread(TBTNode *b){   //中序线索化二叉树
    TBTNode *root;  
    root = (TBTNode *)malloc(sizeof(TBTNode));  //创建头节点
    root->ltag=0; root->rtag=1; root->right=b;
    if(b==NULL) root->left = root;      //空二叉树
    else {
        root->left = b;     //让头节点的left指针指向b
        pre = root;     //pre是*p的前趋节点，供加线索用
        Thread(b);      //中序遍历线索化二叉树
        pre->right = root;  //最后处理，加入指向头节点的线索
        pre->rtag = 1;
        root->right = pre;  //头节点右线索化
    }
    return root;
}
void Thread(TBTNode *&p){
    if(p!=NULL){
        Thread(p->left);        //左子树线索化
        if(p->left == NULL){    //前趋线索化
            p->left=pre;        //建立当前节点的前趋线索
            p->ltag=1;  
        }else p->ltag=0;
        if(pre->right == NULL){ //后继线索化
            pre->right=p;       //建立前趋节点的后继线索
            pre->right=1;
        }else pre->right=0;
        pre = p;
        Thread(p->right);       //递归调用右子树线索化
    }
}
//上代码是中序遍历两个Thread及中间部分

5.6.3 遍历线索化二叉树

遍历某种次序的线索二叉树，就是从该次序下的开始节点出发，反复找到该节点在该次序下的后继节点，直到头节点。

在中序线索二叉树中中序遍历的过程：

/*
p指向根节点;
while p != root 时循环{
    找开始节点*p;
    访问*p节点;
    while(*p节点有右线索)
        一直访问下去;
    p转向右孩子节点;
}
*/
void ThInOrder(TBTNode *tb){
    TBTNode *p=tb->left;        //p指向根节点
    while(p!=tb){
        while(p->ltag==0) p=p->left;    //找开始节点
        printf("%c",p->data);       //访问开始节点
        while(p->rtag==1 && p->right!=tb){
            p=p->right;
            printf("%c",p->data);
        }
        p=p->right;
    }
}

优点：中序遍历算法既没有递归也没有用栈，空间效率得到提高。

5.7.1 哈夫曼树

设二叉树具有n个带权值的叶节点，那么从根节点到各个叶节点的路径长度为相应节点权值的乘积的和，叫做二叉树的带权路径长度。

具有在最小带权路径长度的二叉树成为哈夫曼树（最优树）。

权值是指该节点的优先级，越大，表示搜索的频率越高。越靠近根节点，编码越短。

构造哈夫曼树的原则：

权值越大的叶节点越靠近根节点

权值越小的叶节点越远离根节点

构造哈夫曼树的过程：

在节点集合中选取根节点的权值最小和次小的两个二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根节点的权值为其左、右子树根节点权值之和。然后不断重复，直到生成一棵哈夫曼树。

5.7.3 哈夫曼编码

规定哈夫曼树中的左分支为0，右分支为1，则从根节点到每个叶节点所经过的分支对应的0和1组成的序列便为该节点对应字符的编码。这样的编码成为哈夫曼编码。

哈夫曼编码特点：权值越大的字符编码越短，反之越长。

在一组字符的哈夫曼编码中，不可能出现一个字符的哈夫曼编码是另一个字符哈夫曼编码的前缀。

5.8.1 小结

例5-7

假设二叉树采用二叉链存储结构，设计一个算法求二叉树b中度为2的节点个数。

int dnodes(BTNode *b){
    if(b==NULL) return 0;
    if(b->left!=NULL && b->right!=NULL)
        return 1+dnodes(b->left)+dnodes(b->right);
    else
        return dnodes(b->left)+dnodes(b->right);
}

例5-8

假设二叉树采用二叉链存储结构，设计一个算法求二叉树b中第k层的节点个数。

解：设计算法为knumber(b,h,k,&n)，h表示b所指的节点层次，n是引用型参数，用于保存第k层的节点个数。初始调用时，b为根节点指针，h为1，n赋值为0，即调用方式是：n=0; knumber(b,1,k,n)。

void knumber(BTNode *b,int h,int k,int &n){
    if(b==NULL) return;		//空树直接返回
    else{		//处理非空树
        if(h==k) n++;		//当前访问的节点在第k层时，n增1
        else if(h<k){		//若当前节点层次小于k,递归处理左、右子树
            knumber(b->left,h+1,k,n);
            knumber(b->right,h+1,k,n);
        }
    }
}
void knumber(BTNode *b,int h,int k,int &n){
    if(b==NULL) return;     //空树直接返回
    else{       //处理非空树
        if(h==k) n++;       //当前访问的节点在第k层时，n增1
        else if(h<k){       //若当前节点层次小于k,递归处理左、右子树
            knumber(b->left,h+1,k,n);
            knumber(b->right,h+1,k,n);
        }
    }
}

例5-9

假设二叉树采用二叉链存储结构，设计一个算法求二叉树b的宽度。

解：levelnumber(BTNode *b,int h,int a[])：求二叉树b中所有层的节点个数，存放在a数组中，a[h]表示第h层节点个数。

//将每一层的节点数存入数组a中
void levelnumber(BTNode *b,int h,int a[]){
    if(b==NULL) return;     //空树直接返回
    else{       //处理非空树
        a[h]++; 
        levelnumber(b->left,h+1,a);
        levelnumber(b->right,h+1,a);
    }
}
//具体求解
int BTWidth1(BTNode *b){
    int width=0,i; int a[MaxSize];
    for(i=1;i<MaxSize;i++)
        a[i]=0;     //设置所有元素初始化为0
    levelnumber(b,1,a);
    i=1;
    while(a[i]!=0){     //求a中最大元素即宽度
        if(a[i]>width)
            width=a[i];
        i++;
    }
    return width;
}

例5-10

假设二叉树采用二叉链存储结构，设计一个算法求二叉树b的宽度（采用层次遍历方法）。

int BTWidth2(BTNode *b){
    struct{
        int lno;		//节点的层次
        BTNode *p;		//节点指针
    }Qu[MaxSize];		//定义非环形队列
    int front,rear;		//定义队头和队尾指针
    int lnum,width,i,n;
    front=rear=0;		//置队列为空队
    if(b!=NULL){
        rear++;
        Qu[rear].p=b;		//根节点进队
        Qu[rear].lno=1;		//根节点的层次为1
        while(rear!=front){	//队不空时循环
            front++;
            b=Qu[front].p;	//出队节点p
            lnum=Qu[front].lno;
            if(b->left!=NULL){		//有左孩子，将其进队
                rear++;
                Qu[rear].p=b->left;
                Qu[rear].lno=lnum+1;
            }
            if(b->right!=NULL){		//有右孩子，将其进队
                rear++;
                Qu[rear].p=b->right;
                Qu[rear].lno=lnum+1;
            }
        }
        width=0;lnum=1;i=1;		//width存放宽度
        while(i<rear){
            n=0;
            while(<rear && Qu[i].lno==lnum){
                n++;		//n累计一层中的节点个数
                i++;		//i扫描队列中所有节点
            }
            lnum=Qu[i].lno;
            if(n>width) width=n;
        }
        return width;
    }
    else return 0;
}