c++ 树集合实现记录

• 二叉树

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
template<class Elem>
struct BinNode//定义二叉树链表
{
Elem data;
BinNode <Elem>* left;
BinNode <Elem>* right;
int h;
BinNode(Elem x) {
//初始化
data = x;
h = -1;
left = right = NULL;
}
};
//定义某种类的模板类型复杂数据时需要用 类名<..> 来声明类型
template<class Elem>
class BinTree {
protected:
BinNode<Elem>* root;
void rpreprint(BinNode<Elem>* r) {
//递归遍历
if (r == NULL) return;
cout << r->data << " ";
rpreprint(r->left);
rpreprint(r->right);
}
BinNode<Elem>* rfindx(Elem x, BinNode<Elem>* r) {
//树为空树,或者没找到
if (!r) return NULL;
//刚好找到了
if (r->data == x) return r;
//遍历查找
BinNode<Elem>* found;
found = rfindx(x, r->left);
//不在左边，就在右边或者不存在
// .....？ x:y 三元表达式
return found ? found : rfindx(x, r->right);
}
void rprint(BinNode<Elem>* r, int depth) {
for (int i = 0; i < depth; i++) {
cout << "
";//深度越大，打印的空格越多
}
if (!r) {
cout << "[/]" << endl;
}
else
{
cout << r->data << endl;
rprint(r->left, depth + 1);//先打印左
rprint(r->right, depth + 1);//后打印右
}
}
void rinprint(BinNode<Elem>* r) {
//递归遍历
if (r == NULL) return;
rpreprint(r->left);
cout << r->data << " ";
rpreprint(r->right);
}
void rbackprint(BinNode<Elem>* r) {
//递归遍历
if (r == NULL) return;
rpreprint(r->left);
rpreprint(r->right);
cout << r->data << " ";
}
void ipreprint(BinNode<Elem>* r) {
//用stack是为了记录路径
stack<BinNode<Elem>*> st;
if (!r) return;
while (r)
{
cout << r->data << ' ';
st.push(r);
r = r->left;
while (r == NULL && !st.empty()) {
r = st.top();
st.pop();
r = r->right;
}
}
}
void i_in_print(BinNode<Elem>* r) {
//用stack是为了记录路径
stack<BinNode<Elem>*> st;
if (!r) return;
while (r)
{
st.push(r);
r = r->left;
while (r == NULL && !st.empty()) {
r = st.top();
st.pop();
cout << r->data << ' ';
r = r->right;
}
}
}
public://public部分是接口，不显示细节
BinTree() { root = NULL; }
BinTree(Elem r) {
root = new BinNode<Elem>(r);
}
~BinTree() { }
void preprint() {
//
rpreprint(root);
ipreprint(root);
cout << endl;
}
void in_print() {
//
rinprint(root);
cout << endl;
}
BinNode<Elem>* findX(Elem x) {
return rfindx(x, root);
}
bool insert(Elem p, int l_or_r, Elem x) {
//首先找到p节点
BinNode<Elem>* found;
found = findX(p);
if (!found) return false;
if (l_or_r == 0) {
//左边
//类的函数使用类的指针来操作较方便
if (found->left) return false;
//通过new来直接插入
found->left = new BinNode<Elem>(x);
}
else
{
if (found->right) return false;
found->right = new BinNode<Elem>(x);
}
return true;
}
void print_tree() {
rprint(root, 0);
}
};

• 二叉搜索树

#include<iostream>
#include"bintree.h"
using namespace std;
template<class Elem>
class BSTree :public BinTree<Elem> {
protected:
BinNode<Elem>* rfindMax(BinNode<Elem>* r) {
if (r->right == NULL) return r;
return rfindMax(r->right);//尾递归
}
BinNode<Elem>* rinsert(Elem x, BinNode<Elem>* r) {
if (r == NULL) {
r = new BinNode<Elem>(x);
//申请内存失败
if (r == NULL) throw - 1;
return r;
}
//递归插入，当x小于当前值，往左节点插入，直到找到的点为空
else if (x < r->data) {
r->left = rinsert(x, r->left);
}
else if (x > r->data) {
r->right = rinsert(x, r->right);
}
else
{
//等于
throw - 2;
}
return r;
}
BinNode<Elem>* remove(Elem x, BinNode<Elem>* r) {
//r可能为空
BinNode<Elem>* temp;
if (r == NULL) throw - 1;
else if (x < r->data) {
r->left = remove(x, r->left);//更新树根
}
else if (x > r->data) {
r->right = remove(x, r->left);
}
else
{
//节点有两个子节点
if (r->left && r->right) {
temp = rfindMax(r->left);
r->data = temp->data;
r->left = remove(temp->data, r->left);
}
else
{
temp = r;
r = r->left ? r->left : r->right;
delete temp;
}
}
return r;
}
public:
BSTree() {
this->root = NULL;
}
BinNode<Elem>* findMax() {
//return rfindMax(this->root);
BinNode<Elem>* temp;
temp = this->root;
while (temp && temp->right)
{
temp = temp->right;
}
return temp;
}
BinNode<Elem>* findMin() {
BinNode<Elem>* temp;
temp = this->root;
while (temp && temp->left)
{
temp = temp->left;
}
return temp;
}
BinNode< Elem>* findX(Elem x) {
BinNode<Elem>* temp;
temp = this->root;
while (temp && x != temp->data)
{
if (x > temp->data) temp = temp->right;
else temp = temp->left;
}
return temp;
}
bool insert(Elem x) {
//BST不能有重复值
//判断大小
try
{
this->root = rinsert(x, this->root);
}
catch (const std::exception&)
{
return false;
}
return true;
}
//?循环remove
bool remove(Elem x) {
try
{
this->root = remove(x, this->root);
}
catch (const std::exception&)
{
return false;
}
return true;
}
};
int main() {
BSTree<int> bt;
bt.insert(10);
bt.insert(20);
bt.insert(30);
bt.insert(15);
bt.print_tree();
cout << bt.findMax()->data << endl;
cout << bt.findMin()->data << endl;
return 0;
}

