当前位置：网站首页>二叉树 | 代码随想录学习笔记

二叉树 | 代码随想录学习笔记

2022-08-10 22:23:00 【Begonia_cat】

文章目录

跟随carl代码随想录刷题
语言：python
本文为笔者学习二叉树的笔记，主要内容来自于代码随想录。

二叉树

二叉树的定义

二叉树的定义与链表差不多，只不过二叉树的节点里多了两个指针：指向左右孩子。

class TreeNode: 
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

二叉树的形式、平衡二叉树、二叉搜索树

  • 二叉树主要有两种形式【不包含数值】：
    • 满二叉树
      • 一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上。
      • 深度为k时，有2^k - 1个节点。
        在这里插入图片描述
    • 完全二叉树
      • 除了最底层节点可能没填满外，其余每层节点数都达到了最大值。并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为n层，则该层包含1~2^(h-1)个节点。
        在这里插入图片描述
      • 堆就是一个完全二叉树
  • 二叉搜索树
    • 二叉搜索树是有序树
    • 如果左子树不为空，则左子树上所有节点的值均小于它的根节点的值。
    • 如果右子树不为空，则右子树上所有节点的值均大于它的根节点的值。
      在这里插入图片描述
  • 平衡二叉树（又称AVL树）
    • 是空树或左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
      在这里插入图片描述
      红黑树是一种平衡二叉树
    • 一定要知道自己所用语言的常用的容器底层是如何实现的

二叉树的存储方式

  • 两种方式：

    • 链式存储

      • 用指针
      • 元素散落在内存中的各个地址
        在这里插入图片描述

    • 顺序存储

      • 用数组
      • 元素在内存中是连续分布的
        在这里插入图片描述

    • 如果父节点的数组下标是i，那么它的左孩子就是i*2+1，右孩子就是i*2+2

    • 链式表示方式便于理解，一般都用链式存储二叉树（所以喔，数组依然可以表示二叉树）。

二叉树的遍历方式

  • 主要有两种遍历方式：
原网站

版权声明
本文为[Begonia_cat]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_44250700/article/details/126254194

边栏推荐

猜你喜欢

随机推荐