树和树的表示
树的定义
树（Tree）: 零个或多个结点(即 n（n≥0）)构成的有限集合
当n=0时，称为空树；
对于任一棵非空树（n> 0），它具备以下性质：
树中有一个称为“根（Root）”的特殊结点，用 r 表示；
其余结点可分为m(m>0)个互不相交的有限集T1，T2，… ，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”
什么是树？什么不是树？
从上图可以总结出：
- 子树是不相交的
- 除了根结点外，每个结点有且仅有一个父结点
- 一棵N个结点的树有N-1条边
树的基本术语
- 结点的度（Degree）：结点的子树个数, 通俗来讲是拥有的儿子的数量
- 树的度：树的所有结点中最大的度数
- 路径和路径长度：从结点n1到nk的路径为一个结点序列n1 , n2 ,… , nk 。其中， ni是 ni+1的父结点。 路径所包含边的个数为路径的长度。
- 叶结点（Leaf）：度为0的结点
- 父结点（Parent）：子树的根结点称为它的父结点
- 子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。
- 兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。
- 祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
- 子孙结点(Descendant)：某一结点的子树中的所有结点是这个结点的子孙。
- 结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。
- 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度
树的表示
在每一个节点除了数据域外还要一些指针，使得该结点的每一个儿子都有一个指针指向它
二叉树及存储结构
二叉树定义
二叉树T：一个有穷的结点集合。这个集合可以为空若不为空，则它是由根结
二叉树的常见形态
注意图c和图d。二叉树的子树有左右顺序之分
特殊的二叉树
1.斜二叉树： 斜树一定要是斜的，但是往哪斜还是有讲究。所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树
2.完美二叉树(满二叉树)：在一颗二叉树中，所有分支都存在左子树和右子树，并且最后，所有的叶子都在同一层
3.完全二叉树:没有满二叉树那么完美，最后可能会缺一些子树，但是一定一定要保证子树是按照层序编号，如图中的二叉树是可以一层一层的从左向右编排
下图的最后一层因为没有按照层序编号，所以不是完全二叉树
二叉树的存储结构——顺序存储结构
对于完全二叉树
存储方式：将完全二叉树从上到下，从左到右一个一个存储到数组中
- 对于非根结点的结点而言，它的父结点是自己的序号除以2
- 结点的左孩子是2 * i
- 结点的有孩子是2 * i+1
对于一般二叉树
一般的二叉树需要在形式上补成完全二叉树，在按照顺序存放到数组中，不存在的节点用"空"表示
二叉树的存储结构——链式存储结构
依靠结构体实现，在一个结点中放置数据域、左指针、右指针
