二叉树(待完善)

作者: 愿你我皆是黑马 | 来源:发表于2021-07-18 23:52 被阅读0次

什么是二叉树

每个节点最多只有两个分支(即分支度不大于2)的树结构


常见特殊二叉树

  • 空二叉树:节点个数为0的树,也叫空树

  • 斜树:相当于链表的特殊结构,所有节点都只有左节点 或 都只有右节点
    左斜树:
    右斜树:

  • 满二叉树除了底层叶子节点,所以其他节点都存在左右子节点

    1. 叶子节点只能出现在最下一层
    2. 非叶子节点的度一定是2
    3. 同样深度的树,满二叉树节点个数最多,叶子数最多
  • 完全二叉树满二叉树最后开始按顺序去掉n(>=0)个节点的树

    1. 叶子节点只会出现在最下两层
    2. 最下层的叶子节点都往左连续
    3. 倒数第二层,叶子节点都往右连续
    4. 同样节点数的二叉树,完全二叉树的深度最小
    5. 具有n个节点的完全二叉树的深度为\lfloor \log_2{n} \rfloor +1
    6. 具有n个节点的完全二叉树,按层编号,
      i=1 :无双亲,属于该完全二叉树的根
      i>1 : 双亲节点是\lfloor i/2 \rfloor
      2i>n : 则节点i无左孩子,否则左孩子为2i
      2i+1>n : 则节点i无右孩子,否则右孩子为2i+1
  • 二叉搜索树

  • 平衡二叉搜索树

  • 线索二叉树

  • 红黑树

  • AVL树

  • 赫弗曼树


二叉树的一般性质

  • 在二叉树的第i层,最多有2^{i-1}个节点。(i>=1,即下标不是从0开始是从1开始)
  • 深度为k的二叉树最多有2^k-1个节点
  • 如果叶子节点数为n_0,度为2的节点数为n_2,则n_0=n_2+1

二叉树的存储方式

  • 链式存储
    以节点类为单位,每个节点有(左)节点和(右)节点的引用。
  • 顺序储存
    按层遍历:从上到下,每层从左到右遍历。将节点按顺序放到数组中
    • 对于完全二叉树来说:i的左节点为 2 * i,i的右节点为2 * i + 1
    • 若不是完全二叉树要使用上述性质,则空余节点使用null代替后。按序放到数组中

二叉树的建立



二叉树的遍历

  • 深度优先遍历:一条路走到底的遍历方式

    1. 前序遍历:左右的前面插入中,即:中左右
    2. 中序遍历:左右的中间插入中,即:左中右
    3. 后序遍历:左右的后面插入中,即:左右中
  • 广度优先遍历:按一层或一圈的遍历方式
    从上到下,一层一层的从左到右遍历


递归实现二叉树的遍历

  • 前序

    def 二叉树前序遍历(当前遍历到的节点):
      if 当前遍历到的节点==None:
          return
      print(当前遍历到的节点.value)
      二叉树前序遍历(当前遍历到的节点.左节点)
      二叉树前序遍历(当前遍历到的节点.右节点)
    
  • 中序

    def 二叉树前序遍历(当前遍历到的节点):
      if 当前遍历到的节点==None:
          return
      二叉树前序遍历(当前遍历到的节点.左节点)
      print(当前遍历到的节点.value)
      二叉树前序遍历(当前遍历到的节点.右节点)
    
  • 后序

    def 二叉树前序遍历(当前遍历到的节点):
      if 当前遍历到的节点==None:
          return
      二叉树前序遍历(当前遍历到的节点.左节点)
      二叉树前序遍历(当前遍历到的节点.右节点)
      print(当前遍历到的节点.value)
    

栈实现二叉树的遍历

  • 前序

  • 中序

  • 后序

    
    

树、森林、与二叉树的转换

  • 树转二叉树
    一般步骤:
    1. 连线
  • 森林

相关文章

  • 二叉树(待完善)

    什么是二叉树 每个节点最多只有两个分支(即分支度不大于2)的树结构 常见特殊二叉树 空二叉树:节点个数为0的树,也...

  • 待完善

    有一直老母鸡,当她还是小鸡的时候,无忧无虑的,然后她长大了,发现小时候一起玩儿的禽类有的上了天,有的下了水,有的长...

  • 待完善

    两个人最好的状态,好像就是我在闹他在笑。以前特别不理解,随着我们两个的相处,我越发的感觉这样的状态,特别的舒服,我...

  • 数据结构-系列文章

    线性表 单链表 单链表-OC实现 双链表 循环链表 栈 栈 队列 待完善 数组 待完善 树 待完善 图 待完善 哈...

  • 牧牛,与马斯洛需求层次理论

    一、马斯洛五需求层次理论 第一层:待完善 第二层:待完善 第三层:待完善 第四层:待完善 第五层:待完善 二、牧牛...

  • 普通二叉树的Java实现

    二叉树的性质每个节点至多有两个分支(子节点),分支具有左右次序,不能颠倒。 主要是遍历的代码,其他待完善。

  • 目录(待完善)

    饮食: 1.三大能量元素 2.热量计算 健身: 1.有氧运动 2.无氧运动 3.自重训练 4.减肥方法

  • leetcode 待完善

    一、树 1.判断是否是对称二叉树 2.序列化与反序列化二叉树 3.广度优先遍历二叉树(递归版) 4.入一颗二叉树和...

  • SimpleRPC待完善

    common: provider: server: client:

  • 二叉树按层打印(待完善)

    代码如下: 解法二: 方法三: 引自《编程之美》

网友评论

    本文标题:二叉树(待完善)

    本文链接:https://www.haomeiwen.com/subject/awetmltx.html