【数据结构】树

一.二叉树的基本概念和性质：

1.二叉树的递归定义：

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成

2.二叉树的特点：

（1）每个结点最多只有两棵子树，即不存在结点度大于2的结点

（2）子树有左右之分，不能颠倒。

3.满二叉树：

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

（1）每一层上结点数都达到最大。

（2）度为1的结点数 n_1=0

4.完全二叉树：

深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。

（1）完全二叉树的任意结点，左子树的高度-右子树的高度=0或1

5.二叉树的性质：

1）在二叉树的第i层，至多有 $2^{i-1}$ 个结点。

2）深度为k的二叉树上至多含有 2^k-1 个结点。

3) n_0=n_2+1

证明如下：

二叉树中全部结点数

除根结点外，每个结点必有一个直接前驱，即一个分支

（1度结点必有1个直接后继，2度结点必有2个直接后继）

即：

叶子数=2度结点数+1

4）具有n个结点的完全二叉树的深度为 $\lfloor log_2n\rfloor +1$

对有n个结点的完全二叉树的结点按层序编号，则对于任一结点i，有：

如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2
如果2i>n，则结点i无左孩子；如果 $2i\leq n$ ，则其左孩子是2i
如果2i+1>n，则结点i无右孩子；如果 $2i+1\leq n$ ，则其右孩子是2i+1

例题：

设一棵完全二叉树具有1000个结点，则它有489个叶子结点，有488个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。

二.二叉树、树以及森林的存储结构

1.二叉树的顺序存储结构

用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。

问：顺序存储后能否复原成唯一对应的二叉树形状？

若是完全二叉树则可以完全复原，下标值为i的双亲，左孩子为2i，右孩子为2i+1。

而对于一般的二叉树的存储，将其先补成完全二叉树，然后按照完全二叉树的顺序存储方式进行存储，而新补上的结点只占位置，不存放数据元素。

对于一般二叉树的顺序存储，如果是斜树，则会浪费很多的存储空间，而且插入删除不便。

2.二叉树的链式存储结构

有一个指向根的指针root

二叉链表：2个链分别存放左孩子和右孩子。

三叉链表：2个链分别存放左孩子和右孩子另外一个指向双亲。

线索链表：用空链域存放前驱或后继。

2.1 二叉链表：

结点结构：

lchild

data

rchild

