基本概念

树的定义:树是$N(N\geqslant 0)$个结点的有限集合。特别的，当$N=0$时，称为空树。

任意非空树满足的条件：

  • 有且仅有一个特定的称为根的结点
  • 当$N>1$时，其余结点可分为$m$个互不相交的有限集合$T_1,T_2,\dots,T_m$,其中每个集合本身又是一棵树，并且称为根结点的子树

树是一种递归的数据结构

  • 根结点无前驱结点，除根结点外的其余所有结点有且仅有一个前驱结点
  • 树中所有结点可以有零个或多个后继结点

基本术语

  1. 结点$K$,结点$A,B,E$为到结点$K$的唯一路径上的结点，$A,B$为$K$的祖先结点，$K$为$A,B$的子孙结点；$E$为$K$的双亲结点，$K$为$E$的孩子结点，有相同双亲的结点为兄弟结点，如$K$和$L$互为兄弟节点；
  2. 树中一个子结点的个数称为该结点的度，树中结点的最大度数称为树的度；
  3. 度大于$0$的结点称为分支结点,如$B,C,D$,度为$0$的结点称为叶子结点，如$K,L,M$；
  4. 树的深度为树中结点的最大层数，如图的树形结构深度为4
  5. 两个结点之间的路径为两个结点之间所经过的结点序列，路径长度为路径上经过的边的个数，如$A$到$K$的路径长度为3；
  6. 森林是$m$课互不相交的树的集合；

二叉树概念

定义:每个结点至多只有两颗子树的树形结构，即二叉树中不存在度大于2的结点，二叉树有左右之分，次序不可颠倒。

二叉树的形态：

满二叉树：一颗高度为$h$，并且含有$2^h-1$个结点的二叉树

对于编号$i$结点，如果有双亲，其双亲为[$i/2$]，如果孩子结点，左孩子为$2i$,右孩子为$2i+1$

完全二叉树：设深度为$h$，有$n$个结点的二叉树，当且仅当其每一个结点都与深度为$h$的满二叉树中编号为$1\sim n$的结点一一对应，称为完全二叉树。

特点：

  1. 若$i\leqslant[n/2] $,则结点$i$为分支节点，否则为叶子节点；
  2. 如果有度为1的结点，只可能有一个，且该结点只有左孩子无右孩子；

平衡二叉树：树上任一结点的左子树和右子树的深度差不超过1

二叉树的性质：

  1. 非空二叉树上叶子结点数等于度为2的结点数加1，即$N_0=N_2+1$
  2. 非空二叉树上第$K$层至多有$2^{k-1}个结点(K\geqslant 1)$
  3. 深度为$h$的二叉树至多有$2^{h}-1$个结点
  4. 对于具有$1 \sim n$编号的完全二叉树，具有如下关系
    • 当$i>1$时，结点$i$的双亲结点编号为$[i/2]$,当$i$为偶数时其为双亲结点的左孩子，当$i$为奇数时其为双亲结点的右孩子
    • 当$2i\leqslant n $时，结点$i$的左孩子编号为$2i$，否则无左孩子
    • 当$2i+1\leqslant n $时，结点$i$的左孩子编号为$2i +1$，否则无右孩子
    • 结点$i$所在深度为$[\log _2{i}+1]$
  5. 具有$n$个结点的完全二叉树的深度为$[\log _2{(n+1)}]$或$[\log _2{n}]+1$

二叉树的顺序存储

将完全二叉树上编号为$i$的结点元素存储在某个数组下标为$i-1$的分量中。

对于一般的二叉树，使用0表示不存在的空结点，下标从1开始。

二叉树的链式存储

typedef struct biTreeNode{
    ElemType data;
    struct biTreeNode *left,*right;//左右孩子指针
}biTreeNode,*biTree;

二叉树遍历

  1. 先序遍历

    访问根结点$\rightarrow$先序遍历左子树$\rightarrow $先序遍历右子树

    void preOrder(BiTree tree){
    if(tree != null){
        visit(tree);
        preOrder(tree->left);
        preOrder(tree->right);
    }
}

  2. 中序遍历

    中序遍历左子树$\rightarrow$访问根结点$\rightarrow $中序遍历右子树

    void inOrder(BiTree tree){
    if(tree != null){
        inOrder(tree->left);
        visit(tree);
        inOrder(tree->right);
    }
}

  3. 后序遍历

    后序遍历左子树$\rightarrow$后序遍历右子树$\rightarrow $访问根结点

    void postOrder(BiTree tree){
    if(tree != null){
        postOrder(tree->left);
        postOrder(tree->right);
        visit(tree);
    }
}

    • 先序遍历：1 2 4 6 3 5
    • 中序遍历：2 6 4 1 3 5
    • 后序遍历：6 4 2 5 3 1

  4. 非递归遍历算法

    //中序遍历非递归算法
