Liu, Jian's Blog

首页 归档 标签 关于

【数据结构】树与二叉树

2020-04-01 8 min read # 计算机考研

🔑【数据结构】之查找

树与二叉树

树的基本概念

树的定义

  • 非线性、一对多、唯一的根
  • 结点可以为0，为0时，称为空树
  • 子树从左到右有次序称为有序树，否则为无序树，二叉树为有序树

树的基本性质（牢记）

  • 树的结点数等于所有结点的度加一
  • 度为m的树中第i层上至多有mi−1m^{i-1}个结点
  • 高度为h的m叉树至多有(mh−1)(m−1)\frac{(m^h-1)}{(m-1)}个结点
  • 具有n个结点的m叉树的最小高度为log⁡mn(m−1)+1\log_m{n(m-1)+1}

二叉树

二叉树的定义

在满足树的定义基础上增加以下两个条件：

  • 每个结点最多有两子树，即二叉树中的结点的度只能为0、1、2
  • 子树有左右顺序之分，不能颠倒
    满二叉树：深度为k，有2k−12^k-1个结点
    完全二叉树：给满二叉树标号，从上至下，从左到右，n个结点的完全二叉树和对应满二叉树的编号相同（就是满二叉树顺序删除的结果）

二叉树的主要性质

  • 叶子节点等于双分支节点数加一，总分支数等于总结点数-1
  • 二叉树的第i层上最多有2i−12^{i-1}个节点
  • 深度为k的二叉树最多有2k−12^k-1个节点（等比求和公式）
  • 给定n个节点，能构成∁2nnn+1\frac{\complement_{2n}^n}{n+1}种二叉树
  • n个节点的完全二叉树深度为log⁡2n+1\log_2n+1
  • 节点编号为i，若!=1，则a的双亲节点为i/2，若2n<=n，a的左孩子为2i，若2i>n，则无左孩子；若2n+1<=n，a的右孩子为2i+1，若2i+1>n，则无右孩子

二叉树的存储结构

typedef struct BTNode
{
    ElemType data;
    struct BTNode *lchild,*rchild;//三叉链表在此基础上增加*parent指针
}BTNode;
  • 二叉链表存储n个结点共有n+1个空指针，三叉链表有n+2个

二叉树的遍历

  • 先序遍历
void preorder(BTNode *p)
{
    if(p!=NULL)
    {
        visit(p);
        preorder(p->lchild);
        preorder(p->rchild);
    }
}
  • 中序遍历
void inorder(BTNode *p)
{
    if(p!=NULL)
    {
        inorder(p->lchild);
        visit(p);
        inorder(p->rchild);
    }
}
  • 后序遍历
void postorder(BTNode *p)
{
    if(p!=NULL)
    {
        postorder(p->lchild);
        postorder(p->rchild);
        visit(p);
    }
}
  • 层次遍历
void level(BTNode *p)
{
    int front,rear;
    BTNode *que[maxSize];
    front=rear=0;
    BTNode *q;
    if(p!=NULL)
    {
        rear=(rear+1)%maxSize;
        que[rear]=p;
        while(front!=rear)
        {
            front=(front+1)%maxSize;
            p=que[front];
            visit(p);
            if(p->lchild!=NULL)
            {
                rear=(rear+1)%maxSize;
                que[rear]=p->lchild;
            }
            if(p->rchild!=NULL)
            {
                rear=(rear+1)%maxSize;
                que[rear]=p->rchild;
            }
        }
    }
}

由遍历序列构造二叉树

  • 已知前中序遍历，能确定唯一二叉树
  • 已知后中序遍历，能确定唯一二叉树
  • 已知层次和中序遍历，能确定唯一二叉树
  • 已知前后序遍历，不能确定唯一二叉树

二叉排序树

  • 二叉排序树或者是空数，或者是满足以下性质的二叉树：
    1. 若它的左子树不空，则左子树所有关键字的值小于根关键字的值
    2. 若它的右子树不空，则右子树所有关键字的值大于根关键字的值
  • 二叉排序树的插入：先查找，找不到则作为最后访问的叶子结点作为最后访问的叶子结点的孩子
