树
树的定义和基本术语
- 节点: 包含一个数据元素和若干指向其子树的分支
- 度： 节点拥有的子树数称为节点的度
- 叶子： 度为0的节点称为叶子或中断节点
- 非终端节点，分支节点：度不为0的节点
下面几个概念不做解释了：Child,Parent,Sibling,祖先,子孙，堂兄弟 - 层次：从根开始，根为第一层，根的孩子是第二层。。。。
- 深度：树中最大的层次称为深度或者高度
- 有序树：从左至右是有顺序的就称为有序树（第一个孩子，最后一个孩子）
- 无序树：否则就是无序树
- 森林：子树的集合称为森林
二叉树
二叉树是一种树形结构，它的特点是每个节点之多只有两棵子树，并且二叉树的子树有左右之分，其次不能任意颠倒。
遍历二叉树
二叉树是由3个基本单元组成：根节点，左子树，右子树。因此如果能遍历这三个部分就遍历了整棵树。
- 先序遍历
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树
- 中序遍历
- 中序遍历左子树
- 访问根节点
- 中序遍历右子树
- 后序遍历
- 后序遍历左子树
- 后序遍历右子树
- 访问根节点
例子：
我画了一个树
先序遍历的结果：
-+ab-cd/ef
中序遍历的结果:
a+bc-d-e/f
后序遍历的结果:
abcd-*+ef/-
网友评论