typedef struct BiTreeNode{
    DataType data;
    struct BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;

2.2 三叉链表：

结点结构：

parent

lchild

data

rchild

typedef struct BiTreeNode{
    DataType data;
    struct BiTreeNode *lchild,*rchild,*parent;
}BiTreeNode,*BiTree;

3.树和森林的存储结构

3.1 树的双亲表示法

对于一个结点来说，双亲是一定的。

typedef struct PTNode{
    DataType data;
    int parent;
}PTNode;
typedef struct PTree{
    PTNode nodes[MAX_SIZE];
    int r,n;
}PTree;

3.2 树的孩子表示法

对于一个结点来说，孩子的数量是不一定的，为了整体元素结构的一致性，采用存储地址的方法。

typedef struct CTNode{
    int child;
    struct CTNode *next;
}CTNode;

typedef struct CTBox{
    DataType data;
    CTNode *firstchild;
}CTBox;
typedef struct CTree{
    CTBox nodes[MAX_SIZE];
    int n,r;
}CTree;

3.3 树的双亲孩子表示法

结点结构变为

data

parent（下标）

指向第一个孩子的指针

3.4 树的孩子兄弟表示法

typedef struct CSNode{
    datatype data;
    struct CSNode *firstchild,*rightsib;
}CSNode;

三.二叉树、树及森林的基本操作

1.二叉树的遍历

顺着某一条搜索路径寻访二叉树中的结点，使得每个结点均被访问一次，且仅被访问一次。

1.1 先序遍历：

根、左、右。

若二叉树非空，则：

1）访问根结点

2）先序遍历左子树

3）先序遍历右子树

typedef struct BiNode{
    int data;
    struct BiNode *rchild,*lchild;
}BiNode;
void preOrder(BiNode *root){
    if(root){
        cout<<root->data;
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}

1.2 中序遍历：

左、根、右。

若二叉树非空，则：

1）中序遍历左子树

2）访问根结点

3）中序遍历右子树

void inOrder(BiNode *root){
    if(root){
        inOrder(root->lchild);
        cout<<root->data;
        inOrder(root->rchild);
    }
}

中序遍历的非递归算法：

1.初始化栈，将根结点入栈。

2.如果栈空则结束（空树或所有结点处理完毕），否则进入下一步。

3.p指向栈顶元素，如果p不空，则左孩子入栈，直到左孩子为空。

4.如果栈不空，则出栈，输出该结点，再将其右孩子入栈。以该结点为本子树的根，转步骤2继续。

void InOrder(BiNode *root){
    stack <BiNode*> s;
    BiNode* p=root;
    s.push(p);
    while(!s.empty()){
        while(p->lchild){//走到最左边
            p=p->lchild;
            s.push(p);
        }
        p=s.top();//弹栈
        s.pop();
        cout<<p->data;
        if(p->rchild){
            s.push(p->rchild);
        }
    }
}

1.3 后序遍历：

左、右、根。

若二叉树非空，则：

1）后序遍历左子树

2）后序遍历右子树

3）访问根结点

void postOrder(BiNode *root){
    if(root){
        postOrder(root->lchild);
        postOrder(root->rchild);
        cout<<root->data;
    }
}

1.4 层次遍历：

从上到下、从左到右。

初始化队列，根结点入队列。

如果队列不空，则出队列并访问该结点；该结点左孩子入队，右孩子入队；如果队列为空，则层次遍历结束。

void levelOrder(BiNode *root){
    queue <BiNode*> s;
    BiNode* p=root;
    s.push(p);
    while(!s.empty()){
        p=s.front();
        s.pop();
        cout<<p->data;
        if(p->lchild){
            s.push(p->lchild);
        }
        if(p->rchild){
            s.push(p->rchild);
        }
    }
}

1.5 对遍历的分析：

从前面的三种遍历算法可以知道，如果将输出语句抹掉，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。

从虚线的出发点到终点的路径上，每个结点经过三次。

第一次经过时访问=先序遍历
第二次经过时访问=中序遍历
第三次经过时访问=后序遍历

1.6 二叉树遍历算法的应用举例：

1.6.1 表达式树：

算数表达式可以表示为一棵二叉树中缀表达——对树进行中序遍历即可得到表达式。

前缀表达式：不含括号的算数表达式，将运算符写在前面，操作数写在后面。
中缀表达式：操作符以中缀形式处于操作数中间。
后缀表达式：不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格的从左到右进行（不再考虑运算符的优先次序）

表达式树的构建：（即：给出一个中序序列，构建出这棵树）

顺序扫描中缀表达式明确：左子树的优先级高

当扫描到的是运算数：先检查当前的表达式树是否存在。如果不存在，则表示扫描到的是第一个运算数，将它作为树根。如果树存在，则将此运算数作为前一运算符的右孩子。
如果扫描到的是+或-：将它作为根结点，原来的树作为它的左子树。
如果扫描到的是*或/：则与根结点进行比较。如果根节点也是*或/，则根结点应该先执行，于是，将当前的运算符作为根结点，原来的树作为左子树。如果根结点是+或-，则当前运算符应该先运算，于是将它作为右子树的根，原来的右子树作为它的左子树。

在遇到运算数时，如何知道它前面的运算符是谁？这只需要判别根结点有没有右孩子。如果没有右孩子，则运算数是根节点的右运算数，否则就是根结点右孩子的右运算数。

1.6.2 由先序和中序遍历序列建立二叉树：

可以唯一的确定一棵二叉树。

void PreInorder(char preorder[],char inorder[],int first1,int end1,int first2,int end2,BiNode *t){
    //先序序列从first1到end1，中序序列从first2到end2，建立一棵二叉树放在t中
    int m;
    t=new BiNode;
    t->data=preorder[first1];//二叉树的根
    m=first2;
    while(inorder[m]!=preorder[first1]){//在中序序列中定位根结点的位置
        ++m;
    }
    //建立左子树
    if(m==first2){//左子树为空
        t->lchild=NULL;
    }
    else{
        PreInorder(preorder, inorder, first1+1, first1+m-first2, first2, m-1, t->lchild);
    }
    //建立右子树
    if(m==end2){//右子树为空
        t->lchild=NULL;
    }
    else{
        PreInorder(preorder, inorder, first1+m+1-first2, end1, m+1, end2, t->rchild);
    }
}
void CreateBiTree(char preorder[],char inorder[],int n,BiNode *root){
    if(n<=0){
        root=NULL;
    }
    else{
        PreInorder(preorder, inorder, 0, n-1, 0, n-1, root);
    }
}

1.6.3 二叉树中叶子结点的统计：

先序（中序或后序）遍历二叉树，在遍历过程中查找叶子节点，将算法中“访问结点”的操作改为：判定是否为叶子结点。

叶子结点：左右孩子均为空。

1.6.4 二叉树的深度：

空树：深度=0；

左右子树为空：深度=1；

其他：深度等于1+max（左子树深度，右子树深度）

int get_depth(BiNode *t){
    if(t==NULL){
        return 0;
    }
    else if(t->lchild==NULL&&t->rchild==NULL){
        return 1;
    }
    else{
        int depth;
        int depth1=get_depth(t->lchild);
        int depth2=get_depth(t->rchild);
        depth=max(depth1,depth2);
        return depth;
    }
}

2.树和森林的基本操作

2.1 树以及森林和二叉树的相互转换

1）树->二叉树

兄弟加线，每一个结点只保留与第一个孩子的连线，再进行旋转。

树转换成的二叉树，其根结点的右子树一定为空。

想要有右子树，就必须要有兄弟。将兄弟作为右子树。

2）二叉树->树

结点与其右子树、右子树的右子树加线，去掉结点与右子树的连线，再进行旋转。

3）森林->二叉树

将森林中的每一棵树都先转化为二叉树，再令第i棵树作为第i-1棵树的右子树。

4）二叉树->森林

断开根结点与右子树的关系，再将右子树作为新树，依次断开根结点与右子树的关系，直至右子树为空，得到了多棵二叉树。

再将这些二叉树转化为树。

2.2 树的遍历

先序遍历
后序遍历
层次遍历

没有中序遍历是因为树不分左右子树

2.3 森林的遍历

先序遍历：先序遍历每一棵树
中序遍历：后序遍历每一棵树

四.二叉树的变形

1.二叉排序树（BST）

对于二叉排序树的插入和删除操作：我们需要改变指针指向的地址，而在函数中传递指针，只能够改变指针指向的内容，所以要传递指针的引用。

1.1 定义（具有递归性质）：

二叉排序树或是一颗空树，或是一棵具有以下性质的树

（1）若它的左子树不空，则它左子树上所有结点的值均小于根结点的值。

（2）若它的右子树不空，则它右子树上所有结点的值均大于根结点的值。

（3）它的左右子树都是二叉排序树

1.2 二叉排序树的查找：

在二叉排序树中查找给定k值的过程是：

1）若root是空树，则查找失败

2）若k=root->data,则查找成功，否则

3）若k<root->data，则在root的左子树上查找；否则

4）在root的右子树上查找。

上述过程一直持续到k被找到或者待查找的子树为空。如果待查找的子树为空，则查找失败。

只需要查找两个子树之一。

BiNode* search(BiNode *root,int key){
    if(root==NULL){
        return NULL;
    }
    else{
        while(key!=root->data){
            if(key>root->data){
                root=root->rchild;
            }
            else if(key<root->data){
                root=root->lchild;
            }
            else{
                break;
            }
        }
               return root;
    }
}

1.3 二叉排序树的插入：

若二叉排序树为空树，则新插入的结点为新的根结点；否则新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。

void insert(BiNode *&root,int key){
    BiNode *p;
    if(root==NULL){
        p=new BiNode;
        p->data=key;
        p->lchild=NULL;
        p->rchild=NULL;
    }
    else{
        if(key<root->data){
            insert(root->lchild, key);
        }
        else{
            insert(root->rchild,key);
        }
    }
}

二叉排序树的构造：

BiSortTree::BiSortTree(int array[],int n){
    root=NULL;
    for(int i=0;i<n;i++){
        insertBST(root, array[i]);
    }
}

二叉排序树构造算法总结：
1）一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列

2）每次插入的新结点都是二叉排序树上新的叶子结点

3）找到插入位置后，不必移动其它结点，仅需修改某个结点的指针

4）在左子树/右子树的查找过程与在整棵树上查找过程相同

5）新插入的结点没有破坏原有结点之间的关系

注：

此处函数参数为指针的引用类型

1）只传指针的话，只能改变指针最初的指向的内容，而不能够改变指针所指向的地址。

2）而采用指针的引用，实际上改变指针，就改变了指针指向的地址。

3）这样做，还能够直接链接起根结点和孩子之间的指针关系。（bt->lchild/rchild 就被赋值为下一级函数所开辟出空间的地址）

1.4 二叉排序树的删除：

在二叉排序树上删除某个结点之后，仍然保持二叉排序树的特性。

1）被删除的结点是叶子

删除该结点，并将该结点的双亲的孩子指针域赋值为空

2）被删除的结点只有左子树或只有右子树

将双亲结点相应的指针域的值指向被删除结点的左/右孩子

3）被删除的结点既有左子树，又有右子树

以其左子树的最大值或右子树的最小值来代替该结点

以其前驱替代，然后再删除前驱结点

void deleteNode(BiNode *&bt){
    BiNode *p=bt;
    if(bt->lchild==NULL&&bt->rchild==NULL){//叶子结点
        bt=NULL;//该结点的双亲结点的相应孩子指针被赋值为空
        delete p;//返回时，其双亲的左右孩子指针均被赋值为NULL
    }
    if(bt->lchild==NULL){//该结点的左孩子为空，只有右子树
        bt=bt->rchild;
        delete p;
    }
    if(bt->rchild==NULL){//该结点的右孩子为空，只有左子树
        bt=bt->lchild;
        delete p;
    }
    else{//左右子树均存在，选取其前驱作为新的根结点
        BiNode *parent=bt,*pre=bt->lchild;
        while(pre->rchild){//找到左子树值最大的结点，parent保存这个结点的双亲结点
            parent=pre;
            pre=pre->rchild;
        }
        bt->data=pre->data;//用该结点的直接前驱替代该结点，并删除该结点的直接前驱
        if(parent==bt){
            parent->lchild=pre->lchild;
        }
        else{
            parent->rchild=NULL;
        }
        delete pre;
    }
}

二叉排序树的性能取决于二叉树的形状

2.平衡二叉树

2.1 定义：

平衡二叉树或者是一颗空树，或者是具有下列性质的二叉树：

是一棵二叉排序树
并且任何结点的左右子树的深度之差不超过1

2.2 构造平衡二叉树：

在插入过程中，采用平衡旋转技术。

1）平衡因子BF（Balance Factor）：

左子树高度 - 右子树高度的值

平衡因子的绝对值大于1，就需要进行调整。

2）最小不平衡子树：

距离插入结点最近的，且BF的绝对值大于1的结点。

旋转只需要纠正最小不平衡子树即可。

3）右旋：

旧根结点为新根结点的右子树
新根结点的右子树（如果存在）为旧根结点的左子树

4）左旋：

旧根结点为新根结点的左子树
新根结点的左子树（如果存在）为旧根结点的右子树

2.3 四种类型的旋转

1）LL型

2）RR型

3）LR型

最小不平衡子树根结点左子树先左旋，最小不平衡子树再右旋

4）RL型

最小不平衡子树根结点右子树先右旋，最小不平衡子树再左旋

3.最优树——哈夫曼树

3.1哈夫曼编码

1）前缀码：

对每一个字符规定一个0，1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。

2）前缀码的平均码长：

每个字符频率乘以该字符编码的bit数之和。

3）最优前缀码：

寻找最小的前缀码的平均码长。

4）最优树：

称树的带权路径长度最短的一类树为“最优树”。

3.2 哈夫曼树的构造

（1）初始化：
由给定的 n个权值构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合。

（2）选取与合并：
在二叉树集合中选取根结点的权值最小的两颗二叉树分别作为左、右子树构造一颗新的二叉树，这颗新的二叉树的根结点的权值为其左、右子树根结点的权值之和。

（3）删除与加入
在二叉树集合中删去作为左、右子树的二叉树，并将新建立的二叉树加入到二叉树结合中。

（4）重复
重复（2）（3）两步，直到二叉树集合中只剩下一颗二叉树。

哈夫曼树的左右子树可以进行交换。

有n个叶子结点的哈夫曼树有2n-1个结点。

3.3 哈夫曼算法的实现：

1）存储结构：

weight

lchild

rchild

parent

由于有n个叶子结点的哈夫曼树有2n-1个结点，设置数组长度为2n-1。

2）伪代码：

1.数组huffTree初始化：

所有元素结点的双亲、左右孩子都置为-1.

2.权值给定：

数组huffTree的前n个元素的权值给定

3.进行n-1次合并：

3.1 在二叉树集合中选取两个权值最小的根结点，其下标为i1，i2

3.2 将二叉树i1，i2合并为一棵新的二叉树

struct element{
    int weight;
    int lchild,rchild,parent;
};
void select(struct element huffTree[],int k,int &i1,int &i2){
    for(int i=0;i<k;i++){//初始化i1，i2
        if(huffTree[i].parent==-1){
            i1=i2=i;
            break;
        }
    }
    for(int i=0;i<k;i++){
        if(huffTree[i].parent==-1&&huffTree[i].weight<huffTree[i1].weight){
            i1=i;
        }
    }
    for(int i=0;i<k;i++){
        if(huffTree[i].parent==-1&&i!=i1&&huffTree[i].weight<huffTree[i2].weight){
            i2=i;
        }
    }
}
void huffmanTree(struct element huffTree[],int w[],int n){
    int i1,i2,i;
    for(i=0;i<2*n-1;i++){
        huffTree[i].parent=huffTree[i].lchild=huffTree[i].rchild=-1;
    }
    for(i=0;i<n;i++){
        huffTree[i].weight=w[i];
    }
    for(i=n;i<2*n-1;i++){
        select(huffTree, i, i1, i2);
        huffTree[i].weight=huffTree[i1].weight+huffTree[i2].weight;
        huffTree[i1].parent=i;
        huffTree[i2].parent=i;
        huffTree[i].lchild=i1;
        huffTree[i].rchild=i2;
    }
}

4.堆排序

4.1 堆的定义：

堆通常是一个可以被看作一棵完全二叉树的数组对象。

每个结点的值都小于或等于其左右孩子结点的值（称为小根堆）

或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）

特点：

1.大根堆的根结点是所有结点中值最大的结点。

2.较大结点靠近根节点，但不绝对。

3.每次创建一个堆，都使数据基本有序。

4.2 堆排序的思想：

首先，将待排序的记录序列构造成一个堆（大根堆），此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样，又找出了次大的记录，以此类推，直到堆中只有一个记录。

4.3 堆的存储：

将堆用顺序结构存储，则堆就对应了一组序列。

根据完全二叉树的性质：

结点i的双亲结点编号为i/2，左孩子为2i，右孩子为2i+1

4.4 堆调整：

在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？

建立堆，从下向上调整；调整堆时，从上向下处理。

首先，根和他两个孩子中较大的那个比较，如果根比较大，不做处理；如果根比较小，则交换，交换后，再去看交换的结果是否影响下面的堆。

4.5 如何处理堆顶元素？

堆顶就是r[1]。

第k次处理堆顶，就是将堆顶记录r[1]与r[n-k+1]交换。

4.6 代码：

void sift(int r[],int k,int end){
    //当前处理的根结点的编号为k，堆中最后一个结点的编号为k
    int i=k;
    int j=2*i;
    int temp;
    while(j<=end){
        if(j<end&&r[j]<r[j+1]){//找到左右孩子中较大的那个
            j++;
        }
        if(r[i]<r[j]){
            temp=r[i];
            r[i]=r[j];
            r[j]=temp;
        }
        i=j;
        j=2*i;
    }
}
void heapsort(int r[],int n){
    //初始化，得到一个初始堆
    for(int k=n/2;k>=1;k--){
        sift(r,k,n);
    }
    for(int k=1;k<n;k++){//最大的元素往后挪，堆逐渐缩小
        r[0]=r[1];
        r[1]=r[n-k+1];
        r[n-k+1]=r[0];
        sift(r,1,n-k);
    }
}

时间复杂度：

O(nlog_2n)

不稳定排序