哈夫曼树的建立 还没写完 在改正

存储结构: 

class node{
    public:
        int weight; 权值域，保存该节点的权值
        int lchild; 指针域，结点的左孩子在数组中的下标
        int rchild; 指针域 结点的右孩子在数组中的下标
        int parent; 指针域，该节点的双亲结点在数组中的下标
}

性质:

在构建哈夫曼树的过程，只有出度为0和2的结点，

在二叉树中 n0 = n2 + 1  ------》  n2 = n0-1  代入下面公式

因此n=n0+n2 = n0+(n0-1) = 2*n0 -1  所以创建数组大小为2*n0 -1大小的数组

哈夫曼树的创建:

1. 数组huffTree初始化，所有元素结点的双亲，左孩子，右孩子都设置为-1;

2.数组huffTree的前n个元素的权值给定值w[n];

3.进行n-1次合并, (当有3个元素是需要合并两次）所以要合并n-1次

        3.1 在二叉树集合中选取两个权值最小的根节点，权值最小结点其下标分别为i1,i2;

        3.2 将二叉树i1,i2合并为一棵新的二叉树k

创建哈夫曼树代码

void huffTree(node huffTree[], int w[], int n){
    int i1,i2;
    for(int i=0; i 
 说一下找最小值的思路:
 
首先设置一个较大的元素，之后遍历数组，当数组中的元素比这个元素小的时候，就让数组中的元素等于这个元素并记录该元素下标.  对于哈夫曼树还要满足一个条件就是parent域必须是-1；
 
 
为什么定义较大的元素，因为当这个元素很小比如是2，输入arr[3]={5,6,7}，则比较最小值时候，数组中没有一个数值比最小值还小，最终不能交换，导致查到的最小值是自己设置的值，而不是数组中的值。
 
找次小值的思路：
 
首先定义一个较大的值secmin，之后遍历数组，对于哈夫曼树有一个条件就是parent域为-1，用数组中的每一个元素和这个最小值作比较，但是数组中的元素不能是之前循环判断的最小的那个元素，怎么判断不是最小的那个呢，在找最小值的时候已经记录了最小值的下标，这次让判断时候，除了要求数组元素小于secmin,并且让这次访问的数组下标不等于最小值的下标就好了.
 
void select(node huffTree[], int k,int n, int &i1, int &i2){
	
	int min_data = 6666, secmin_data = 6666;   
    //设置大点,如果小了，数组中的元素都没有min_data小，则就进不去数组中选择元素
	
    int min_loc,secmin_loc; //用来记录最小值的位置
	//找到最小的结点 
	for(int i=0; i
						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/3970862.html