由于红黑树的删除用到了二叉树的一些函数 所以我们从二叉树讲起
二叉树 不带颜色的红黑树 看看两张画的有点丑的图
如图
一个节点 记录一个数值 同时还有两个指向该节点两个儿子的标识
儿子有两个 左儿子和右儿子
图中就有两个二叉树示例
一个仅有右儿子 一个左右儿子均有
C语言中或者C++语言中我们这样定义二叉树结构
struct node {
std::shared_ptr<node> left_; //智能指针
std::shared_ptr<node> right_;
int value_;
node() {
left_ = right_ = nullptr;
value_ = -1;
}
};
那么遍历树中的元素然后打印的代码如下
void PrintTree(const std::shared_ptr<node>& root) {
if (root == nullptr)
return;
std::cout << root->value_ << " ";
PrintTree(root->left_);
PrintTree(root->right_);
}
我们现在创建一个图中TREE2并把它的元素数值依次打印出来
// 122.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <memory>
#include <iostream>
struct node {
std::shared_ptr<node> left_;
std::shared_ptr<node> right_;
int value_;
node() {
left_ = right_ = nullptr;
value_ = -1;
}
};
void PrintTree(const std::shared_ptr<node>& root) {
if (root == nullptr)
return;
std::cout << root->value_ << " ";
PrintTree(root->left_);
PrintTree(root->right_);
}
int main()
{
std::shared_ptr<node> root(new node);
root->value_ = 2;
std::shared_ptr<node> x(new node);
x->value_ = 1;
root->left_ = x;
std::shared_ptr<node> y(new node);
y->value_ = 3;
root->right_ = y;
PrintTree(root);
std::cout << std::endl;
return 0;
}
打印结果如图:
原文：http://www.cnblogs.com/itdef/p/6393738.html