• AVL树

//空树高度为-1
#include<iostream>
#include<math.h>
#include"bst.h"
using namespace std;
template<class Elem>
class Avltree :public BSTree<Elem> {
//class ... : public ...继承
protected:
int height(BinNode<Elem>* r) {
if (r == NULL) return -1;
return r->h;
}
BinNode<Elem>* ll_rotate(BinNode<Elem>* r) {
BinNode<Elem>* temp;
temp = r->left;
r->left = temp->right;
temp->right = r;
r->h = max(height(r->left), height(r->right)) + 1;
temp->h = max(height(temp->left), height(temp->right)) + 1;
return temp;
}
BinNode<Elem>* rr_rotate(BinNode<Elem>* r) {
BinNode<Elem>* temp;
temp = r->right;
r->right = temp->left;
temp->left = r;
r->h = max(height(r->left), height(r->right)) + 1;
temp->h = max(height(temp->left), height(temp->right)) + 1;
return temp;
}
BinNode<Elem>* lr_rotate(BinNode<Elem>* r) {
r->left = rr_rotate(r->left);
return ll_rotate(r);
}
BinNode<Elem>* rl_rotate(BinNode<Elem>* r) {
r->right = ll_rotate(r->right);
return rr_rotate(r);
}
//插入函数加个判断
BinNode<Elem>* rinsert(Elem x, BinNode<Elem>* r) {
if (r == NULL) {
r = new BinNode<Elem>(x);
if (r == NULL) throw - 1;
}
else if (x < r->data)
{
r->left = rinsert(x, r->left);
if (height(r->left) - height(r->right) == 2) {
if (x < r->left->data) {
r = ll_rotate(r);
}
else
{
r = lr_rotate(r);
}
}
}
else if(x > r->data)
{
r->right = rinsert(x, r->right);
if (height(r->right) - height(r->left) == 2) {
if (x > r->right->data) {
r = rr_rotate(r);
}
else
{
r = rl_rotate(r);
}
}
}
else {
throw - 2;
}
r->h = max(height(r->left), height(r->right)) + 1;
return r;
}
public:
Avltree() {
this->root = NULL;
}
};

• 堆

#include<stdio.h>
#include<stdlib.h>
typedef int Elem;
struct Heap
{
Elem* data;
int capcacity;
int size;
};
typedef struct Heap* heap;
heap init_heap(int maxsize) {
//创建堆结构体
heap h;
h = (heap)malloc(sizeof(struct Heap));
if (h == NULL) return NULL;
//创建数组
h->data = (Elem*)malloc(sizeof(Elem) * (maxsize + 1));
if (h->data == NULL) return NULL;
//初始化
h->size = 0;//记录元素个数
h->capcacity = maxsize;//用于记录有效大小，为实际大小减1
return h;
}
void print_heap(heap h) {
for (int i = 1; i < h->size; i++) {
printf("%d ,", h->data[i]);
}
putchar('n');
}
void percolate_up(int k, heap h) {
int x;
//保存k节点的值
x = h->data[k];
int i;
for (i = k; i > 1 && h->data[i] < h->data[i / 2]; i = i / 2) {
//如果i不为树根处，且父节点比子节点更大，交换
h->data[i] = h->data[i / 2];
}
h->data[i] = x;
h->size++;
}
int isfull(heap h) {
return h->capcacity == h->size;
}
int insert_heap(heap h, Elem x) {
if (isfull(h)) return 0;
h->data[++h->size] = x;//插入
percolate_up(h->size, h); //把顺序表向上过滤
return 1;
}
void destroy(heap h) {
free(h->data);
free(h);
}
int main() {
heap h;
h = init_heap(10);
insert_heap(h, 20);
insert_heap(h, 10);
insert_heap(h, 5);
print_heap(h);
destroy(h);
return 0;
}

最后

以上就是粗暴咖啡为你收集整理的c++ 树集合实现记录的全部内容，希望文章能够帮你解决c++ 树集合实现记录所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。