//二叉排序树的查找
//递归算法（基本思路：若为空，返回；否则与根比较相等则找到，小于则从左子树继续找，大于则从右子树继续找）
BstTree BstSearch(BstTree bst, ElemType x)
{
    if(bst==NULL)
    return NULL;
    else if(bst->data==x)
    return bst;
    else if(x<bst->data)
    return BstSearch(bst->lchild,x);
    else return BstSearch(bst->rchild,x);
}

//非递归算法
BstTree BstSearch(BstTree bst, ElemType x)
{
    p=bst;
    while(p)
    {
        if(p->data==x)
        return p;//已找到
        else if(x<p->data)
        p=p->lchild;
        else p=p->rchild;
    }
    return NULL;//没找到
}
  • 二叉排序树的建立：经过一系列的插入操作即可建立
  • 二叉排序树的删除：
    1. 叶子结点直接删除
    2. 左子树或右子树为空：移花接木——将子树直接接到双亲上
    3. 左右子树都不为空：偷梁换柱——将左子树上的最大结点（或右子树上的最小结点）替换被删除结点
  • 二叉排序树的查找效率：结点层次等于查找的比较次数$$\frac{层次*层次结点个数}{结点总个数}$$
  • 关键字有序插入建立二叉排序树将得到一颗单支树，则其等价于顺序查找，平均比较次数为$$\frac{n+1}{2}$$

平衡二叉树（AVL树）

  • 其左右二叉树都是平衡二叉树，且左右子树高度之差的绝对值不超过1（树越矮效率越高）
    平衡因子指其左子树减去右子树高度的差，只能去-1、0、1
  • 平衡二叉树的构造：按照二叉排序树的方法插入结点，失去平衡时调整
  • 调整方法：rr、rl、ll、lr
  • 平衡二叉树的查找：同二叉排序树$$O(\log_2n)$$

二叉树遍历算法的改进（非递归遍历）

  1. 用栈的方式实现（了解）

  2. 线索二叉树（会画）

    • 二叉树的节点构造
    lchild ltag data rtag rchild
    • ltag，rtag=0表示孩子节点，=1 ltag指向前驱，rtag指向后继
    • 左边空指针为前驱，右边空指针为后继
    • 步骤：
      • 先标出所有空指针
      • 写出所需要遍历的结果
      • 标出前驱或者后继

树和森林

  • 树的存储结构：

    • 双亲表示法

      数组下标 结点数据 双亲结点的下标（根节点为-1）

    • 孩子表示法

      数组下标 结点数据 ->指向孩子结点下标
      数组下标 父结点下标 结点数据 ->指向孩子结点下标

    • 孩子兄弟表示法

      • 在兄弟之间增加指针
      • 优点：可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等
      • 缺点：从当前结点查找其双亲结点比较麻烦。如果为每个结点增设一个parent域指向其父结点，则查找结点的父结点也比较方便

  • 森林与二叉树的转换

    • 树和二叉树的对应关系

      树 对应的二叉树
      根
      第一个孩子
      下一个兄弟      		 根
      左孩子
      右孩子
      • 特点：由树转化成的二叉树，根结点没有右孩子

    • 森林与二叉树的转换：把第一棵树的根当做对应二叉树的根，其他数看做第一棵树的兄弟，然后将树转换成二叉树

  • 树和森林的遍历

    • 树的遍历：

      • 先根遍历：先访问根结点，然后依次访问先根遍历的每颗子树
      • 后根遍历：先访问后根遍历每颗子树，然后访问根结点

    • 森林遍历

      • 先序遍历森林：访问森林中第一棵树的根结点；先序遍历第一个树中根结点的子树森林；现需遍历除第一棵树之后剩余的树构成的森林
      • 中序遍历森林：中序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；访问第一棵树的根结点；中序遍历除第一棵树之后剩余的树构成的森林

    • 树、森林、二叉树遍历的关系

      树 森林 二叉树
      先根遍历 中序遍历 先序遍历
      后根遍历 中序遍历 中序遍历

树的应用

  • 赫夫曼树和赫夫曼编码
    • 赫夫曼树，又称最优树、哈夫曼树，是一类带权路径长度最短树
    • 树的带权路径长度：所有叶子结点的带权路径长度之和$$WPL=\sum_{k=1}^nw_kl_k$$注：路径长度lkl_k按分支数目计算
    • 构造赫夫曼树：每次取两个最小的树组成二叉树
    • 赫夫曼编码（前缀码）：向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀码
Powered by Gridea RSS