树、二叉树

－树

树的引入：

（分层次组织在管理上具有更高的效率）
首先分析对存储数据的查找，有两种类型：
静态查找：集合中记录是固定的，没有插入和删除操作，只有查找；
动态查找：集合中记录是动态变化的，除查找外还有插入和删除。

我们暂时先考虑较简单的静态查找，静态查找的方法有：
方法1-顺序查找：
利用数组循环查找（数组下标为0时是哨兵，哨兵就是我们想要查找的值）
for（ int i = array.length-1; array[ i ] != K; i-- ）;
array[ 0 ] = K;
K为需要查找的数
方法2-二分查找：
前提：假设放置是顺序从小到大，且是在数组中查找，不能是链表
二分查找：判定树，判定树上每个结点需要的查找次数刚好为该结点所在的层数，查找成功时查找次数不会超过判定树的深度 n个结点的判定树的深度为（log2n）＋1；
把数据按树的形式存储数据而不是数组的形式。
由此引入树的概念

什么是树？

树：由n个结点构成的有限集合；n＝0时为空树。
树中有一个称为“根”的特殊结点用r表示；其余结点可分为m个互不相交的有限集 其中每个集合本身又是一棵树，称为原来树的子树。
子树不相交，除了根结点外，每个结点有且仅有一个父结点，一棵N个结点的树有N－1条边。
树的一些基本术语：1.结点的度：结点的子树个数 2.树的度：树的所有结点中最大的度数 3.叶结点：度为0的结点 4.父结点：有子树的结点是其子树的根结点的父结点，对应子结点 5.兄弟结点：具有同一父结点的各结点彼此是兄弟结点 6.路径和路径长度：从结点n1到结点nk的路径为一个结点序列 ni是ni+1的父结点 路径所包含边的个数为路径的长度 结点的层次：根结点在1层 其他结点的层数是其父结点的层数加1 树的深度：树中所有结点中的最大层次是这棵树的深度
数组及普通链表均难以实现树
儿子－兄弟表示法 两个指针：第一个指针指向其第一个子结点 第二个指针指向其下一个兄弟指针 最后一个兄弟指针指向空
这样的树称为二叉树，每一个结点上是两个指针

－二叉树：

一个有穷的结点集合，这个集合可以为空；若不为空，则它是由根结点和称为其左子树和右子树的两个不相交的二叉树组成，二叉树子树有左右之分。
五种基本形态：空、只有一个结点、只有左结点、只有右结点、有左右两个结点

特殊的二叉树：

斜二叉树、完美二叉树（满二叉树）、完全二叉树
关于完全二叉树：有n个结点的二叉树，对树中结点按从上至下从左至右顺序进行编号 编号为X的结点与满二叉树结点中编号为X的结点在二叉树中的位置相同

一个二叉树第n层的最大结点数为：2的n-1次方，
深度为k的二叉树有最大结点总数为：2的k次方减1，
对任何非空二叉树，若n0表示叶结点个数 n2是度为2的非叶结点个数，那么两者满足关系 n0 ＝ n2＋1
证明：从边的数量看，从上往下与从下往上看 n0＋n1＋n2－1＝n1＋2*n2；所以 n0＝n2＋1
操作集：判断二叉树是否为空；遍历：按顺序访问每个结点。
三种遍历：先序：根－左子树－右子树；中序：左子树－根－右子树；后序：左子树－右子树－根；层次遍历：从上到下、从左到右。

二叉树的存储结构

1.顺序存储结构

完全二叉树：按从上到下从左到右顺序存储n个结点（序号从1开始）的完全二叉树的结点父子关系存入数组中 。
－非根结点（序号i>1）的父结点的序号是［i/2］
－结点（序号为i）的左孩子结点的序号2i
－结点（序号为i）的有孩子结点的序号为2i＋1
一般二叉树也可采用上述结构 只需用空结点将其补齐为对应的完全二叉树，不过这样会造成空间浪费

2.链表存储 Left－Data－Right

结构体为包含两个指针的结构