二叉树、霍夫曼编码和红黑树的C++实现
程序员文章站
2022-05-19 19:53:47
...
主要参考：《数据结构与算法/leetcode/lintcode题解》、《算法导论》
<数据结构与算法>学习笔记（一）基础知识-基本数据结构
4. 二叉树
参考：《算法导论》
二叉树每个节点有最多两个子树，子树有左右之分，可以实现二叉查找树和二叉堆。二叉树有个规律，如果一颗二叉树的终端节点数为，度为2的节点数为，则有。
二叉树的遍历通常有三个步骤：对当前节点进行操作、遍历左边子节点、遍历右边子节点。访问节点的不同顺序形成了不同的遍历方式。树的遍历通常是用递归的思想来理解和实现的。
遍历方式有以下几种：
- 深度优先：先访问子节点再访问父节点，最后访问第二子节点。根据根节点相对于左右子节点的访问顺序可细分为三种方式：1）前序：先根后左后右；2）中序：先左后根后右；3）后序：先左后右再根。这种方式使用递归，即栈的思想对二叉树进行遍历。
- 广度优先：先访问根节点，沿着树的宽度遍历子节点，直到所有节点被访问。这种方式使用队列的思想。
二叉搜索树（二叉查找树）
二叉搜索树：对任意节点x，左子树的关键字不超过x.key，右子树的关键字不低于x.key。大多数搜素树操作的最坏运行时间与树的高度成正比。
它的一个重要特征是用中序遍历可以得到有序数组。
二叉搜索树的常用操作主要有：遍历（可以和其它数据结构如链表结合，二者之间相互转换）、查找、插入、删除。
难点是删除操作，需要考虑三种情况，分别处理三种不同的情况。好在书上给出了详细的算法实现过程，用C++写的时候基本上按照伪代码中的流程，基本上没有什么问题。这个过程充分感受到了逻辑思维起到的重要作用，本身这些过程都是比较抽象的，可能实现任何一个操作，如果让一个初学者凭想象来设计解决方案可能都要费些功夫的，然而书上给出的所有的算法流程都是简化到极致的。很难想到整个思路可以这样简洁。
下面是具体的C++代码:
TreeNode.h(树的节点)
#pragma once
//二叉树节点定义
class TreeNode
{
public:
int val;
TreeNode* left, *right, *p;//左孩子、右孩子、父节点。仅当p=nullptr时该节点是根节点root。
TreeNode(int x);
};
TreeNode.cpp
#include "TreeNode.h"
TreeNode::TreeNode(int x) :val(x), left(nullptr), right(nullptr),p(nullptr){}
binarySearchTree.h（二叉搜素树）
#pragma once
//二叉搜索树，实现
#include"TreeNode.h"
#include<iostream>
#include<queue>
class binarySearchTree
{
private:
TreeNode* root;//根节点，root->p=nullptr;
public:
TreeNode* getroot();
binarySearchTree(); //构造函数
~binarySearchTree(); //析构函数
void preTreeWalk(TreeNode* x ); //前序遍历
void inoTreeWalk(TreeNode* x); //中序遍历
void postTreeWalk(TreeNode* x); //后序遍历
void levelOrder(); //广度优先
TreeNode* search(int k); //查询一个数值，返回某个节点
TreeNode* Maximum(TreeNode* x); //最大值
TreeNode* Minimum(TreeNode* x); //最小值
TreeNode* Success(TreeNode* x); //返回节点x的后继节点，大于x->val的最小关键字的节点，
//如果x->val是最大值则返回nullptr
void insert(TreeNode* x); //插入一个节点或者数值
void insert(int x);
void Transplant(TreeNode* u, TreeNode* v); //用节点v来代替节点u，这个函数是方便我门的删除操作的
void Delete(TreeNode* z); //删除某个节点
};
binarySearchTree.cpp
#include "binarySearchTree.h"
TreeNode* binarySearchTree::getroot()
{
return root;
}
binarySearchTree::binarySearchTree():root(nullptr){}//初始时搜索树为空
binarySearchTree::~binarySearchTree()
{
delete root;
}
void binarySearchTree::preTreeWalk(TreeNode* x)//p,left,right
{
if (x != nullptr) {
std::cout << " " << x->val ;
preTreeWalk(x->left);
preTreeWalk(x->right);
}
}
void binarySearchTree::inoTreeWalk(TreeNode* x)
{
if (x != nullptr) {
preTreeWalk(x->left);
std::cout << " " << x->val ;
preTreeWalk(x->right);
}
}
void binarySearchTree::postTreeWalk(TreeNode* x)
{
if (x != nullptr) {
preTreeWalk(x->left);
preTreeWalk(x->right);
std::cout << " " << x->val ;
}
}
void binarySearchTree::levelOrder()
{
std::queue<TreeNode*> allNode; //队列，先进先出，用在这里再合适不过了
allNode.push(root);
int t = 0,l;
while (allNode.size()!=0) {
l = allNode.size();
std::cout << "\n第" << t++ << "层的所有元素, " <<l<< std::endl;
for(int i=0;i<l;++i) {
TreeNode* x = allNode.front();
allNode.pop(); //注意，队列queue没有直接弹出一个元素的操作，显示第一个元素后要删除这个元素才能达到我们的目的
std::cout << x->val << " ";
if (x->left != nullptr)
allNode.push(x->left);
if (x->right != nullptr)
allNode.push(x->right);
}
}
}
TreeNode* binarySearchTree::search(int k)
{
TreeNode* x = root;
if (x != nullptr && x->val != k)
if (x->val < k)
x = x->left;
else
x = x->right;
return x;
}
TreeNode* binarySearchTree::Maximum(TreeNode* x)
{
while (x->right) {
x=x->right;
}
return x;
}
TreeNode* binarySearchTree::Minimum(TreeNode* x)
{
while (x->left)
x=x->left;
return x;
}
TreeNode* binarySearchTree::Success(TreeNode* x)
{
if (x->right)
return Minimum(x->right); //如果该节点有右子树，则x的后继是右子树中的最左节点
TreeNode* y = x->p;
while (y && x == y->right) { //如果该节点右子树为空，就必须必须寻找它的父节点了，
x = y; //此时如果该节点是最大值就返回空指针，否则，一直向左找父节点直到父节点在右边
y = y->p;
}
return y;
}
void binarySearchTree::insert(TreeNode* x)
{
TreeNode* t = root,*y=nullptr;
while (t != nullptr) { //通过比较来得出数值应该出入到树的那个位置上去，
y = t;
if (x->val < t->val)
t = t->left;
else
t = t->right;
}
x->p = y;
if (y == nullptr)
root = x;
else if (x->val < y->val)
y->left = x;
else
y->right = x;
}
void binarySearchTree::insert(int x)
{
TreeNode* z=new TreeNode(x);
insert(z);
}
void binarySearchTree::Transplant(TreeNode* u, TreeNode* v)
{
if (u->p == nullptr)
root = v;
else if (u == u->p->left)
u->p->left = v;
else
u->p->right = v;
if (v)
v->p = u->p;
}
void binarySearchTree::Delete(TreeNode* z)
{
if (z->left == nullptr)
Transplant(z, z->right); //如果没有左孩子则用右孩子来替换z
else if (z->right == nullptr) //如果没有右孩子则用左孩子来替换
Transplant(z, z->left);
else {
TreeNode* y = Minimum(z->right); // 如果既有左孩子又有右孩子，这时候就比较的复杂了
if (y->p != z) { //
Transplant(y, y->right); //
y->right = z->right;
y->right->p = y;
}
Transplant(z, y);
y->left = z->left;
y->left->p = y;
}
}
main.cpp
#include"binarySearchTree.h"
#include<math.h>
#include<ctime>
int main() {
srand(clock());
binarySearchTree bst;
bst.insert(10);
for (int i = 0; i < 20; i++) {
bst.insert(int(((double)rand() / (RAND_MAX + 1)) * 20));//利用随机数构建一个随机的二叉搜素树，
}
std::cout << "前序：" << std::endl;
bst.preTreeWalk(bst.getroot());
std::cout << "\n中序：" << std::endl;
bst.inoTreeWalk(bst.getroot());
std::cout << "\n后序：" << std::endl;
bst.postTreeWalk(bst.getroot());
std::cout << "\n广度：" << std::endl;
std::queue<int>test;
bst.levelOrder();
std::cout << "\n最大值：" << bst.Maximum(bst.getroot())->val << "，最小值：" << bst.Minimum(bst.getroot())->val << std::endl;
bst.Delete(bst.Maximum(bst.getroot()));
bst.inoTreeWalk(bst.getroot());
bst.Delete(bst.getroot());
std::cout << std::endl;
bst.inoTreeWalk(bst.getroot());
return 0;
}
输出：
前序：
10 0 4 1 0 0 3 1 5 7 5 6 5 9 8 12 19 18 17 12 16
中序：
0 4 1 0 0 3 1 5 7 5 6 5 9 8 10 12 19 18 17 12 16
后序：
0 4 1 0 0 3 1 5 7 5 6 5 9 8 12 19 18 17 12 16 10
广度：
第0层的所有元素, 1
10
第1层的所有元素, 2
0 12
第2层的所有元素, 2
4 19
第3层的所有元素, 3
1 5 18
第4层的所有元素, 4
0 3 7 17
第5层的所有元素, 5
0 1 5 9 12
第6层的所有元素, 3
6 8 16
第7层的所有元素, 1
5
最大值：19，最小值：0
0 4 1 0 0 3 1 5 7 5 6 5 9 8 10 12 18 17 12 16
0 4 1 0 0 3 1 5 7 5 6 5 9 8 12 18 17 12 16
C:\Users\xhh\Source\Repos\algo_binaryTree\Debug\algo_binaryTree.exe (进程 53508)已退出，代码为 0。
按任意键关闭此窗口. . .
5. 霍夫曼编码
这种编码是用贪心算法来构造最优前缀码，它是用较小的比特表示出现频率最高的字符，用较多的比特表示出现频率低的字符。这种编码需要用到二叉树。数据结构与算法/leetcode/lintcode题解中用python实现了霍夫曼编码，看起来不难，但我自己实际用C++实现的时候还是废了很大的功夫的。下面是代码
先是简单编码：
simpleCompression.h
#pragma once
//简单编码
#include<string>
#include<set>
#include<map>
//为了简便，还是要用到set和map这两个无序容器，虽然用数组也不是不可以，
//但C++特意提供了这些容器总要发挥它该有的作用不是~。
//
class simpleCompression
{
private:
std::string str; //输入的字符串。
int bitLen; //编码字符的二进制码的位数
std::map<char, std::string> stringToBit;//映射关系
public:
simpleCompression(std::string s);//构造函数，输出给定的字符串
~simpleCompression();
std::string compress(); //编码字符串
std::string uncompress(std::string str2); //解码字符串
std::string s2b(); //字符对应的二进制字节码以字符串的形式输出
};
simpleCompression.cpp
#include "simpleCompression.h"
simpleCompression::simpleCompression(std::string s)
{
str = s;
std::set<char> ch;
for (char const c : s)
ch.insert(c);
int x = 1,y=2;
while (y < ch.size()) {
x++;
y *= 2;
}
bitLen = x;
int i = 0;
for (const char c:ch) {
std::string str1(bitLen,'0');//初始化
int z = i++,k=1;
while (z != 0) {
int b = z % 2;
str1[bitLen - k++] = b==1 ? '1' : '0';
z = (z - b) / 2;
}
stringToBit[c] =str1;
}
}
simpleCompression::~simpleCompression(){}
std::string simpleCompression::compress()
{
std::string str1;
for (char const c : str)
str1.append(stringToBit[c]);
return str1;
}
std::string simpleCompression::uncompress(std::string str2)
{
std::map<std::string, char> bit2String;
for (auto it = stringToBit.cbegin(); it != stringToBit.cend(); ++it)
bit2String[it->second] = it->first;
std::string str1;
for (int i = 0; i < str2.size(); i += bitLen) {
std::string substr = str2.substr(i,bitLen);
str1.push_back(bit2String[substr]);
}
return str1;
}
std::string simpleCompression::s2b()
{
std::string str1;
for (auto it = stringToBit.cbegin(); it != stringToBit.cend(); it++) {
str1.push_back(it->first);
str1.push_back(':');
str1.append(it->second);
str1.push_back(',');
}
return str1;
}
然后是霍夫曼编码
huffman.h
#pragma once
#include<string>
#include<map>
#include<vector>
//先定义一个节点
struct treeNode {
int val;
char ch;
std::string coding;
treeNode *right, *left;
treeNode(int v, char c) :val(v), ch(c), coding(""), right(nullptr), left(nullptr) {}
treeNode(int v) :val(v), ch(NULL), coding(""), right(nullptr), left(nullptr) {}
};
//
class huffman
{
private:
std::string str;
treeNode* root;
std::map<char, std::string> charToBit;
public:
huffman(std::string strs);
~huffman();
std::string compress();
std::string uncompress(std::string strr);
std::string s2b();
void treeWalk(treeNode* x);//遍历整个树同时将char对应的节点和它对应的二进制码加入到映射charToBit中
};
huffman.cpp
#include "huffman.h"
//#include<algorithm> //可以借助泛型算法来简化这个流程的，但其实不是必须的，理论上尽可能的不要用到其它的库比较好
huffman::huffman(std::string strs)
{
str = strs;
std::map<char, int>stat; //统计字符串中各字符出现的次数
for (char const c : str) {
if (stat.find(c) == stat.end())
stat[c] = 1;
else
stat[c]++;
}
std::vector<treeNode*> coll; //按照val的大小插入vector容器中
for (auto it = stat.begin(); it != stat.end(); ++it) {
//std::cout << it->first << ":" << it->second << std::endl;
//auto it1 = coll.begin();
int i = 0,j=0;//
while (i<=coll.size()) {
if (i == coll.size()) {
j = i;
i++;
}
else if (coll[i]->val > it->second) {
i++;
}
else {
j = i;
i = coll.size()+1;
}
}
//std::cout << j<<", " <<it->first<<" "<<it->second<< std::endl;
coll.insert(coll.begin()+j, new treeNode(it->second, it->first));
}
//std::sort(coll.begin(), coll.end(), [](const treeNode* s1, const treeNode* s2) {return s1->val > s2->val; });
//for (auto c : coll)
//std::cout << c->ch << ":" << c->val << std::endl;
while (coll.size() != 1) {
treeNode* left = coll[coll.size() - 1], * right = coll[coll.size() - 2];
coll.pop_back(); coll.pop_back();
treeNode* p = new treeNode(left->val + right->val);
//std::cout << "p:" << p->val << std::endl;
p->left = left;
p->right = right;
int i = 0,j=0;
while (i <= coll.size()) {
if (i == coll.size()) {
j = i;
i++;
}
else if (coll[i]->val >= p->val) {
i++;
}
else {
j = i;
i = coll.size() + 1;
}
}
coll.insert(coll.begin()+j, p);
//std::sort(coll.begin(), coll.end(), [](const treeNode* s1, const treeNode* s2) {return s1->val > s2->val; });
}
root = coll[0];
//std::cout << "root->val:" << root->val << std::endl;
treeWalk(root);
}
huffman::~huffman()
{
}
std::string huffman::compress()
{
std::string str1;
for (char const c : str)
str1.append(charToBit[c]);
return str1;
}
std::string huffman::uncompress(std::string strr)
{
std::map<std::string, char> bit2Char;
for (auto it = charToBit.begin(); it != charToBit.end(); ++it)
bit2Char[it->second] = it->first;
std::string str1="", str2 = "";
for (auto const c : strr) {
str2.push_back(c);
if (bit2Char.find(str2) != bit2Char.end()) {
str1.push_back(bit2Char[str2]);
str2 = "";
}
}
return str1;
}
std::string huffman::s2b()
{
std::string str1;
for (auto it = charToBit.begin(); it != charToBit.end(); ++it) {
str1.push_back(it->first);
str1.push_back(':');
str1.append(it->second);
str1.push_back(',');
}
return str1;
}
void huffman::treeWalk(treeNode* x)
{
if (x) {
if (x->left) {
x->left->coding=x->coding+'0';
//x->left->coding.push_back('0');
}
if (x->right) {
x->right->coding=x->coding+'1';
//x->right->coding.push_back('1');
}
if(x->right==nullptr&&x->left==nullptr){
charToBit[x->ch] = x->coding;
//std::cout <<x->ch<<" :"<< x->coding << std::endl;
}
treeWalk(x->left);
//std::cout << x->coding << std::endl;
treeWalk(x->right);
}
}
测试，并比较简单编码和霍夫曼编码的差别
main.cpp
#include"simpleCompression.h"
#include<iostream>
#include"huffman.h"
int main() {
std::string str = "everyday is awesome!";
std::cout << "Simple compression" << std::endl;
simpleCompression sc(str);
std::string compress = sc.compress();
std::string uncompress = sc.uncompress(compress);
std::cout << compress << std::endl;
std::cout << uncompress << std::endl;
std::cout << sc.s2b() << std::endl;
std::cout << "Huffman compress:" << std::endl;
double rate = (double)compress.length() / ((double)str.length() * 8);
std::cout << "压缩率：" << rate << std::endl;
huffman h(str);
std::string hc = h.compress();
std::string huc = h.uncompress(hc);
std::cout << hc << std::endl;
std::cout << huc << std::endl;
std::cout << h.s2b() << std::endl;
rate = (double)hc.length() / ((double)str.length() * 8);
std::cout << "压缩率：" << rate << std::endl;
return 0;
}
输出
Simple compression
01001010010010001100001100101100000001011001000000101011010010010111011001000001
everyday is awesome!
:0000,!:0001,a:0010,d:0011,e:0100,i:0101,m:0110,o:0111,r:1000,s:1001,v:1010,w:1011,y:1100,
Huffman compress:
压缩率：0.5
101110010111110011101101100101011000000010011111011000011110110011011010
everyday is awesome!
:010,!:11010,a:011,d:11011,e:10,i:11000,m:11001,o:11110,r:11111,s:000,v:11100,w:11101,y:001,
压缩率：0.45
C:\Users\xhh\Source\Repos\xhh22900\huffmanCompression\huffman\Debug\huffman.exe (进程 45048)已退出，代码为 0。
按任意键关闭此窗口. . .
6.红黑树
红黑树是一颗二叉树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是RED或者BLACK的。通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其它路劲长出2倍，所以近似于平衡的。这样树的每个节点包含5个属性：color、key、left、right、p。如果一个节点没有子节点或者父节点，那么这个节点对应的某个属性的指针是空指针，我们可以将这个指针看作指向二叉搜索树的叶结点（外部节点）的指针，而所有带关键字的节点视为内部节点。
一颗红黑树为满足下面红黑性质的二叉搜素树：
- 每个节点要么是红色要么是黑色。
- 根节点是黑色。
- 每个叶结点是黑色。
- 如果一个节点是红色，则它的两个子节点都是黑色。
- 对每个节点，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色节点。
为了便于处理红黑树代码中的边界条件，我们用一个哨兵来代替空指针。（所有节点的属性中应该为空指针的指针变为指向这个哨兵的指针）。
黑高（black-height，记为bh(x))：从某个节点x出发到达一个叶结点的任意一条简单路径上的黑色节点的个数称为该节点的黑高。
为了维持红黑性质，搜索树的插入和删除操作不能直接用在红黑树上。为此，在需要插入和删除操作时需要需改树种某些节点的颜色及指针结构。
指针结构的修改通过旋转来完成，旋转是一种能保持二叉搜素树性质的搜素树局部操作。有两种旋转操作：左旋和右旋。
红黑树的插入和删除操作都需要考虑所有可能出现的情况，对每种情况做出一些局部调整，包括结构调整和颜色调整，以保证插入和删除操作不会破坏红黑树的红黑性质。但这种事情是非常抽象的。
《算法导论》书中介绍的很详细，但如果只是单纯的看出，很难看懂相关的说明，必须实际的操作，话说书中给出的关键的算法中居然存在错误，实际操作了才能发现的一处致命的错误，不知道原版有没有同样的错误。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tXJo5JDm-1596539879156)(C:\Users\xhh\Pictures\QQ浏览器截图\algo1.png)]
其中第12行到第14的三行代码前应该加上一个else表示这三行是输入前面的判断语句的，没有else的话就不在前面的判断语句中了，这样会导致明显的错误，按照这个算法编写的C++程序不会报错（这不是语法错误而是逻辑错误）但不会出现正确的结果。总之这些算法只能自己感悟，书上已经解释的够详细的了。
花了很长时间完成了红黑树的C++实现，其中包括了搜索、遍历、插入和删除操作，基本上能正常运算，但不保证里面不会出现逻辑错误。
RedBlackTree.h
#pragma once
#include<iostream>
#include<queue>
#define RED true
#define BLACK false
struct treeNode
{
int key;
bool color;//由于节点只有红色和黑色，直接用布尔值来表示颜色就行了，true for RED, false for BLACK
treeNode* p, * left, * right;
treeNode(int k, bool c) :key(k), color(c), p(nullptr), left(nullptr), right(nullptr) {}
treeNode(int k) :key(k), color(RED), p(nullptr), left(nullptr), right(nullptr) {}
};
class RedBlackTree
{
private:
treeNode* root, * nil;//根节点和叶节点（外部节点）
public:
RedBlackTree();
~RedBlackTree();
void leftRotate(treeNode* x); //左旋
void rightRotate(treeNode* x); //右旋
void rbInsert(treeNode* z); //插入元素
void rbInsert(int x);
void rbInsertFixup(treeNode* z); //辅助程序，添加节点后的调整程序，对节点重新着色并旋转
void rbTransplant(treeNode* u, treeNode* v);
void rbDelete(treeNode* z); //删除
void rbDeleteFixup(treeNode* z); //删除节点后的调整程序
treeNode* treeMin(treeNode* z);
treeNode* treeMax(treeNode* z);
void preTreeWalk(treeNode* x); //前序遍历
void inoTreeWalk(treeNode* x); //中序遍历
void postTreeWalk(treeNode* x); //后序遍历
void levelOrder(); //广度优先
treeNode* getRoot();
treeNode* search(int x); //搜索数值为x的节点R
};
RedBlackTree.cpp
#include "RedBlackTree.h"
RedBlackTree::RedBlackTree() : nil(new treeNode(0, BLACK)) { root = nil; }
RedBlackTree::~RedBlackTree()
{
delete root; delete nil;
}
void RedBlackTree::leftRotate(treeNode* x)
{
//std::cout << "\n左旋-->" << x->key<<std::endl;
//levelOrder();
//std::cout << "\n左旋" << std::endl;
treeNode* y = x->right;
x->right = y->left;
if (y->left != nil)
y->left->p = x;
y->p = x->p;
if (x->p == nil)
root = y;
else if (x->p->left == x)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p = y;
}
void RedBlackTree::rightRotate(treeNode* y)
{
//std::cout << "\n右旋-->" << y->key<< std::endl;
//levelOrder();
//std::cout << "\n右旋" << std::endl;
treeNode* x = y->left;
y->left = x->right;
if (x->right != nil)
x->right->p = y;
x->p = y->p;
if (y->p == nil)
root = x;
else if (y->p->right == y) //这里由于之前一不小心少了一个‘=’符号，导致后面一连串的错误，为此我debug了好久。。。
y->p->right = x;
else
y->p->left = x;
x->right = y;
y->p = x;
}
void RedBlackTree::rbInsert(treeNode* z)
{
treeNode* x = root,* y = nil;
while (x != nil) {
y = x;
if (z->key < x->key)
x = x->left;
else
x = x->right;
}
z->p = y;
if (y == nil)
root = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
z->left = nil;
z->right = nil;
z->color = RED;
rbInsertFixup(z);
}
void RedBlackTree::rbInsert(int x)
{
rbInsert(new treeNode(x));
}
void RedBlackTree::rbInsertFixup(treeNode* z)
{
while (z->p->color == RED) {
if (z->p == z->p->p->left) {
treeNode* y = z->p->p->right;
if (y->color == RED) {
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else if (z == z->p->right) {
z = z->p;
leftRotate(z);
}
else {
z->p->color = BLACK;
z->p->p->color = RED;
rightRotate(z->p->p);
}
}
else if (z->p == z->p->p->right) {//左右互换
treeNode* y = z->p->p->left;
if (y->color == RED) {
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else if (z == z->p->left) {
z = z->p;
rightRotate(z);
}
else {
z->p->color = BLACK;
z->p->p->color = RED;
leftRotate(z->p->p);
}
}
root->color = BLACK;
}
}
void RedBlackTree::rbTransplant(treeNode* u, treeNode* v)
{
if (u->p == nil)
root = v;
else if (u == u->p->left)
u->p->left = v;
else
u->p->right = v;
v->p = u->p;
}
void RedBlackTree::rbDelete(treeNode* z)
{
std::cout << "\n删除--" << z->key << std::endl;
treeNode* y = z, * x;
bool yOriginalColor = y->color;
if (z->left == nil) {
x = z->right;
rbTransplant(z, z->right);
}
else if (z->right == nil) {
x = z->left;
rbTransplant(z, z->left);
}
else {
y = treeMin(z->right);
yOriginalColor = y->color;
x = y->right;
if (y->p == z)
x->p = y;
else {
rbTransplant(y, y->right);
y->right = z->right;
y->right->p = y;
}
rbTransplant(z, y);
y->left = z->left;
y->left->p = y;
y->color = z->color;
}
if (yOriginalColor == BLACK) //如果删除的节点的颜色是黑色，那么就必须要对红黑树的剩余代节点做一些处理了
rbDeleteFixup(x); //但如果删除的颜色是红色，那么并不需要做额外的处理
}
void RedBlackTree::rbDeleteFixup(treeNode* x)
{
while (x != root && x->color == BLACK) {
if (x == x->p->left) {
treeNode* w = x->p->right;
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
leftRotate(x->p);
w = x->p->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->p;
}
else if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rightRotate(w);
w = x->p->right;
}
w->color = x->p->color;
x->p->color = BLACK;
w->right->color = BLACK;
leftRotate(x->p);
x = root;
}
else if(x==x->p->right){
treeNode* w = x->p->left;
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
leftRotate(x->p);
w = x->p->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->p;
}
else if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
leftRotate(w);
w = x->p->left;
}
w->color = x->p->color;
x->p->color = BLACK;
w->left->color = BLACK;
rightRotate(x->p);
x = root;
}
}
x->color = BLACK;
}
treeNode* RedBlackTree::treeMin(treeNode* z)
{
while (z->left != nil)
z = z->left;
return z;
}
treeNode* RedBlackTree::treeMax(treeNode* z)
{
while (z->right != nil)
z = z->right;
return z;
}
void RedBlackTree::preTreeWalk(treeNode* x)
{
while (x!=nil) {
std::cout << x->key << "--" << x->color << std::endl;
preTreeWalk(x->left);
preTreeWalk(x->right);
}
}
void RedBlackTree::inoTreeWalk(treeNode* x)
{
while (x!=nil) {
inoTreeWalk(x->left);
std::cout << x->key << "---" << x->color << std::endl;
inoTreeWalk(x->right);
}
}
void RedBlackTree::postTreeWalk(treeNode* x)
{
while (x!=nil) {
inoTreeWalk(x->left);
inoTreeWalk(x->right);
std::cout << x->key << "---" << x->color << std::endl;
}
}
void RedBlackTree::levelOrder()
{
std::queue<treeNode*> allNode; //队列，先进先出，用在这里再合适不过了
allNode.push(root);
int t = 0, l;
while (allNode.size() != 0) {
l = allNode.size();
std::cout << "\n第" << t++ << "层的所有元素, " << l << std::endl;
for (int i = 0; i < l; ++i) {
treeNode* x = allNode.front();
allNode.pop(); //注意，队列queue没有直接弹出一个元素的操作，显示第一个元素后要删除这个元素才能达到我们的目的
std::cout << x->key << " --"<<x->color<<" ";
if (x->left != nil) {
allNode.push(x->left);
std:: cout << "left, " ;
}
if (x->right != nil) {
allNode.push(x->right);
std::cout << "right ";
}
}
}
}
treeNode* RedBlackTree::getRoot()
{
return root;
}
treeNode* RedBlackTree::search(int x)
{
treeNode* z = root;
while (z != nil) {
if (z->key > x)
z = z->left;
else if (z->key < x)
z = z->right;
else
return z;
}
return nil;
}
main.cpp
#include"RedBlackTree.h"
int main() {
RedBlackTree rbt;
rbt.rbInsert(new treeNode(10));
//rbt.levelOrder();
rbt.rbInsert(new treeNode(9));
//rbt.levelOrder();
rbt.rbInsert(new treeNode(8));
rbt.levelOrder();
//for (int i = 0; i < 7; i++)
//rbt.rbInsert(new treeNode(i));
rbt.rbInsert(new treeNode(1));
rbt.levelOrder();
rbt.rbInsert(new treeNode(11));
std::cout << "-------------------" << std::endl;
rbt.levelOrder();
rbt.rbInsert(new treeNode(7));
//rbt.getRoot()->left->key = 6;
std::cout << "-------------------" << std::endl;
rbt.levelOrder();
rbt.rbInsert(new treeNode(14));
rbt.levelOrder();
rbt.rbInsert(4);
rbt.levelOrder();
std::cout << "\n搜素："<<rbt.search(8)->key << std::endl;
rbt.rbDelete((rbt.search(9)));
rbt.levelOrder();
}
输出
第0层的所有元素, 1
9 --0 left, right
第1层的所有元素, 2
8 --1 10 --1
第0层的所有元素, 1
9 --0 left, right
第1层的所有元素, 2
8 --0 left, 10 --0
第2层的所有元素, 1
1 --1 -------------------
第0层的所有元素, 1
9 --0 left, right
第1层的所有元素, 2
8 --0 left, 10 --0 right
第2层的所有元素, 2
1 --1 11 --1 -------------------
第0层的所有元素, 1
9 --0 left, right
第1层的所有元素, 2
7 --0 left, right 10 --0 right
第2层的所有元素, 3
1 --1 8 --1 11 --1
第0层的所有元素, 1
9 --0 left, right
第1层的所有元素, 2
7 --0 left, right 11 --0 left, right
第2层的所有元素, 4
1 --1 8 --1 10 --1 14 --1
第0层的所有元素, 1
9 --0 left, right
第1层的所有元素, 2
7 --1 left, right 11 --0 left, right
第2层的所有元素, 4
1 --0 right 8 --0 10 --1 14 --1
第3层的所有元素, 1
4 --1
搜素：8
删除--9
第0层的所有元素, 1
10 --0 left, right
第1层的所有元素, 2
7 --1 left, right 11 --0 right
第2层的所有元素, 3
1 --0 right 8 --0 14 --1
第3层的所有元素, 1
4 --1
C:\Users\xhh\Source\Repos\c++study\redBlackTree\Debug\redBlackTree.exe (进程 10388)已退出，代码为 0。
按任意键关闭此窗口. . .