Algorithm11.5 数据结构 二叉类型相关树结构-哈夫曼树/二叉搜索树/红黑树/B+树
[TOC]
二叉类型相关数据结构
哈夫曼树
性质
实现-二叉链表
二叉链表实现 - 利用链表来链接起树的结构
1、节点中有两个指向叶子结点的指针。结构体的因为是二叉链表，所以和二叉树的类似。
struct node(){
int data;
node * lchild;
node * rchild;
} *huffmantree, huffman[maxn];;
2、新增的数据结构：也就是huffman[maxn]，起作用就是储存所有的节点的。
对应的思路，每次挑出节点中值最小的两个，然后把这两个节点合成一个，然后进行排序，并把新产生的节点放到优先队列中，然后再选出两个最小的，一直这么迭代下去。
- 通过一个vis数组，来将右儿子给闭掉，然后将左儿子的值更新为他们所形成的父亲节点的值。
node * HuffmanTree() {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n; ++j) if (!vis[j]) pq.push({huffman[j].data, j});
ll = pq.top().idx;pq.pop();
rr = pq.top().idx;
while (!pq.empty()) pq.pop();
vis[rr] = 1;
node * lnode = new node {huffman[ll].data, huffman[ll].lchild, huffman[ll].rchild};
huffman[ll] = {huffman[ll].data + huffman[rr].data, lnode, &huffman[rr]};
}
return &huffman[ll];
}
- 通过对优先队列的维护，每次弹出右儿子，左儿子更新了值再放回去
node * HuffmanTree() {
for (int j = 0; j < n; ++j) pq.push({huffman[j].data, j});
for (int i = 0; i < n - 1; i++) {
ll = pq.top().idx;pq.pop();
rr = pq.top().idx;pq.pop();
vis[rr] = 1;
node * lnode = new node {huffman[ll].data, huffman[ll].lchild, huffman[ll].rchild};
huffman[ll] = {huffman[ll].data + huffman[rr].data, lnode, &huffman[rr]};
pq.push({huffman[ll].data, ll});
}
return &huffman[ll];
}
3、测试用例：
input:
8
5 29 7 8 14 23 3 11
output:
100 42 19 8 3 5 11 23 58 29 29 14 15 7 8
完整代码：
#include <iostream>
using namespace std;
const int maxn = 1e5 + 9;
struct node {
int data;
node *lchild;
node *rchild;
} *huffmantree, huffman[maxn];
int n, ll, rr;
#include <queue>
struct nd {
int val, idx;
bool operator < (const nd n) const {return val > n.val;}
};
priority_queue<nd, vector<nd>, less<nd>> pq;
void PreOrder(node *T) {
if (T) {
cout << T->data << " ";
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
node * HuffmanTree() {
for (int j = 0; j < n; ++j) pq.push({huffman[j].data, j});
for (int i = 0; i < n - 1; i++) {
ll = pq.top().idx;pq.pop();
rr = pq.top().idx;pq.pop();
node * lnode = new node {huffman[ll].data, huffman[ll].lchild, huffman[ll].rchild};
huffman[ll] = {huffman[ll].data + huffman[rr].data, lnode, &huffman[rr]};
pq.push({huffman[ll].data, ll});
}
return &huffman[ll];
}
int main(void) {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &huffman[i].data);
// build tree
huffmantree = HuffmanTree();
PreOrder(huffmantree);
return 0;
}
二叉搜索树
也称为二叉查找树、二叉排序树
性质
情况一：左儿子小于父节点 && 右儿子大于父节点 => 中序遍历得到递增序列
情况二：左儿子大于父节点 && 右儿子小于父节点 => 中序遍历得到递减序列
实现
二叉链表实现，每添加一次新的值，就build一次，从根节点往下插入新的值
- 要插入的数比当前节点的值小=>往左子树插入
- 要插入的数比当前节点的值大=>往右子树插入
然后如果插到最底部了，当前这个节点直接NULL了，那就重新new一个这个要插入的数对应的节点。
node * build(node * nw) {
if (nw == NULL) {
nw = new node();
nw->pri = nwpri;nw->val = nwval;
nw->l = nw->r = NULL;
return nw;
}
if (nwval <= nw->val) nw->l = build(nw->l);
else nw->r = build(nw->r);
return nw;
}
（这个建树的过程类似于给出前中序得后序，就是用递归来更新子树的过程）
#include <iostream>
using namespace std;
struct nd {
int val, pri;
bool operator < (const nd n) const {return pri < n.pri;}
}a[35];
int n, nwval, nwpri;
#include <algorithm>
struct node {
int val, pri;
node * l, *r;
}* root;
node * build(node * nw) {
if (nw == NULL) {
nw = new node();
nw->pri = nwpri;nw->val = nwval;
nw->l = nw->r = NULL;
return nw;
}
if (nwval <= nw->val) nw->l = build(nw->l);
else nw->r = build(nw->r);
return nw;
}
#include <queue>
queue<node*> q;
#include <vector>
vector<int> v_val, v_pri;
void level_traverse(node * nw) {
q.push(nw);
while (!q.empty()) {
node * nwnode = q.front();q.pop();
v_val.push_back(nwnode->val);
v_pri.push_back(nwnode->pri);
if (nwnode->l) q.push(nwnode->l);
if (nwnode->r) q.push(nwnode->r);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].val, &a[i].pri);
sort(a+1, a+1+n);
for (int i = 1; i <= n; ++i) {
nwval = a[i].val, nwpri = a[i].pri;
root = build(root);
}
level_traverse(root);
for (int i = 0; i < v_val.size(); ++i) {
if (i != 0) cout<<" ";
cout<<v_val[i];
}
cout<<endl;
for (int i = 0; i < v_pri.size(); ++i) {
if (i != 0) cout<<" ";
cout<<v_pri[i];
}
return 0;
}