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;
}