树-二叉树-二叉搜索树

1. 二叉树基础

2021-06-23 468 1

简介 介绍树、二叉树、二叉搜索树的基本概念以及操作,分析了时间复杂度

    学习树这种数据结构之前,需要熟悉数组、链表、栈、队列,如果都已经熟悉了,那么学习树就容易多了。

    首先来看几棵树,让大家对树有个大致的认识

upfile


关于树的几个概念

    父结点、子结点、兄弟结点、 根结点、叶子结点

    A 节点就是 B 节点的父节点,B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点,所以它们之间互称为兄弟节点。我们把没有父节点的节点叫做根节点,也就是图中的节点 E。我们把没有子节点的节点叫做叶子节点或者叶节点,比如图中的 G、H、I、J、K、L 都是叶子节点。

upfile


    高度、深度、层次

    结点的高度: 结点到叶子结点的最长路径

    结点的深度:根结点到这个结点的路径长度

    结点的层次: 结点的深度 加 1

    树的高度: 根结点的高度


upfile


二叉树、完全二叉树、满二叉树

    树结构多种多样,不过最常用还是二叉树。二叉树,每个节点最多有两个“叉”,也就是两个子节点,分别是左子节点和右子节点。但是不要求每个节点都有两个子节点,有的节点只有左子节点,有的节点只有右子节点。以下三棵树都是二叉树:


upfile


    叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点,这种二叉树就叫做满二叉树(上图中的第二棵树)

叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫做完全二叉树(上图中的第三棵树)以下两棵树不是完全二叉树

upfile


二叉树的存储方式

    想要存储一棵二叉树,我们有两种方法,一种是基于指针或者引用的二叉链式存储法,一种是基于数组的顺序存储法。

    链式存储法。从图中你应该可以很清楚地看到,每个节点有三个字段,其中一个存储数据,另外两个是指向左右子节点的指针。我们只要拎住根节点,就可以通过左右子节点的指针,把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。

upfile


    基于数组的顺序存储法。我们把根节点存储在下标 i = 1 的位置,那左子节点存储在下标 2 * i = 2 的位置,右子节点存储在 2 * i + 1 = 3 的位置。以此类推,B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置,右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。


upfile


    节点 X 存储在数组中下标为 i 的位置,下标为 2 * i 的位置存储的就是左子节点,下标为 2 * i + 1 的位置存储的就是右子节点。反过来,下标为 i/2 的位置存储就是它的父节点。

    堆其实就是一种完全二叉树,最常用的存储方式就是数组。


二叉树的遍历

    经典的方法有三种,前序遍历、中序遍历和后序遍历。其中,前、中、后序,表示的是节点与它的左右子树节点遍历的先后顺序。

    前序遍历是指,对于树中的任意节点来说,先遍历这个节点,然后再遍历它的左子树,最后遍历它的右子树。

    中序遍历是指,对于树中的任意节点来说,先遍历它的左子树,然后再遍历它本身,最后遍历它的右子树。

    后序遍历是指,对于树中的任意节点来说,先遍历它的左子树,然后再遍历它的右子树,最后遍历这个节点本身。

    二叉树的前、中、后序遍历就是一个递归的过程。比如,前序遍历,其实就是先遍历根节点,然后再递归地遍历左子树,最后递归地遍历右子树。

    二叉树的遍历代码模板

    # Python

    def recursion(level, param1, param2, ...): 

        # recursion terminator 

        if level > MAX_LEVEL: 

       process_result 

       return 

        # process logic in current level 

        process(level, data...) 

        # drill down 

        self.recursion(level + 1, p1, ...) 

        # reverse the current level status if needed

    // Java

    public void recur(int level, int param) { 

      // terminator 

      if (level > MAX_LEVEL) { 

        // process result 

        return; 

      }

      // process current logic 

      process(level, param); 

      // drill down 

      recur( level: level + 1, newParam); 

      // restore current status 

     

    }

    // C/C++

    void recursion(int level, int param) { 

      // recursion terminator  递归终止条件

      if (level > MAX_LEVEL) { 

        // process result 

        return

      }

      // process current logic   处理当前递归层的逻辑

      process(level, param);

      // drill down   处理子问题

      recursion(level + 1, param);

      // reverse the current level status if needed   处理当前递归层的状态

    }


二叉搜索树(Binary Search Tree)

    二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值。

upfile


    1. 二叉查找树的查找操作

    先取根节点,如果它等于我们要查找的数据,那就返回。如果要查找的数据比根节点的值小,那就在左子树中递归查找;如果要查找的数据比根节点的值大,那就在右子树中递归查找。


upfile


2. 二叉查找树的插入操作

    如果要插入的数据比节点的数据大,并且节点的右子树为空,就将新数据直接插到右子节点的位置;如果不为空,就再递归遍历右子树,查找插入位置。同理,如果要插入的数据比节点数值小,并且节点的左子树为空,就将新数据插入到左子节点的位置;如果不为空,就再递归遍历左子树,查找插入位置。


upfile


3. 二叉查找树的删除操作

    需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。然后再删除掉这个最小节点,因为最小节点肯定没有左子节点(如果有左子结点,那就不是最小节点了),所以,我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。


upfile


支持重复数据的二叉查找树

    第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据,因此我们通过链表和支持动态扩容的数组等数据结构,把值相同的数据都存储在同一个节点上。

    第二种方法比较不好理解,不过更加优雅。

    每个节点仍然只存储一个数据。在查找插入位置的过程中,如果碰到一个节点的值,与要插入数据的值相同,我们就将这个要插入的数据放到这个节点的右子树,也就是说,把这个新插入的数据当作大于这个节点的值来处理。

upfile

    当要查找数据的时候,遇到值相同的节点,我们并不停止查找操作,而是继续在右子树中查找,直到遇到叶子节点,才停止。这样就可以把键值等于要查找值的所有节点都找出来。

upfile


对于删除操作,我们也需要先查找到每个要删除的节点,然后再按前面讲的删除操作的方法,依次删除。

upfile


二叉查找树的时间复杂度分析

    二叉查找树的形态各式各样,比如这个图中,对于同一组数据,我们构造了三种二叉查找树。它们的查找、插入、删除操作的执行效率都是不一样的。图中第一种二叉查找树,根节点的左右子树极度不平衡,已经退化成了链表,所以查找的时间复杂度就变成了 O(n)。二叉查找树是一棵完全二叉树(或满二叉树)。这个时候,插入、删除、查找的时间复杂度O(height),对于完全二叉树的height是小于等于 log2n,平衡二叉查找树的高度接近 logn,所以插入、删除、查找操作的时间复杂度也比较稳定,是 O(logn)。

upfile

点赞 1

文章评论

欢迎您:

纸上得来终觉浅,绝知此事要躬行!

112 文章 57774 浏览 3 评论

联系我

  •   QQ:    361352119
  •  Email:  lisimmy@sina.com
  • 微信: