Debug客栈
做一个爱分享的程序猿
Debug客栈
数据结构 非线性结构

友情提示:此篇文章大约需要阅读 3分钟8秒,不足之处请多指教,感谢你的阅读。订阅本站

数的定义

专业定义:

  1. 有且只有一个根的节点
  2. 有若干的互不相交的子树,这些子树本身也是一棵树

通俗的定义:

  1. 树是由节点和边组成
  2. 每个节点只有一个父节点,但可以有多个子结点
  3. 但有一个节点例外,该节点没有父节点,此节点为根节点。

专业术语:

节点
父节点
子节点
子孙
祖先
堂兄弟
深度:从根节点到最底层节点的层数。(根节点是第一层)
叶子节点:没有子节点的节点
非终端节点:实际就是非叶子节点
度:子结点的个数

树的分类

一般树

任意一个节点的子节点的个数都不受限制

二叉树

任意一个节点的子节点的个数最多为两个,且子节点的位置不可变更

分类:

  1. 一般二叉树
  2. 满二叉树 在不增加树的层数的前提下,无法再多添加一个节点的二叉树。
  3. 完全二叉树 如果只是删除了满二叉树最底层最右边的连续若干个节点。

森林

n 个互不相交的树的集合

树的存储

二叉树的存储

连续存储[完全二叉树]

优点:
查找某个节点的父节点和子结点速度(也包括有没有子结点)很快.

缺点:
耗用的内存空间比较大.

链式存储

一般树的存储

双亲表示法

求父节点方便。

孩子表示法

求子节点方便。

双亲孩子表示法

求父节点和子结点都很方便。

二叉树表示法

把一个普通的树转换成二叉树来存储。

具体转换方法:

  1. 设法保证任意一个节点的左指针指向它的第一个孩子,右指针指向它的堂兄弟。
  2. 只要能满足此条件,就可以把一个普通的树转换成为二叉树。
  3. 一个普通树转换成的二叉树一定没有右子树。

森林的存储

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

树的操作

遍历

先序遍历

先访问根节点
再先序访问左子树
再先序访问右子树

先序遍历顺序:ABDCEFG

先序遍历顺序:ABCDEFLQMNS

中序遍历

中序遍历左子树
再访问根节点
再中序遍历右子树

中序遍历顺序:CDFELBAMSNQA

后序遍历

中序遍历左子树
中序遍历右子树
遍历根节点

后序遍顺序:FLEDCBSNMQA

已知两种遍历序列求原始二叉树

通过先序和中序 或者 中序和后序
可以还原出原始的二叉树
但是通过先序和后序是无法还原出原始的二叉树的

换种说法:
只有通过先序和中序,或通过中序与后序
我们才能可以唯一的确定一个二叉树

示例1(已知先序和中序求后序):

先序:ABCDEFGH
中序:BDCEAFHG
画出图如下:

求后序:DECBHGFA
示例2(已知中序和后序求先序):
中序:BDCEAFHG
后序:BECBHGFA
画出图如下:
求先序:ABCDEFGH

树的应用

  1. 树是数据库中数据组织的一种重要形式。
  2. 操作系统子父进程的关系本身就是一棵树。
  3. 面向对象中的类的继承关系
  4. 赫夫曼树
赞赏
本文链接:https://www.debuginn.cn/226.html
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可,转载请保留此文章链接
相关链接: 首页  |  引导页  |  赞助本站  |  @QQ  |  @微博  |  @Bilibili  |  @推特  |  @Github  |  阿里云活动
社会主义核心价值观: 富强、民主、文明、和谐、自由、平等、公正、法治、爱国、敬业、诚信、友善

发表评论

textsms
account_circle
email

Debug客栈

数据结构 非线性结构
树 数的定义 专业定义: 有且只有一个根的节点有若干的互不相交的子树,这些子树本身也是一棵树 通俗的定义: 树是由节点和边组成每个节点只有一个父节点,但可以有多个子…
扫描二维码继续阅读
2017-12-01