【数据结构】二叉树的概念 |
您所在的位置:网站首页 › 数据结构二叉树公式 › 【数据结构】二叉树的概念 |
在上一章中我们正式开启了对数据结构中树的讲解,介绍了树的基础。本章我们将学习二叉树的概念,介绍满二叉树和完全二叉树的定义,并对二叉树的基本性质进行一个简单的介绍。本章附带课后练习。 🔗 链接:【数据结构】树的概念与结构 0x00 概念📚 定义:二叉树既然叫二叉树,顾名思义即度最大为2的树称为二叉树。 它的度可以为 1 也可以为 0,但是度最大为 2 。 📜 一颗二叉树是节点的一个有限集合,该集合: ① 由一个根节点加上两颗被称为左子树和右子树的二叉树组成 ② 或者为空 🔺 观察上图我们可以得出如下结论: ① 二叉树不存在度大于 2 的节点,换言之二叉树最多也只能有两个孩子。 ② 二叉树的子树有左右之分,分别为左孩子和右孩子。次序不可颠倒,因此二叉树是有序树。 📌 注意:对于任意的二叉树都是由以下几种情况复合而成的: 📚 定义:一个二叉树,如果每一层的节点数都达到了最大值(均为2),则这个二叉树就可以被称作为 "满二叉树" 。 📜 换言之,如果一个二叉树的层数为 🔺 计算公式: ① 已知层数求总数: ② 已知总数求层数: ❓ 十亿个节点,满二叉树是多少层? 💡 📚 定义:对于深度为 📜 前 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。所以,满二叉树是一种特殊的完全二叉树(每一层节点均为2)。 📚 常识: ① 完全二叉树中,度为 1 的最多只有 1 个。 ② 高度为 📚 四点规则: ① 若规定根节点的层数为 1 ,则一颗非空二叉树的第 ② 若规定根节点的层数为 1 ,则深度为 ③ 对任何一颗二叉树,如果度为 0 其叶子结点个数为 ④ 若规定根节点的层数为 1 , 具有 📚 对于有
假设 ① 求左孩子: ② 求右孩子: ③ 求父亲(假设不关注是左孩子还是右孩子): ④ 判断是否有左孩子: ⑤ 判断是否由右孩子: 💭 PS:二叉树不一定要标准,比如这个其实也是二叉树: 1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( ) A. 不存在这样的二叉树 B. 200 C. 198 D. 199 2. 在具有 2n 个结点的完全二叉树中,叶子结点个数为( ) A. n B. n+1 C. n-1 D. n/2 3. 一棵完全二叉树的节点数位为531个,那么这棵树的高度为( ) A. 11 B. 10 C. 8 D. 12 5. 一个具有767个节点的完全二叉树,其叶子节点个数为() A. 383 B. 384 C. 385 D. 386 参考资料: Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. . 百度百科[EB/OL]. []. https://baike.baidu.com/. 📌 笔者:王亦优 📃 更新: 2021.11.24 ❌ 勘误: 无 📜 声明: 由于作者水平有限,本文有错误和不准确之处在所难免,本人也很想知道这些错误,恳望读者批评指正! 本篇完。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |