排序算法的图形界面实现

#include "stdafx.h" #define RED 1 #define BLACK 2 CString REDBLACKTREE = "1、每个节点或是红的，或是黑的\r\n\ 2、根节点是黑的\r\n\ 3、每个叶节点（NIL）是黑的\r\n\ 4、如果一个节点是红的，则它的两个儿子都是黑的\r\n\ 5、对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点。"; template <class T> struct _Red_Black_Tree { _Red_Black_Tree *pLeft; _Red_Black_Tree *pRight; _Red_Black_Tree *pParent; int nColor; T value; _Red_Black_Tree() { pLeft = NULL; pRight = NULL; pParent = NULL; nColor = BLACK; value = 0; } }; static _Red_Black_Tree<int> NIL ; //定义一个空结点 _Red_Black_Tree<int> *pGRoot = &NIL; template <class T> _Red_Black_Tree<T>* Left_Rotate(_Red_Black_Tree<T> *r, _Red_Black_Tree<T> *x) { _Red_Black_Tree<T> *pRoot = r; _Red_Black_Tree<T> *y = x->pRight; x->pRight = y->pLeft; y->pLeft->pParent = x; y->pParent = x->pParent; if(x->pParent == &NIL) pRoot = y; else { if( x == x->pParent->pLeft) x->pParent->pLeft = y; else x->pParent->pRight = y; } y->pLeft = x; x->pParent = y; return pRoot; } template <class T> _Red_Black_Tree<T>* Right_Rotate(_Red_Black_Tree<T> *r, _Red_Black_Tree<T> *y) { _Red_Black_Tree<T> *pRoot = r; _Red_Black_Tree<T> *x = y->pLeft; y->pLeft = x->pRight; x->pRight->pParent = y; x->pParent = y->pParent; if(y->pParent == &NIL) pRoot = x; else { if( y == y->pParent->pLeft) y->pParent->pLeft = x; else y->pParent->pRight = y; } x->pRight = y; y->pParent = x; return pRoot; } template <class T> _Red_Black_Tree<T>* RB_Insert(_Red_Black_Tree<T> *r, _Red_Black_Tree<T> *z) { Compare<T> comparefunc; _Red_Black_Tree<T> *pRoot = r; _Red_Black_Tree<T>* y = &NIL; _Red_Black_Tree<T> *x = pRoot; while(x != &NIL) { y = x; if (comparefunc(z->value, x->value) == -1) x = x->pLeft; else x = x->pRight; } z->pParent = y; if (y == &NIL) pRoot = z; else if (comparefunc(z->value, y->value) == -1) y->pLeft = z; else y->pRight = z; z->pLeft = &NIL; z->pRight = &NIL; z->nColor = RED; pRoot = RB_Insert_Fixup(pRoot, z); return pRoot; } template <class T> _Red_Black_Tree<T>* RB_Insert_Fixup(_Red_Black_Tree<T> *r, _Red_Black_Tree<T> *z) { _Red_Black_Tree<T> *pRoot = r; _Red_Black_Tree<T> *y; while (z->pParent->nColor == RED) { if (z->pParent == z->pParent->pParent->pLeft) { y = z->pParent->pParent->pRight; if ( y->nColor == RED) { z->pParent->nColor = BLACK; y->nColor = BLACK; z->pParent->pParent->nColor = RED; z = z->pParent->pParent; } else { if (z == z->pParent->pRight) { z = z->pParent; pRoot = Left_Rotate(pRoot, z); } z->pParent->nColor = BLACK; z->pParent->pParent->nColor = RED; pRoot = Right_Rotate(pRoot, z->pParent->pParent); } } else { y = z->pParent->pParent->pLeft; if (y->nColor == RED) { z->pParent->nColor = BLACK; y->nColor = BLACK; z->pParent->pParent->nColor = RED; z = z->pParent->pParent; } else { if (z == z->pParent->pLeft) { z = z->pParent; pRoot = Right_Rotate(pRoot, z); } z->pParent->nColor = BLACK; z->pParent->pParent->nColor = RED; pRoot = Left_Rotate(pRoot, z->pParent->pParent); } } } z->nColor = BLACK; return pRoot; } template <class T> _Red_Black_Tree<T>* Tree_Minimum(_Red_Black_Tree<T> *x) { while( x->pLeft != &NIL) { x = x->pLeft; } return x; } template <class T> _Red_Black_Tree<T>* Tree_Successor(_Red_Black_Tree<T> *x) { if (x->pRight != &NIL) return Tree_Minimum(x->pRight); _Red_Black_Tree<T> *y = x->pParent; while(y != &NIL && x == y->pRight) { x = y; y = y->pParent; } return y; } template <class T> _Red_Black_Tree<T>* RB_Delete(_Red_Black_Tree<T> *r, _Red_Black_Tree<T> *z) { _Red_Black_Tree<T> *pRoot = r; _Red_Black_Tree<T> *x = NULL; _Red_Black_Tree<T> *y = NULL; if ( z->pLeft == &NIL || z->pRight == &NIL) y = z; else y = Tree_Successor(z); if (y->pLeft != &NIL) x = y->pLeft; else x = y->pRight; x->pParent = y->pParent; if (y->pParent == &NIL) pRoot = x; else { if (y == y->pParent->pLeft) y->pParent->pLeft = x; else y->pParent->pRight = x; } if (y != z) z->value = y->value; if (y->nColor == BLACK) pRoot = RB_Delete_Fixup(pRoot, x); delete y; return pRoot; } template <class T> _Red_Black_Tree<T>* RB_Delete_Fixup(_Red_Black_Tree<T> *r, _Red_Black_Tree<T> *x) { _Red_Black_Tree<T> *pRoot = r; while ( x != pRoot && x->nColor == BLACK) { if(x == x->pParent->pLeft) { _Red_Black_Tree<T> *w = x->pParent->pRight; if (w->nColor == RED) { w->nColor = BLACK; x->pParent->nColor = RED; pRoot = Left_Rotate(pRoot, x->pParent); w = x->pParent->pRight; } if (w->pLeft->nColor == BLACK && w->pRight->nColor == BLACK) { w->nColor = RED; x = x->pParent; } else { if (w->pRight->nColor == BLACK) { w->pLeft->nColor = BLACK; w->nColor = RED; pRoot = Right_Rotate(pRoot, w); w = x->pParent->pRight; } w->nColor = x->pParent->nColor; x->pParent->nColor = BLACK; w->pRight->nColor = BLACK; pRoot = Left_Rotate(pRoot, x->pParent); x = pRoot; } } else { _Red_Black_Tree<T> *w = x->pParent->pLeft; if (w->nColor == RED) { w->nColor = BLACK; x->pParent->nColor = RED; pRoot = Right_Rotate(pRoot, x->pParent); w = x->pParent->pLeft; } if (w->pLeft->nColor == BLACK && w->pRight->nColor == BLACK) { w->nColor = RED; x = x->pParent; } else { if (w->pLeft->nColor == BLACK) { w->pRight->nColor = BLACK; w->nColor = RED; pRoot = Left_Rotate(pRoot, w); w = x->pParent->pLeft; } w->nColor = x->pParent->nColor; x->pParent->nColor = BLACK; w->pLeft->nColor = BLACK; pRoot = Right_Rotate(pRoot, x->pParent); x = pRoot; } } } x->nColor = BLACK; return pRoot; } template <class T> _Red_Black_Tree<T>* rb_search (_Red_Black_Tree<T> *x, T k, T *Arr)//查找一个关键字 { int i = 0; while (x != &NIL && x->value != k) //X结点不为空且X的数据域不为K，则继续循环 { Arr[i] = x->value; i++; if (x->value < k)//若当前结点比关键字小 x = x->pRight; //转向右孩子 else x = x->pLeft;//否则转向左孩子 } return x; } int nNum = 0; int gArr[4096] = {0}; template <class T> void rb_mid_visit_tree(_Red_Black_Tree<T> *root)//中序遍历 { if (root != &NIL) { rb_mid_visit_tree (root->pLeft); gArr[nNum] = root->value; nNum++; // rb_print_node (root); rb_mid_visit_tree (root->pRight); } }