树和二叉树

树

树的定义和基本术语

• 节点: 包含一个数据元素和若干指向其子树的分支
• 度： 节点拥有的子树数称为节点的度
• 叶子： 度为0的节点称为叶子或中断节点
• 非终端节点，分支节点：度不为0的节点
  下面几个概念不做解释了： Child, Parent, Sibling, 祖先, 子孙，堂兄弟
• 层次：从根开始，根为第一层，根的孩子是第二层。。。。
• 深度：树中最大的层次称为深度或者高度
• 有序树：从左至右是有顺序的就称为有序树（第一个孩子，最后一个孩子）
• 无序树：否则就是无序树
• 森林：子树的集合称为森林

二叉树

二叉树是一种树形结构，它的特点是每个节点之多只有两棵子树，并且二叉树的子树有左右之分，其次不能任意颠倒。

遍历二叉树

二叉树是由3个基本单元组成：根节点，左子树，右子树。因此如果能遍历这三个部分就遍历了整棵树。

• 先序遍历

1. 访问根节点
2. 先序遍历左子树
3. 先序遍历右子树

• 中序遍历

1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树

• 后序遍历

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根节点

例子：

我画了一个树

先序遍历的结果：
-+ab-cd/ef
中序遍历的结果:
a+bc-d-e/f
后序遍历的结果:
abcd-*+ef/-