二叉树、哈希表_哈希表二叉树链表查元素时间

二叉树

二叉树的遍历：前序遍历、中序遍历、后序遍历

二叉排序树（也叫二叉搜索树、二叉查找树）：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。并且没有键值相等的节点。因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。

平衡二叉树：首先满足时一颗排序二叉树，并且满足条件：任何一个节点的左右子数的深度差不能超过1；

完全二叉树:若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。优点：子节点的标号与父节点的编号存在关系。

满二叉树:除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。满二叉树是完全二叉树的一个特例。

正则二叉树:所有节点的出度为0或者为2

最优二叉树（哈夫曼树）：带权值的结点都是叶子结点。权值越小的结点，其到根结点的路径越长

红黑树（参考：http://www.cnblogs.com/v-July-v/archive/2010/12/29/1983707.html）：一种二叉查找树，同时也是一个平衡二叉树。但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。红黑树的查找、插入、删除的时间复杂度最坏为O(log n)

二叉堆：用在堆排序中，是一种完全二叉树。分为最大堆和最小堆。并且满足下面两个特性：

（1）父节点的键值总是小于等于（或者大于等于）任何一个子节点的键值；

（2）每个节点的左右子树都是二叉堆。

哈希表（参考：http://blog.csdn.net/ljlstart/article/details/51335687）：在内存中的结构就是一个数组。Key通过一 个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标 的数组空间里，而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分 利用到数组的定位性能进行数据定位。

哈希表和红黑树的区别：参考：http://blog.csdn.net/ljlstart/article/details/51335687

Huffman编码