You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 

1.3 KiB

  • 基础

    • 树的定义

      • 树是一种数据结构
      • 树是一种可以递归定义的数据结构
      • 树是由n个结点组成的集合
        • n=0表示空树
        • n>0表示存在一个结点为根,其他结点可以分为m个集合,每个集合本身又是一个树
    • 树的概念

      • 叶子:

      • 树的深度/高度:树存在的层

      • 树的度:结点分叉的度

        ​ 整棵树的度指最大的度

      • 孩子结点/父结点:描述结点关系

      • 子树:树的分支

    • 二叉树

      • 二叉树是指不超过2的树
      • 每一个结点最多右两个孩子结点
      • 两个孩子结点被区分为左孩子结点和右孩子结点
    • 满二叉树

      • 每一层的结点数都达到最大值
    • 完全二叉树

      • 定义:叶子节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
      • 简化1:从根进行编号,中间不间断的二叉树
      • 简化2:由满二叉树从右边拿走部分节点
  • 二叉树的存储方式

    • 链式存储方式
      • 父节点与左孩子节点下标关系: i => 2i + 1
      • 父节点与右孩子节点下标关系: i => 2i + 2
    • 顺序存储方式