锐客网

  1. 首页 > it技术 > >

5.2_1_二叉树的定义和基本术语

数据结构

二叉树

  1. 根节点
  2. 左右子树
  3. 每个结点都是两颗子树
  4. 二叉树是有序树，不能调换
满二叉树 高度为h，且含有2^h -1棵子树，除了叶子结点，其余的结点都是含有两个子节点
从1开始编号
i左节点为2i,右节点2i+1
求父节点为i/2向下取整
完全二叉树
  1. 在满二叉树去掉后面的编号的结点
  2. 满二叉树是特殊的完全二叉树
  3. 编号和满二叉树一致，所以关于父子结点的计算相同
  4. 叶子结点最多在最后两层
    1. 最多只有一个度为1的结点，而且必定是左孩子，不是右孩子
  5. 【5.2_1_二叉树的定义和基本术语】i <= n/2 为分支结点；i > n/2 为叶子结点
二叉排序树
  1. 左子树所有结点小于根节点
  2. 右子树所有结点大于根节点
平衡二叉树
  1. 任意节点的高度之差不超过1
  2. 让二叉排序树效率高很多
  3. 越胖越好

    推荐阅读


    上一篇：js错误集锦|js错误集锦 函数在一个map循环遍历中进行返回值返回 结果在调用该函数时收不到返回值

    下一篇：北海道之旅，不慌不忙，自由自在