• c语言数据结构 二叉树下

    一.二叉树的性质

    1. 若规定根节点的层数为 1 ，则一棵非空二叉树的 第 i 层上最多有
    个结点 .
    2. 若规定根节点的层数为 1 ，则 深度为 h 的二叉树的最大结点数是
    .
    3. 对任何一棵二叉树 , 如果度为 0 其叶结点个数为 , 度为 2 的分支结点个数为 , 则有
    ＝ ＋ 1
    4. 若规定根节点的层数为 1 ，具有 n 个结点的满二叉树的深度 ， h=
    . (ps ：
    是 log 以 2
    为底， n+1 为对数 )
    5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对
    于序号为 i 的结点有：
    二.有关二叉树的选择题讲解
    1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（
    ）
    A 不存在这样的二叉树
    B 200
    C 198
    D 199
    2. 下列数据结构中，不适合采用顺序存储结构的是（
    ）
    A 非完全二叉树
    B 堆
    C 队列
    D 栈
    3. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（
    ）
    A n
    B n+1
    C n-1
    D n/2
    4. 一棵完全二叉树的节点数位为 531 个，那么这棵树的高度为（
    ）
    A 11
    B 10
    C 8
    D 12
    5. 一个具有 767 个节点的完全二叉树，其叶子节点个数为（）
    A 383
    B 384
    C 385
    D 386
    1.由性质五得度数为0的叶子节点数比度为2的结点数的多一。所以选B。
    当二叉树为满二叉树时，是不存在度为1的结点。
    当二叉树为完全二叉树时，度为1的结点数小于等于1。
    2.选A。
    该题如果为单选就选择最错误的那一个，如果是多选还要选择C。队列是用链表实现比较合适，而链表不是顺序存储结构。
    顺序存储结构有：顺序表、队列（数组实现）、栈
    堆是可以利用数组实现的。
    3.选A。
    由性质五得度数为0的叶子节点数比度为2的结点数的多一。
    当二叉树为满二叉树时，是不存在度为1的结点。
    当二叉树为完全二叉树时，度为1的结点数小于等于1。
    设度为0的结点数为N0，度为1的结点数为N1，度为2的数为N2。
    N0+N1+N2=2n
    N0+N1+N0-1=2n
    2*N0-1+N1=2n
    其中N0、N1、N2是整数，那么这里N1只能为1
    N0=n
    4.选B
    N代表完全二叉树的总结点数
    将选项中的数值代入，看531在哪个范围内
    2^9=512 2^10=1024
    5.选B
    计算过程同3
    三.二叉树的储存方式
    1.顺序存储
    2.链表存储

    a.二叉链表 

     b.三叉链表

    四.二叉树的三种遍历方式及相关讲解

    1. 前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结点的操作发生在遍历其左右子树之前。
    2. 中序遍历 (Inorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之中（间）。
    3. 后序遍历 (Postorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之后。
    以上三种遍历也可称呼为前根遍历、中根遍历、后根遍历。
    例子讲解：

     前根遍历顺序：根、左子树、右子树

    该图前根遍历顺序为：1 2 3 NULL NULL NULL 4  5 NULL NULL 6 NULL NULL 

    中根遍历顺序：左子树、根、右子树

    该图中根遍历顺序为：NULL 3 NULL 2 NUL NULL 5 NULL 1 4 NULL 6 NULL

    后根遍历顺序：左子树、右子树、根

    该图后根遍历顺序为：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4

    五.二叉树三种遍历方式递归代码实现

     

    六.其他有关二叉树功能的实现

    1.遍历计数

     

     //子问题解决问题

    将一棵树不断得划分为根、左子树、右子树。

     2.求二叉树叶子结点的个数

     

    3.计算二叉树的高度

     

     //子问题解决

    4.计算二叉树的第k层的结点个数 

    学习真的是一件好孤独好矛盾的事情。当我躺在宿舍刷着手机，会很焦虑；当我抱着电脑独自在自习室、教室学习，有的时候会感到很享受、有的时候会感到很孤独。当学的东西越来越多，我很疑惑。如果真的再努力些，自己是否有进入这个行业的资格。天地之大，总会有我立身之处。还是在该学习的时候认真学，该玩的时候就认真玩。

  • 相关阅读:
    深度剖析动态规划算法：原理、优势与实战
    【无功优化】“碳中和”目标下电气互联系统有功-无功协同优化模型（Matlab代码实现）
    flink1.18.0 自定义函数 接收row类型的参数
    abc 329 e ( dfs
    Android I/O Prefetch 学习
    8、Mip-NeRF
    Ps：变换
    如何看待Unity新的收费模式？（InsCode AI 创作助手）
    对xgboost进行可视化，解决中文乱码问题
    Java毕业设计之评教评分教务管理系统springboot mybatis
  • 原文地址：https://blog.csdn.net/shizhongruyi0606/article/details/126642294