void inOrder*(BiTree tree){
    initStack(stack);//初始化栈
    BiTree p = tree;//遍历指针
    while(p || !isEmpty(stack)){
        if(p){
            push(stack,p);
            p = p->left;
        }
        else{
            pop(stack,p);
            visit(p);
            p = p->right;
        }
    }
}

  5. 层次遍历

    按图中箭头的顺序进行遍历，先访问第一层，再访问第二层,$\dots$

    void levelOrder(BiTree tree){
    initQueue(queue);
    biTree p;
    enQueue(queue,tree);//根节点入队
    while(!isEmpty(queue)){
        deQueue(queue,p);//队头元素出队
        visit(p);
        if(p->left != null)
            enQueue(queue,p->left);
        if(p->right != null)
            enQueue(queue,p->right);
    }
}

  6. 根据遍历序列构造二叉树

    • 二叉树的先序序列和中序序列可以唯一确定一颗二叉树。先序序列中，第一结点为根节点，在中序序列中，根结点将其分为两个子序列，根据该子序列在先序序列中找到对应的左子序列和右子序列，其先序序列中，左子序列第一个结点为左子树的根节点，右子序列的第一个结点为右子树的根结点，如此递归。
    • 二叉树的后序序列和中序序列可以唯一确定一颗二叉树。后序序列的最后一个结点为根节点。
    • 层次遍历序列和中序序列可以唯一确定一颗二叉树。

    求先序序列$ABCDEFGHI$和中序遍历$BCAEDGHFI$所确定的二叉树

线索二叉树

二叉树线索化时通常规定，若无左子树，令leftChild指向其前驱结点，leftTag = 1；若无右子树，令right-child指向其后继结点,rightTag = 1。

线索二叉树的存储结构

typedef struct threadNode{
    ElemType data;
    struct threadNode *leftChild,rightChild;
    int leftTag,rightTag;
}

线索二叉树的构造

//中序遍历-二叉树线索化
//指针pre指向中序遍历时上一个刚刚访问过的结点
void inThreadNode(threadNode &p,threadNode &pre){
    if(p != null){
        inThreadNode(p->leftChild,pre);//递归线索化左子树
        if(p->leftChild == null){ //建立前驱线索
            p->leftChild = pre;
            p->leftTag = 1;
        }
        if(pre != null && pre->rightCihld == null){//建立后继线索
            pre->rightChild = p;
            pre->rightTag = 1;
        }
        pre = p;
        inthreadNode(p->rightChild,pre);//递归线索化右子树
    }
}

void createInThreadNode(threadNode T){
    threadNode pre = null;
    if(T != null){
        inThreadNode(T,pre);
        pre->rightChild = null;//处理遍历的最后一个结点
        pre->rightTag = 1;
    }
}

线索二叉树的遍历

  • 求中序线索二叉树中中序序列的第一个结点

    threadNode * firstNode(threadNode *p){
    while(p->leftTag == 0)
        p = p->leftChild;
    return p;
}

  • 求中序线索二叉树中结点p在中序序列下的后继结点

    threadNode * nextNode(threadNode *p){
    if(p->rightTag == 0)
        return firstNode(p->rightChild);
    else return p->rightChild;
}

  • 遍历算法

    void * inThreadNode(threadNode *T){
    for(threadNode *p = firstNode(T);p != NULL;p = nextNode(p))
        visit(p);
}

树的存储结构

  1. 双亲表示法

    #define MAX_TREE_SIZE 100
typedef struct{
    ElemType data;//数据
    int parent;//双亲位置域
}Node;
typedef struct{
    Node nodes[MAX_TREE_SIZE];
    int n;//结点数
}Tree;

  2. 孩子表示法

    将每个结点的孩子结点都用单链表链接起来形成一个线性结构

  3. 孩子兄弟表示法

    以二叉链表作为树的存储结构，每个结点包括：结点值、指向结点第一个孩子的指针、指向结点下一个兄弟结点的指针

    typedef struct Node{
    ElemType data;//数据
    struct Node *firstChild,*nextSibling;//第一个孩子和兄弟指针
}Node,*Node;

树、森林与二叉树的转换

树转换为二叉树的规则：每个结点的左指针指向它的第一个孩子结点，右指针指向它在树中的相邻兄弟结点，由于根结点没有兄弟，因此由树转换而来的二叉树没有右子树。

