最优二叉树【官方澳门新永利下载】

基本概念

给定n个权值作为n的[叶子]结点,构造一棵二叉树,若带权路径长度到达最小,称那样的二叉树为最优二叉树,也叫做哈夫曼树(Huffman
Tree)。哈夫曼树是带权路线长度最短的树,权值比较大的结点离根较近。

思路将输入的每多少个叶子节点权值存入数组arr[]中,并将每一个纸牌节点建成一颗树,存入数组tree[]中,因为有n个叶子节点,所以创立最优二叉树要求n-1步,每趟在arr[]数组中找到最小的七个值,创建四个新的节点,存入tree[]中,将新节点的权值存入arr[]中,最后建成一颗最优二叉树。

概念节点

struct treenode { int data; treenode *lch; //左孩子 treenode *rch; //右孩子};

创设最优二叉树

treenode *huffmanTree { //n为叶子个数 int index = 0; for (int i = 0; i < n; ++i) { //将每一个叶子节点建成一棵树,放入数组tree[]中 treenode *p = new treenode; p->data = arr[i]; //arr[]中放着叶子节点的权值 p->lch = NULL; p->rch = NULL; tree[index++] = p; } treenode *root = NULL; //定义最优二叉树的根 for (int i = 0; i < n - 1; ++i) { //每次取arr[]中未使用的最小两个值 sort(arr + i, arr + n); treenode *ch1 = NULL, *ch2 = NULL; for (int j = 0; j < index; ++j) {//在数组tree[]中找到这两个值,建立新的节点 if(tree[j]->data == arr[i]) ch1 = tree[j]; if(tree[j]->data == arr[i + 1]) ch2 = tree[j]; if(ch1 && ch2) break; } treenode *p = new treenode;//建立新的节点,存入数组tree[]中 p->data = ch1->data + ch2->data; p->lch = ch1; p->rch = ch2; root = p;//更新根,直到建立完成 tree[index++] = p; arr[i + 1] = p->data;//并将这个节点的权值传入数组arr[]中 } return root;}

估测计算权值WPL

结点的权及带权路线长度若将树中结点赋给二个富有某种意义的数值,则那个数值称为该结点的权。结点的带权路线长度为:从根结点到该结点之间的不二秘籍长度与该结点的权的乘积。树的带权路线长度树的带权路径长度规定为富有叶子结点的带权路径长度之和,记为WPL。

void weight(treenode *root, int n) {//n为树当前的层数,root为最优二叉树的根 treenode *p = root; if(p != NULL) { if((p->lch) == NULL && (p->rch) == NULL) {//即当p为叶子节点时 //cout << p->data << endl; w += n * (p->data);//w为最优二叉树的权值 } weight(p->lch, n + 1); weight(p->rch, n + 1); }}

C++代码

#include <iostream>#include <algorithm>using namespace std;const int MAX_N = 1e6;int arr[MAX_N];int w = 0;struct treenode { int data; treenode *lch; treenode *rch;};treenode *tree[MAX_N];int main() { int n; cin >> n; for (int i = 0; i < n; ++i) cin >> arr[i]; treenode *root = NULL; root = huffmanTree; weight;//注意0 cout << w << endl; return 0;}


一:什么是最优二叉树?

从本身个人明白的话,最优二叉树就是从已交付的靶子带权结点
经过一种办法的结合产生一棵树.使树的权值最小.
最优二叉树是带权路线长度最短的二叉树。依照结点的个数,权值的例外,最优二叉树的模样也各分歧。它们的共同点是:带权值的结点都以卡片结点。权值越小的结点,其到根结点的路径越长

合法概念:

在权为wl,w2,…,wn的n个叶子所结合的具有二叉树中,带权路线长度最小的二叉树称为最优二叉树哈夫曼树

二:上边先弄清多少个多少个概念:

1.门道长度

在树中从一个结点到另一个结点所经历的道岔构成了那三个结点间的不二法门上的分支数称为它的门路长度

2.树的门径长度
 树的路径长度是从树根到树中每一结点的门路长度之和。在结点数目一样的二叉树中,完全二叉树的不二秘籍长度最短。

3.树的带权路线长度(Weighted Path Length of Tree,简记为WPL)
  结点的权
:在一些运用中,赋予树中结点的三个有某种意义的实数。
  结点的带权路线长度:结点到树根之间的门道长度与该结点上权的乘积。
  树的带权路线长度(Weighted
Path Length of
Tree):定义为树中具有叶结点的带权路线长度之和,平时记为:

发表评论

电子邮件地址不会被公开。 必填项已用*标注