树
树的定义
专业定义：
- 有且只有一个根的节点
- 有若干的互不相交的子树，这些子树本身也是一棵树
通俗的定义：
- 树是由节点和边组成
- 每个节点只有一个父节点，但可以有多个子结点
- 但有一个节点例外，该节点没有父节点，此节点为根节点。
专业术语：
节点 父节点 子节点 子孙 祖先 堂兄弟
深度：从根节点到最底层节点的层数。（根节点是第一层）
叶子节点：没有子节点的节点
非终端节点：实际就是非叶子节点
度:子结点的个数
树的分类
一般树
任意一个节点的子节点的个数都不受限制
二叉树
任意一个节点的子节点的个数最多为两个，且子节点的位置不可变更
分类：
- 一般二叉树
- 满二叉树 在不增加树的层数的前提下，无法再多添加一个节点的二叉树。
- 完全二叉树 如果只是删除了满二叉树最底层最右边的连续若干个节点。
森林
n 个互不相交的树的集合
树的存储
二叉树的存储
连续存储[完全二叉树]
优点： 查找某个节点的父节点和子结点速度(也包括有没有子结点)很快.
缺点： 耗用的内存空间比较大.
链式存储
一般树的存储
双亲表示法
求父节点方便。
孩子表示法
求子节点方便。
双亲孩子表示法
求父节点和子结点都很方便。
二叉树表示法
把一个普通的树转换成二叉树来存储。
具体转换方法:
- 设法保证任意一个节点的左指针指向它的第一个孩子，右指针指向它的堂兄弟。
- 只要能满足此条件，就可以把一个普通的树转换成为二叉树。
- 一个普通树转换成的二叉树一定没有右子树。
森林的存储
先把森林转化成二叉树，再存储二叉树
树的操作
遍历
先序遍历
- 先访问根节点
- 再先序访问左子树
- 再先序访问右子树
先序遍历顺序：ABDCEFG
先序遍历顺序：ABCDEFLQMNS
中序遍历
- 中序遍历左子树
- 再访问根节点
- 再中序遍历右子树
中序遍历顺序：CDFELBAMSNQA
后序遍历
- 中序遍历左子树
- 中序遍历右子树
- 遍历根节点
后序遍顺序：FLEDCBSNMQA
已知两种遍历序列求原始二叉树
通过先序和中序 或者 中序和后序
可以还原出原始的二叉树
但是通过先序和后序是无法还原出原始的二叉树的
换种说法：
只有通过先序和中序，或通过中序与后序
我们才能可以唯一的确定一个二叉树
示例1（已知先序和中序求后序）：
先序：ABCDEFGH 中序：BDCEAFHG 画出图如下：
求后序：DECBHGFA 示例2（已知中序和后序求先序）： 中序：BDCEAFHG 后序：BECBHGFA 画出图如下： 求先序：ABCDEFGH
树的应用
- 树是数据库中数据组织的一种重要形式。
- 操作系统子父进程的关系本身就是一棵树。
- 面向对象中的类的继承关系
- 赫夫曼树