【数据结构】什么是树

树是由若干个有限节点组成的一个具有层次关系的集合

树的特点

  • 数学基础是: 图论
  • 一棵树中每两个点之间都有且只有一条路
  • 一颗有N个点的树有N-1条边

结构与名称

树的结构图

像图中的圈我们称之为“节点”, 节点与节点之间的线称之为“边”, 最起始的节点叫“根”

一个节点下面的节点成为该节点的子节点, 该节点是其子节点的父节点

节点的层级用“深”来表示, 并且以0开始计数

当节点不再分叉时, 末尾的节点称为“叶子节点”

一个节点的子节点数量称为“度”, 如果一个节点有3个子节点, 那么它的度为3, 当度为0时就是叶子节点

一个节点到另一个节点之间的连线 称为“路径”

树和非树的典型

空树是指,有了树的结构, 但是还没有填充节点

树和非树

树的遍历

树的遍历分为,两大类, 四小类

按照某种规则, 不重复地访问某种树的所有节点

  • 先序遍历(深度优先)
  • 中序遍历(深度优先)
  • 后续遍历(深度优先)
  • 层序遍历(广度优先)

先、 中、后都是针对的根节点来说的, 并且树是一种自相似的结构, 可以采用递归, 所以比较好记忆

1.先序遍历

左、中、右

优先访问根节点, 然后访问其左子树, 如果左子节点还有其左子节点, 再继续往下访问其左子节点, 直至没有, 然后访问其节点的父节点, 最后访问其父节点的右子节点, 就这样一层一层向上,直至根节点的整个左子树遍历完, 去对右子树做同样的操作

先序遍历

2. 中序遍历

中、左、右

优先访问左子树, 然后访问根节点, 最后访问右节点

中序遍历

3. 后序遍历

左、 右、 中

优先访问左子树、 然后访问右子树, 最后访问根节点

后序遍历

4. 层序遍历

广度优先逐层访问节点, 直至该层没有, 然后再往下扎

层序遍历

树的衍生

无序树: 树中任意节点的子节点之间没有顺序关系, 这种树称为无序树, 也称为自由树

有序树: 树中任意节点的子结点之间有顺序关系

二叉树: 每个节点最多含有两个子树的树称为二叉树

完全二叉树: 除了最后一层, 其他各层节点数都达到最大

满二叉树: 每一层上的节点数都是最大节点数

霍夫曼树: 带权路径最短的二叉树, 也叫最优二叉树

排序算法的复杂度与稳定性

2019-06-09-21-32-43

关于查找算法

2019-06-09-21-36-02

你的支持将鼓励我继续创作