二叉树知识

提示：文章

前言

前期疑问：
本文目标：

一、背景

最近K3二叉树知识点

二、

二叉树

K3题目看到一个题目

33、关于二叉树，以下说法正确的是（AC）

A 二叉树的特点是每个节点最多只有2棵子树

B 二叉树的子树无左右区分

C 树的每个节点包含0~2个指向子树的分支

D 一个高度为K（树的高度和深度的起始值为1）的二叉树总共最多有2K+1个节点

关于D答案

一个高度为K的二叉树总共最多有2的k次方减1，也即对应满二叉树。

三、最小生成树

参考文档：最小生成树超详细介绍z

四、B+树

B+树和B树的区别

B树和B+树在节点存储方式、查找过程、空间利用率、结构稳定性以及适用场景等方面存在显著区别。‌

1. ‌节点存储方式：
   • B树：叶子节点和非叶子节点都会存储数据和指针，数据和指针保存在同一节点中。‌1
   • B+树：所有数据都存储在叶子节点，非叶子节点只存储索引信息，不存储数据。
2. ‌查找过程：
   • B树：查找数据需要在各个节点上进行，查找效率不稳定。
   • B+树：查找数据从根节点开始，在非叶子节点上进行索引定位，最终在叶子节点上完成查找，查找效率较高。
3. ‌空间利用率：
   • B树：每个节点都存储数据，空间利用率相对较低。
   • B+树：只有叶子节点存储数据，非叶子节点只存储索引信息，空间利用率更高。
4. ‌结构稳定性‌：
   • B树：插入和删除数据时需要频繁变更树的结构，结构稳定性较差。
   • B+树：插入和删除操作主要在叶子节点进行，维护了树结构的稳定性。
5. ‌适用场景：
   • B树：更适合于数据库的索引结构，适用于大量点查询。
   • B+树：更适合文件系统等场景，适用于大量范围查询和排序操作

题目1

以下关于B树和B+树的对比描述不正确的是

A、B树和B+树都可用于文件的索引结构

B、B树能有效支持顺序检索

C、B+树能有效支持随机检索和顺序检索

D、B树和B+树都是平衡的多叉树

正确答案B

五、平衡二叉树

5.1概念：

平衡二叉树也叫AVL树，它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和左子树的高度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

参考文档：数据结构之——平衡二叉树（内容详解）

5.2 题目1

关于平衡二叉树（AVL树），以下说法正确的有（ABCDE）

A.若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值。

B.左子树和右子树的高度之差的绝对值不超过1

C.是一种二叉排序树

D.右子树高度可以大于左子树高度

E.可以是一棵空树

题目2

关于AVL树描述正确的是

A、AVL右子树上的所有节点的值均小于根节点的值

B、AVL树删除操作后会有一个平衡操作

C、AVL左子树上节点的值可以允许大于根节点的值

D、AVL树的插入操作之后不需要平衡操作

正确答案B

三、

3.1

总结

未完待续