【数据结构】树

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

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

证明如下:

二叉树中全部结点数n=n_0+n_1+n_2

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

n=B+1

B=n_1+2n_2(1度结点必有1个直接后继,2度结点必有2个直接后继)

n_0+n_1+n_2=n_1+2n_2+1

即:

n_0=n_2+1

叶子数=2度结点数+1

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

5)

对有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 二叉链表:

结点结构:

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

 2.2 三叉链表:

结点结构:

parentlchilddatarchild
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 树的双亲孩子表示法

结点结构变为

dataparent(下标)指向第一个孩子的指针

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)存储结构:

weightlchildrchildparent

 由于有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)

不稳定排序