【数据结构】带迭代器的红黑树

在上一篇博客中，我们简单的介绍了红黑树及其插入操作，下面我们将给红黑树封装一个迭代器。为方便操作，我们需要添加一个头结点，并设置其颜色为红色，以便于根结点区分开；这个根结点的左指向最小的结点，右指向树中值最大的结点，其双亲结点指向根结点，根结点的双亲域也指向头，如下图所示：测试结果如下：

【数据结构】红黑树

一.红黑树的概念红黑树是一颗二叉搜索树，它的每个结点增加一个存储单位来表示结点的颜色，这个颜色是red或者black，通过对任何一条从根结点到叶子结点上的颜色来约束，红黑树保证最长路径不超过最短路径的两倍，因而近似平衡。二.红黑树的性质1.每个结点不是黑色就是红色；2.根结点的颜色是黑色；3.没有两个连续的红色结点；4.每条路径上黑色结点的数量是相等的。

【数据结构】AVL树及平衡化旋转

二叉搜索树可以缩短查找的效率，但是如果数据有序或接近有序时二叉搜索树将退化为单支树，查找效率将会下降。一.AVL树概念：一颗AVL树是一颗空树或者具有如下性质的二叉搜索树:1.它的左右子树都是AVL树；2.左子树和右子树高度之差的绝对值不超过1；如果一颗二叉搜索树是高度平衡的，它就是AVL树。二.平衡化旋转在AVL树中最重要的是平衡化旋转，使树达到平衡状态。

【数据结构】二叉搜索树——转换成有序双向链表

在上一篇博客中，我们对二叉搜索树已经有了简单的认识。下面我们看看怎样将二叉搜索树转换成有序的双向链表在二叉搜索树中，左子树结点的值小于双亲结点的值，右子树结点的值大于双亲结点的值。因此我们可以通过改变指针指向将二叉搜索树转换成双向链表。具体实现代码如下：测试结果：

【数据结构】二叉搜索树

二叉搜索树主要包括了结点的递归插入和非递归插入，递归删除和非递归删除，查找以及中序遍历这四个函数。其中插入和删除的主体部分是查找，查找效率代表了二叉搜索树中各个操作的性能。对有N个结点的二叉排序树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

【数据结构】栈Stack

栈的顺序存储结构结构1、用数组下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小。因此空栈的判定条件定为top等于-1。pop方法实现元素出栈，top值减1，指向当前栈顶元素下标位置，删除该元素作为出栈操作。测试代码栈的链式存储结构结构1、由于单链表有头指针，所以最好的办法就是把栈顶放在单链表的头部。

【数据结构】二叉树

树是数据结构中非常重要的一部分内容，尤其是二叉树。二叉树则是每个结点最多有两个子树的树，二叉树的度最多为2,。下面我们还要计算二叉树的结点的个数，叶子结点的个数，第K层结点的个数，树的高度，查找值为data的结点，查找双亲结点，查找孩子节点，求一个二叉树的镜像以及判断一个树是不是完全二叉树。

【数据结构】：图

到达V10，则称(V1,V2,V5,…连通图：在无向图中V1到V2有路径，则称V1和V2是连通的，如图中任意两个顶点都是连通的，则称此图是连通图。生成树：一个无向连通图的生成树是它的极小连通子图，若图中有N个节点，则其生成树有N-1条边构成。