• 数据结构——树(树的概念、优缺点、二叉树)


    目录

    一、树的概念

    1、树的优点

             2、树的术语

    二、二叉树

    1、二叉树的概念

    2、二叉树的特性

    3、特殊的二叉树

             4、二叉树的存储


    一、树的概念

    1、树的优点

    数组: 

    - 优点: 
      - 数组的主要优点是根据下标值访问效率会很高.
      - 但是如果我们希望根据元素来查找对应的位置呢?
      - 比较好的方式是先对数组进行排序, 再进行二分查找.
    - 缺点: 
      - 需要先对数组进行排序, 生成有序数组, 才能提高查找效率.
      - 另外数组在插入和删除数据时, 需要有大量的位移操作(插入到首位或者中间位置的时候), 效率很低.

     链表: 

    - 优点: 
      - 链表的插入和删除操作效率都很高.
    - 缺点: 
      - 查找效率很低, 需要从头开始依次访问链表中的每个数据项, 直到找到.
      - 而且即使插入和删除操作效率很高, 但是如果要插入和删除中间位置的数据, 还是需要重头先找到对应的数据.

     树结构: 

    - 我们不能说树结构比其他结构都要好, 因为每种数据结构都有自己特定的应用场景.
    - 但是树确实也综合了上面的数据结构的优点(当然优点不足于盖过其他数据结构), 并且也弥补了上面数据结构的缺点.
    - 而且为了模拟某些场景, 我们使用树结构会更加方便. 比如文件的目录结构.

     

    2、树的术语

     树的定义:

    - 树(Tree): n(n≥0)个结点构成的有限集合。 
      - 当n=0时,称为空树;
      - 对于任一棵非空树(n> 0),它具备以下性质:
      - 树中有一个称为“根(Root)”的特殊结点,用 root 表示;
      - 其余结点可分为m(m>0)个互不相交的有限集T1,T2,... ,Tm,其中每个集合本身又是一棵树,称为原来树的“子树(SubTree)”
    - 注意: 
      - 子树之间不可以相交
      - 除了根结点外,每个结点有且仅有一个父结点;
      - 一棵N个结点的树有N-1条边。

    树的术语:

    - 1.结点的度(Degree):结点的子树个数.
    - 2.树的度:树的所有结点中最大的度数. (树的度通常为结点的个数N-1)
    - 3.叶结点(Leaf):度为0的结点. (也称为叶子结点)
    - 4.父结点(Parent):有子树的结点是其子树的根结点的父结点
    - 5.子结点(Child):若A结点是B结点的父结点,则称B结点是A结点的子结点;子结点也称孩子结点。
    - 6.兄弟结点(Sibling):具有同一父结点的各结点彼此是兄弟结点。
    - 7.路径和路径长度:从结点n1到nk的路径为一个结点序列n1 , n2,… , nk, ni是 ni+1的父结点。路径所包含边的个数为路径的长度。
    - 8.结点的层次(Level):规定根结点在1层,其它任一结点的层数是其父结点的层数加1。
    - 9.树的深度(Depth):树中所有结点中的最大层次是这棵树的深度。

    二、二叉树

    1、二叉树的概念

    • 二叉树的定义

      • 二叉树可以为空, 也就是没有结点.

      • 若不为空,则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

    • 二叉树有五种形态:

      • 注意c和d是不同的二叉树, 因为二叉树是有左右之分的.

    2、二叉树的特性

    二叉树有几个比较重要的特性, 在笔试题中比较常见:

    - 一个二叉树第 i 层的最大结点数为:2^(i-1), i >= 1;

    - 深度为k的二叉树有最大结点总数为: 2^k - 1, k >= 1;

    - 对任何非空二叉树 T,若n0表示叶结点的个数、n2是度为2的非叶结点个数,那么两者满足关系n0 = n2 + 1。 

    3、特殊的二叉树

    完美二叉树(Perfect Binary Tree) , 也称为满二叉树(Full Binary Tree)

    - 在二叉树中, 除了最下一层的叶结点外, 每层节点都有2个子结点, 就构成了满二叉树.

    完全二叉树(Complete Binary Tree)

    - 除二叉树最后一层外, 其他各层的节点数都达到最大个数.
    - 且最后一层从左向右的叶结点连续存在, 只缺右侧若干节点.
    - 完美二叉树是特殊的完全二叉树.

     

    4、二叉树的存储

    - 二叉树的存储常见的方式是链表.

    - 链表存储:

      - 二叉树最常见的方式还是使用链表存储.
      - 每个结点封装成一个Node, Node中包含存储的数据, 左结点的引用, 右结点的引用.

  • 相关阅读:
    Android+Appium自动化测试环境搭建及实操
    Java时间Api
    Pandas 数据分析系列1--Series&DataFrame数据结构详解
    数据视图展示,一“链”直达_三叠云
    【问题解决】源码安装Nginx提示找不到openssl library
    t-io websocket的聊天功能学习记录(二)
    MySQL Insert 后獲得主鍵
    AndroidStudio集成GitHub操作入门
    GD32F407VET6新建固件库工程并下载运行
    二叉树知识点及各种遍历方式
  • 原文地址:https://blog.csdn.net/qq_52301431/article/details/126509249