树与二叉树的应用

  1. 并查集

  2. 二叉排序树

    定义：

    • 若左子树非空，则左子树上所有结点关键值均小于根节点的关键值
    • 若右子树非空，则右子树上所有结点关键值均大于根节点的关键值
    • 左右子树本身也为一颗二叉排序树

    二叉排序树的查找

    从根节点开始，若给定值与根结点关键值相等则查找成功；若根结点大于给定值则在左子树中查找；若根结点小于给定值则在右子树中查找

    //查找函数返回指向关键值为key的结点指针p
biTreeNode * biTreeNodeSearch(biTree tree,ElemType key){
    while(tree != NULL && key != tree->data){
        if(key < tree->data)
            tree = tree->leftChild;
        else
            tree = tree->rightChild;
    }
    return tree;
}

    二叉排序树的插入

    若原二叉树为空，则直接插入结点；若根结点大于给定值则插入到左子树中；若根结点小于给定值则插入到右子树中

    ![15](F:\jiaopaner\source\images\dataStructure\15.jpg)bool biTreeNodeInsert(biTree tree,ElemType key){
    if(tree == null){
        tree = (biTree)malloc(sizeof(biTreeNode));
        tree->data = key;
        tree->leftChild=  tree-rightChild = NULL;
        return true;
    }
    else if(key == tree->data)
        return false;
    else if(key < tree->data)
        return biTreeNodeInsert(tree->lefgChild,key);
    else if(key > tree->data)
        return biTreeNodeInsert(tree->rightChild,key);
}

    二叉排序树的删除

    • 删除的结点为叶结点，则直接删除，不会破坏二叉树的排序性质

    • 若删除结点$z$只有一颗左子树(或右子树)，则让$z$的左子树(或右子树)成为$z$结点的父结点的子树，即代替$z$的位置

    • 若删除结点$z$有左、右子树，则令$z$的右子树中中序第一个子女代替$z$，并转换相应的位置

  3. 平衡二叉树

    定义：任意结点的左右子树高度差不超过1的二叉排序树

    平衡二叉树的插入

    平衡二叉树插入新结点会破坏平衡性，因此插入新结点后需要做调整，以重新达到平衡性

    平衡性调整策略

    • LL平衡旋转(右单旋转)

      在根结点$A$的左孩子(L)结点$B$的左子树(L)结点$BL$上插入了结点,破坏了平衡性的调整策略，$B$结点右上旋转代替$A$成为根结点，$A$结点成为$B$的右子树根结点，且$B$的右子树作为$A$结点的左子树

    • RR平衡旋转(左单旋转)

      在根结点$A$的右孩子(R)结点$C$的右子树(R)结点$CR$上插入了结点,破坏了平衡性的调整策略，$C$结点左上旋转代替$A$成为根结点，$A$结点成为$C$的左子树根结点，且$C$的左子树作为$A$结点的右子树

    • LR平衡旋转(先左后右双旋转)

      在根结点$A$的左孩子(L)结点$B$的右子树(R)结点$BR$上插入了结点,破坏了平衡性的调整策略

    • RL平衡旋转(先右后左双旋转)

      在根结点$A$的右孩子(R)结点$C$的左子树(L)结点$CR$上插入了结点,破坏了平衡性的调整策略

  4. 哈夫曼树和哈夫曼编码

    树结点赋予权值，从根结点到任意结点的路径长度(经过的边数)与该结点权值的乘积称为该结点的带权路径长度，树中所有叶结点的带权路径长度之和称为该树的带权路径长度$WPL$。

    其中$w_i$为第$i$个叶结点的权值，$l_i$为根结点到第$i$个叶结点的路径长度

    在含有$n$个带权叶子结点的二叉树中，其中$WPL$最小的二叉树称为哈夫曼树(最优二叉树)

    $WPL(a)=7\times2+5\times2+2\times2+4\times2=36$

    $WPL(b)=7\times3+5\times3+1\times2+4\times2=46$

    $WPL(c)=7\times1+5\times2+2\times3+4\times3=35$

    $c$树为哈夫曼树

    哈夫曼树的构造

    • 将$n$个带权结点作为$n$课仅含一个结点的二叉树，构成森林$F$
    • 构造一个新结点$P$，并从$F$中选取两棵权值最小的树作为新结点的左、右子树，将新结点的权值置为左、右子树权值之和
    • 从$F$中删除上述选取的两棵树，同时将新结点$P$加入$F$中
    • 重复2、3步骤，直至$F$中只剩下一棵树

    哈夫曼编码

    对频率高的字符赋予短编码，对频率低的字符赋予长编码，从而使字符平均编码长度减短

    哈夫曼编码：对每个字符当作一个独立的结点，其权值为字符出现的次数，构造哈夫曼树

版权声明：原创,转载请注明来源,否则律师函警告


数据结构      数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 3.0协议 。转载请注明出处！