首页 > 其他 > 详细

二叉树

时间:2020-03-28 09:13:40      阅读:46      评论:0      收藏:0      [点我收藏+]

树的定义
  • 专业定义:

    1. 有且只有一个称为根的节点

    2. 有若干个互不相交的子树,这些子树本身也是一颗树

  • 通俗定义:

    1. 树是由节点和边组成

    2. 每个节点只有一个父节点但可以有多个子节点

    3. 但有一个节点例外,该节点没有父节点,此节点称为根节点

  • 专业术语:

    • 节点,父节点,子节点

    • 子孙,堂兄弟

    • 深度:从根节点到最底层节点的层数称之为深度,根节点是第一层

    • 叶子节点:没有子节点的节点

    • 非终端节点:实际就是非叶子节点

    • 度:子节点的个数

树的分类
  • 一般树:任意一个节点的子节点的个数都不受限制

  • 二叉树:任意一个节点的子节点个数最多两个,且子节点的位置不可更改

    • 分类

      • 一般二叉树

      • 满二叉树:在不增加树层数的前提下,无法再多添加一个节点的二叉树就是满二叉树

      • 完全二叉树:如果只是删除了满二叉树最底层最右边的连续若干个节点,这样形成的二叉树就是完全二叉树。(满二叉树是完全二叉树的一个特例)

  • 森林:n个互不相交的树的集合

树的存储
  • 二叉树的存储

    • 连续存储【完全二叉树】

      优点:查找某个节点的父节点和子节点(也包括判断有没有子节点)

      缺点:耗用内存空间过大

    • 链式存储

  • 一般树的存储

    • 双亲表示法:求父节点方便

    • 孩子表示法:求子节点方便

    • 双亲孩子表示法:求父节点和子节点都很方便

    • 二叉树表示法:把一个普通树转化成二叉树来存储

      具体转换方法:

      设法保证任意一个节点的左指针域指向它的第一个孩子,右指针域指向它的兄弟,只要满足此条件,就可以把一个普通树转化为二叉树。

      一个普通树转化成的二叉树一定没有右子树

  • 森林的存储

    先把森林转化为二叉树,再存储二叉树:

    将相邻的父节点依次作为节点的右子树再对各父节点进行转化

二叉树

原文:https://www.cnblogs.com/codeke/p/12585166.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!