1、二叉树广度遍历(非递归)
广度遍历非递归实现需要依靠一个队列。
2、二叉树深度遍历(递归与非递归,前序,中序和后序)
递归前序(根左右):
前序非递归:
递归中序(左根右):
中序非递归:
递归后序(左右根):
非递归后序:二叉树的后序遍历--非递归实现 - 小雨淅淅 - 博客园
3、查找算法
顺序查找(一个个的挨着找)
二分查找(前提,数列有序,假设递增)
插值查找
对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。
斐波那契查找
二分查找、插值查找和斐波那契查找都只适用于数列有序,本质上是类似的,只是分割点选择不同。他们的时间复杂度是一样的,只是适用场景不同,在特定的场景下某种算法更优。
线性索引查找,分为稠密索引、分块索引和倒排索引。稠密索引是指对每个记录都建立一个数据项,空间消耗比较大。分块索引,块间有序,块内无序。
哈希查找:通过哈希函数建立哈希表。哈希表就是一种以键-值存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。
树表查找,分为二叉查找树,
二叉查找树,也叫二叉排序树,要求左子树的值小于根节点,右子树的值大于根节点,同时左右子树也都是二叉查找树。它和二分查找一样,插入和查找的时间复杂度均为O(logn),但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候,树没有保持平衡。可以递归非递归两种方式实现。二叉查找树的中序遍历结果就是一个递增数列,最小值是二叉树最左边的值,最大值是二叉树最右边的值。
2-3查找树
2-3树的查找效率与树的高度是息息相关的。在最坏的情况下,也就是所有的节点都是2-node节点,查找效率为lgN;在最好的情况下,所有的节点都是3-node节点,查找效率为log3N约等于0.631lgN
红黑树由2-3树演变而来,红黑树是一种具有红色和黑色链接的平衡查找树,同时满足:
红色节点向左倾斜
一个节点不可能有两个红色链接
整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同。
4、排序算法
直接插入排序(将无序数列第一个插入到有序数列中)
希尔排序是直接插入排序的一种改进
冒泡排序:
快速排序
直接选择排序
堆排序
【c++】STL里的priority_queue用法总结 - CSDN博客
归并排序
5、贪心算法、回溯法、动态规划
网友评论