7.24数据结构

笔记

数和图

一.树形结构相关概念

    1>树形结构：表示数据元素之间存在一对多的关系
    2>树：是由一个根节点多个子树构成的树形结构
    3>节点：就是树中的数据元素
    4>父亲节点：当前节点的直接上级节点
    5>孩子节点：当前节点的直接下架节点
    6>祖先节点：当前节点的直接或间接上级节点
    7>子孙节点：当前节点的直接或间接下级节点
    8>兄弟节点：拥有相同父节点的所有节点互称为兄弟节点
    9>堂兄弟节点：其父节点在同一层的所有节点，互为堂兄弟节点
    10>根节点：没有父节点的节点
    11>叶子节点：没有子节点的节点称为叶子节点
    12>分支节点：节点的度不为0的节点叫分支节点
    13>节点的度：就是当前节点的孩子节点个数，就称为节点的度
    14>树的度：就是树中节点的度的最大值
    15>节点的层次：从根节点开始到当前节点所经历的层数称为该节点的层次
    16>树的层次：输出节点的层次的最大值

二.二叉树

2.1二叉树的相关概念

    1>二叉树：由根节点和最多两个子树组成，并且严格区分左右子树的树形结构
    2>左子树：由当前节点的左孩子节点为跟节点构成的二叉树
    3>右子树：由当前节点的右孩子节点为根节点构成的二叉树
    4>满二叉树：二叉树的最后一层全是叶子节点，在没有添加层数的条件下，不能在向该树中增加节点的树
            （除了最后一层为叶子节点外，其余层中的节点的度全为2）
    5>完全二叉树：在一棵满二叉树的基础上，最后一层自右向左逐渐减少节点的二叉树

2.2二叉树的状态

一共有五种：空二叉树、只有根节点和左孩子、只有根节点和右孩子、全都有

2.3二叉树的性质

    1>在二叉树的第i层上最多有2^（i-1）个节点
    2>在二叉树的前n层最多有2^n-1个节点
    3>在二叉树中，叶子节点的个数，总比度为2的节点个数多1
    4>在二叉树上，如果第i个节点存在左孩子，那么其左孩子一定是第2*i个节点，如果存在右孩子，那么一定是第2*i+1个节点

2.4二叉树的存储

    1>顺序存储
            对于普通的二叉树而言，如果使用顺序存储，会浪费大量的存储空间，因为需要给没有节点的位置留出空间，以便于后期的插入
            顺序存储，一般用于存储完全二叉树，不适合存储普通二叉树
    2>链式存储
            结构：
    struct        Node
    {
            datatype        data;
            struct        Node*left_child;
            struct        Node*right_child;
    };