精华内容
下载资源
问答
  • 基本概念: 1.树 树是n个结点有限集,他或是空树,或是非空树。对于非空树,有且仅有一个称之为根结点,除根节点以外,... 如果将树中结点各子树看成从左至右是有次序,则称为有序树,反之为无序树。 ...

    基本概念:

    1.树

         树是n个结点的有限集,他或是空树,或是非空树。对于非空树,有且仅有一个称之为根的结点,除根节点以外,其余结点可分为互不相交的有限集,他们每棵又都是树,称为根的子树。树的结构的定义是一个递归的定义。

    2.结点

        树中一个独立单元,包含一个数据元素及若干指向其子树的分支。

    3.结点的度

        结点拥有的子树数

    4.树的度

        树内各结点度的最大值

    5.有序树,无序树

        如果将树中结点的各子树看成从左至右是有次序的,则称为有序树,反之为无序树。

    6.二叉树

        树是n个结点的有限集,他或是空树,或是非空树。对于非空树,有且仅有一个称之为根的结点,除根节点以外,其余结点可分为互不相交的有限集,他们每棵又都是树,称为根的子树。树的结构的定义是一个递归的定义。并且二叉树每个结点最多只有两棵子树,二叉树子树有左右之分,次序不能任意颠倒。

    7.完全二叉树

         深度为k,有n个结点的二叉树,当且仅当每一个结点的深度都为k的满二叉树中编号从1到n的结点一一对应时,称为完全二叉树。叶子结点只可能出现在最大的两层上,对任一结点若其右分支子孙深度为l,则其左分支子孙深度必然是l或l+1;

    8.线索二叉树

          结点有五个区域:数据域,左孩子(lchild),右孩子(rchild),LTag,RTag;

          LTag:   LTag=0  lchild表示左孩子

                        LTag=1  lchild表示该结点前驱

         RTag:   RTag=0  rchild表示右孩子

                        RTag=1  rchild表示该结点后继

     

    性质

    1.在二叉树上第i层至多有2^{i-1}个结点(i>=1)

    2.深度为k的二叉树至多有2^{k}-1个结点(k>=1)

    3.对任何一棵二叉树T,如果其终端结点树是n0,度为2的结点树是n2,则n0=n2+1,n=n0+n1+n2

    4.具有n个结点的完全二叉树深度为[log_{2}n]+1

     

    存储结构

    顺序存储:

    对于完全二叉树,从根按层存储,依次自上而下,自左而右存储结点元素。如果不是完全二叉树,其他情况可能造成空间浪费

    #define MAXSIZE 100   //二叉树最大结点个数
    typedef TElemType SqBiTree[MAXSIZE]    //0号单元存储根结点
    SqBiTree bt;

    链式存储:(链表头指针指向根结点)

    二叉链表:

    数据域,左指针域,右指针域。---------------------含有n个结点的二叉链表有n+1个空链域

    三叉链表:

    数据域,左指针域,右指针域,指向双亲结点指针域。

    typedef struct BiTNode
    {
        TElemType data;//数据域
        struct BiTNode *lchild,*rchild;//左右孩子指针
    }BiTNode,*BiTree;

     

    遍历 ( 以一定规则将二叉树中结点排成一个线性序列,得到二叉树结点的先序序列,中序序列,后序序列===对非线性结构进行线性操作,是每个结点有且仅有一个直接前驱和直接后继(除第一个和最后一个以外)

    遍历二叉树

        以中序为例:先遍历左子树,根结点,右子树

        

    void InOrderTraverse(BiTree T)
    {
        if(T)//二叉树非空
        {
            InOrderTraverse(T->left);//遍历左子树
            printf("%d  ",T->data);//访问根结点
            InOrderTraverse(T->right);//遍历右子树
        }
    }
    

    遍历线索二叉树

    以中序为例

    void InOrderTraverse_Thr(BiThrTree T)
    {//中序遍历,对每个直接输出
     //T指向头结点,头结点的左链表lchild指向根结点
    
        p=T->lchild;     //p指向根结点
        while(p!=T)        //p==T空树或遍历结束
        {
            while(p->LTag==0)//沿着左孩子向下
            {
                p=p->lchild;
                printf("%d  ",p->data);
            }
            while(p->RTag==1&&p->rchild!=T)//沿着右线索访问后继结点
            {
                p=p->rchild;
                printf("%d  ",p->data);
            }
            p=p->rchild;
        }
    }

     

    树和森林

     

    哈夫曼树

    后面两点晚点补起来

     

    展开全文
  • 哈夫曼树

    千次阅读 多人点赞 2017-08-05 23:34:19
    哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域。哈夫曼树不存在入度为1 结点,所以n0=n2+1 设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结

    哈夫曼树节点个数一定是奇数
    假设哈夫曼树是二叉的话,则度为0的结点个数为N,度为2的结点个数为N-1,则结点总数为2N-1。


    哈夫曼树的形态不是唯一的,但是它的带权路径长度WPL是唯一的。
    如:3,5,6
    可以构造出
    14
    8 6
    3 5

    14
    6 8
    3 5
    这两种形态,所以哈夫曼树形态不唯一


    哈夫曼树不可能存在度为1的结点
    生成哈夫曼树的第一步就是在结点集合中找到两个权值最小的结点,然后生成一棵二叉树
    树中任意节点的权值一定大于自己的左右孩子,但不能保证一定不小于其他下一任结点的权值。

    设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域。

    哈夫曼树不存在入度为1 的结点,所以n0=n2+1
    设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有(2m)个空指针域; n0=m
    树的二叉链表存储结构就是孩子-兄弟表示法。
    孩子-兄弟表示法:数据域是结点,如A; 有两个指针域:1)指向长子 2)指向右兄弟
    哈夫曼树的孩子-兄弟表示法的空指针域有三种情况:(1)叶子结点长子域一定为空m个(2)根节点的右兄弟域一定为空 1个 (3)除去根节点外,哈夫曼树的其余结点个数中有一半结点的右兄弟域为空 (n总-1)/2=n2
    所以空指针域=m+1+n2=2m

    哈夫曼树权值结点的父结点实际上是没有值的


    
    一棵哈夫曼树共有215个结点,对其进行哈夫曼编码,共能得到()个不同的码字

    哈夫曼树并不是满二叉树,是正则二叉树(也叫正规二叉树),即其中只有度为0和度为2的结点
    因为n0 = n2 + 1,n = n0 + n2; 所以 n = 2n0 - 1,即n0 = (n + 1) / 2;叶子结点n0对应的即是不同的编码。
    至于满二叉树当然也是正则二叉树的特例。

    展开全文
  • 哈夫曼树构建

    2021-01-08 03:14:38
    哈夫曼树是带权值节点结构,且目标节点存储在叶子节点上。下面使用Go实现哈夫曼树 哈弗曼树构建过程 将带权值的节点进行排序,形成有序链表。 取出链表头两个节点,权值相加形成新节点,并加入上述链表...
  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样...2、排好序之后,将这些数字放入顺序存储结构中,选择最小两个数字,分别以这两个数为左子节点与右子节点,以这两个数字...

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

    构建哈夫曼树的过程:

    1、首先对数组中的数字进行排序,按照从小到大排序;

    2、排好序之后,将这些数字放入顺序存储结构中,选择最小的两个数字,分别以这两个数为左子节点与右子节点,以这两个数字之和为根节点,构造成一个新的二叉树;

    3、在存储结构中删除这两个子节点,并将新的根节点放入存储结构中,重新排序;

    4、按照上面的步骤依次循环,直到只剩下一个节点。

    import java.util.*;
    
    public class Main {
        public static void main(String[] args) {
            int[] arr = {10, 4, 5, 6, 23, 44};
            Node root = createHuffmanTree(arr);
            System.out.println("哈夫曼树前序遍历结果为:");
            preOrder(root);
        }
    
        //哈夫曼树方法
        public static Node createHuffmanTree(int[] arr) {
            //遍历数组,并将数组每个元素变为Node类型,并且放入顺序表中
            List<Node> nodes = new ArrayList<Node>();
            for (int i : arr) {
                nodes.add(new Node(i));
            }
            while (nodes.size() > 1) {
                //从小到大排序
                Collections.sort(nodes);
                //取出节点权值最小的两个节点构成二叉树
                Node leftNode = nodes.get(0);
                Node rightNode = nodes.get(1);
                //重新构建新的二叉树,以之前两个节点为左右子节点
                Node parent = new Node(leftNode.value + rightNode.value);
                parent.left = leftNode;
                parent.right = rightNode;
                //删除两个子节点,并将父节点放入顺序表中
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                nodes.add(parent);
            }
            return nodes.get(0);
        }
    
        //实现前序遍历
        public static void preOrder(Node root) {
            if (root != null) {
                root.preOrder();
            } else {
                System.out.println("该二叉树为空");
            }
        }
    }
    
    //实现Comparable接口
    class Node implements Comparable<Node> {
        int value; //权值大小
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        //实现从小到大排序
        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    
        //前序遍历
        public void preOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }
    }
    
    
    
    哈夫曼树前序遍历结果为:
    Node{value=92}
    Node{value=44}
    Node{value=48}
    Node{value=23}
    Node{value=25}
    Node{value=10}
    Node{value=15}
    Node{value=6}
    Node{value=9}
    Node{value=4}
    Node{value=5}

     

    展开全文
  • 这是我用二叉哈夫曼树代码改,但是无法实现,首先是叶子节点节点数没法表示,然后就算自己输入固定节点也无法正确实现,请问怎么实现三叉哈夫曼树呢 #include #include #include #include using namespace ...
  • 可以这么说,哈夫曼树中,真正有效存储着数据,只有那些叶节点,而其它节点仅仅是为了构造树结构、以及保持总权值最小而存在。 那么问题是,哈夫曼树和文本压缩有什么关系呢?这就不得不提到文本编码问题。 ...

    概览

    本文原载于我的博客,地址:https://blog.guoziyang.top/archives/24/

    哈夫曼树也称为最优二叉树,是加权路径长度最短的二叉树。权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点。每一个父节点的权值等于子节点的权值之和。

    可以这么说,哈夫曼树中,真正有效的、存储着数据的,只有那些叶节点,而其它节点仅仅是为了构造树结构、以及保持总权值最小而存在的。

    那么问题是,哈夫曼树和文本压缩有什么关系呢?这就不得不提到文本编码问题。

    编码与哈夫曼树

    编码(主要是二进制码),是指将一组对象(如字符集)中的每个对象用唯一的一个二进制位串表示。编码的方式有很多种,主要分为两类:等长的和不等长的。等长的自然好理解,每一个字符的二进制码长度都相等,那么不等长的呢?

    很容易就可以想到,不等长的编码有一个问题:二义性,即一串编码可以有多种不同的方式解码,如以下这个例子:

    字符E编码为00,字符T编码为01,字符W编码为0001
    二进制串0001的解码则存在两种方式:ET和W
    

    所以,我们需要这种编码保持前缀性,即一组编码中任意一个编码都不是其它任何一个编码的前缀。而哈夫曼树就可以为我们解决这个问题,即:从根节点到叶节点到路径不存在任何前缀性重复。

    所以,我们引入了哈夫曼编码问题:对于给定的字符集及其每个字符出现的概率(使用频度),求该字符集的最优的前缀性编码。那么总体的思想就很明确了:

    1. 计算每个字符在文本中的出现频率
    2. 构造频率对应的哈夫曼树
    3. 利用这棵树对文本进行编码存储

    编码

    计算字符出现的频率

    这段算法思想比较简单粗暴,直接遍历一遍,把字符和频次存在一个Map里,遍历到一个字符就把那个字符对应的频次加1,最后根据频次计算出该字符对应的频率即可,返回的也是个<字符,频率>的Map。

    Java实现如下:

    private static HashMap<Character, Double> calculateCharChance(String fileContent) {
            if(fileContent == null) {
                return null;
            }
            HashMap<Character, Double> charTimes = new HashMap<>();
            for(int i = 0; i < fileContent.length(); i ++) {
                char tempChar = fileContent.charAt(i);
                if(charTimes.containsKey(tempChar)) {
                    charTimes.put(tempChar, charTimes.get(tempChar) + 1d);
                } else {
                    charTimes.put(tempChar, 1d);
                }
            }
            HashMap<Character, Double> perChance = new HashMap<>();
            for(Map.Entry<Character, Double> entry : charTimes.entrySet()) {
                perChance.put(entry.getKey(), entry.getValue() / fileContent.length());
            }
            return perChance;
        }
    

    构造哈夫曼树

    接着我们就需要构造一棵哈夫曼树,我们首先定义一下每个节点的类:

    class TreeNode implements Serializable{
        private static final long serialVersionUID = 1L;
    
        private Character currentChar = null;
        private Double chance;
        private TreeNode parentNode;
        private TreeNode leftNode;
        private TreeNode rightNode;
    
        public TreeNode(char currentChar, double chance) {
            this.currentChar = currentChar;
            this.chance = chance;
        }
    
        public TreeNode(double chance) {
            this.chance = chance;
        }
    
        public Character getCurrentChar() {
            return currentChar;
        }
    
        public Double getChance() {
            return chance;
        }
    
        public void setParentNode(TreeNode parentNode) {
            this.parentNode = parentNode;
        }
    
        public TreeNode getParentNode() {
            return parentNode;
        }
    
        public void setLeftNode(TreeNode leftNode) {
            this.leftNode = leftNode;
        }
    
        public TreeNode getLeftNode() {
            return leftNode;
        }
    
        public void setRightNode(TreeNode rightNode) {
            this.rightNode = rightNode;
        }
    
        public TreeNode getRightNode() {
            return rightNode;
        }
    }
    

    其中,currentChar字段表示该节点代表的字符,当然,只有叶节点才会有这个字段,chance表示该节点的权重(叶节点的字符的概率)。

    哈夫曼树的构造算法如下:

    1. 由给定的权值构造n棵只有一个根节点、左右子树均为空的二叉树,得到一个二叉树集合
    2. 当集合中的元素大于1时,循环执行:
    	2.1. 选取集合中根节点权值最小的两棵树作为左右子树,权值之和作为父节点的权值构造二叉树
    	2.2. 将这棵树添加进集合,并且删去原来的两棵树
    3. 集合中留下的最后一棵树即为哈夫曼树
    

    代码比较简单:

    private static TreeNode buildHuffmanTree(HashMap<Character, Double> perChance) {
            if(perChance == null) {
                return null;
            }
            ArrayList<TreeNode> treeNodes = new ArrayList<>();
            leafNodes = new HashMap<>();
            for(Map.Entry<Character, Double> entry : perChance.entrySet()) {
                TreeNode tempNode = new TreeNode(entry.getKey(), entry.getValue());
                treeNodes.add(tempNode);
                leafNodes.put(tempNode.getCurrentChar(), tempNode);
            }
            TreeNodeComparator comparator = new TreeNodeComparator();
            while(treeNodes.size() != 1) {
                Collections.sort(treeNodes, comparator);
                TreeNode tempNode1 = treeNodes.remove(0);
                TreeNode tempNode2 = treeNodes.remove(0);
                TreeNode tempTop = new TreeNode(tempNode1.getChance() + tempNode2.getChance());
                tempTop.setLeftNode(tempNode1);
                tempTop.setRightNode(tempNode2);
                tempNode1.setParentNode(tempTop);
                tempNode2.setParentNode(tempTop);
                treeNodes.add(tempTop);
            }
            return treeNodes.get(0);
        }
    

    其中,leafNodes是一个Map,Key为字符,Value是该字符对应的叶节点,便于直接获取哈夫曼树的叶节点而不需要遍历搜索。

    对文本编码

    对文本编码分为两个步骤:获得每个字符对应的编码,对文本进行编码

    获得字符编码

    通过leafNodes,我们可以直接获取到文本中出现过的每一个字符,以及对应的叶节点。从叶节点开始,一层一层向上寻找,直到根节点为止,若该节点为父节点的左节点,则编码字符串后面添一个1,否则添0。最后我们可以得到这个叶节点到根节点的一个01序列。注意,这个序列是叶节点到根节点的路径,而哈夫曼编码是根节点到叶节点的路径,所以得到的字符串还应该倒置一下才是哈夫曼编码。

    HashMap<Character, String> codeMap = new HashMap<>();
    for(Map.Entry<Character, TreeNode> entry : leafNodes.entrySet()) {            		TreeNode tempNode = entry.getValue();
        TreeNode tempHeadNode = null;
        String code = "";
        while(tempNode.getParentNode() != null) {
            tempHeadNode = tempNode.getParentNode();
            if(tempNode.equals(tempHeadNode.getLeftNode())) {
            	code += "0";
            } else {
                code += "1";
            }
            tempNode = tempNode.getParentNode();
         }
         codeMap.put(entry.getValue().getCurrentChar(), new StringBuilder(code).reverse().toString());
    }
    

    对文本编码

    对文本编码就比较容易了,遍历原文本,在codeMap中找到对应字符的01序列即可。

    StringBuilder encraptedContent = new StringBuilder();
    for(int i = 0; i < fileContent.length(); i ++) {
    	encraptedContent.append(codeMap.get(fileContent.charAt(i)));
    }
    binaryNumber = encraptedContent.length();
    encraptedContent = encraptedContent.insert(0, toFullBinaryString(binaryNumber));
    int moreZero = 8 - encraptedContent.length() % 8;
    for(int i = 0; i < moreZero; i ++) {
    	encraptedContent.append("0");
    }
    return encraptedContent.toString();
    

    写入文件

    本来以为是最简单的一部分,没想到确实最让人头疼的一部分。

    也许你已经注意到了,在对文本编码的部分,我将最后的编完码的字符串用0补位,补成8的倍数,就是因为写入的时候,是一个字节一个字节写入的,一个字节是8位。

    而且最重要的问题是,我们不可以使用字符流!试想,如果我们使用字符流,会怎么样呢?

    譬如一个a,在文件中的存储形式是ascii码,也就是0110 0001,一个字节。编码之后,假设是00101,如果按照字符流写入的话,00101还会被转化为ascii码写入,占空间高达5个字节!越压缩越大了。

    所以,我们压缩之后的文件应当是按照字节写入的,同时,每个01应当是一个二进制位。

    Java中有一个基本数据类型byte,对应着存储结构中的一个字节,我们需要改变byte的每一个位,按位或即可。

    譬如,我们需要将一个byte的第1位改为1,我们只需要将这个byte强转为int之后,和0x80(10000000)相与,最后再转为byte即可。

    最后还会遇到一个问题,当我们对01序列凑整的时候(凑整为8的倍数),我们使用的是补0操作,将序列补为8的倍数。可是如果解码的时候,当正常的文本内容读取完成时,会对那些0进行解码,如果恰巧可以解码出字符的话,文本后面就会出现一些奇怪的字符。

    我们处理方式你们可能也注意到了,在对文本编码的时候,我记录了有效的01序列的个数,并将其转化为32位的二进制数,对文本编码时调用的toFullBinaryString()就是将int转化为32位二进制数的。编码时将这个二进制数存在这个密码文件的开头4个字节处,理论上这种方法可以记录有效的2^32 = 4294967296位,也就是42亿多,应该是足够了!

    当然,我们解码的时候也需要这棵哈夫曼树帮助解码,所以我们也需要保存这棵哈夫曼树,这里我只是简单地将这棵树用ObjectOutputStream序列化到一个key文件中了。

    代码如下:

    private static void writeIntoFile(String encraptedContent) {
        if(encraptedContent == null) {
            return;
        }
        char num1 = "1".charAt(0);
        int byteLength = encraptedContent.length() / 8;
        byte[] bytes = new byte[byteLength];
        for(int i = 0; i < byteLength; i ++) {
            bytes[i] = (byte)0;
        }
        for(int i = 0; i < encraptedContent.length(); i ++) {
            char tempBinary = encraptedContent.charAt(i);
            if(tempBinary == num1) {
                switch(i % 8) {
                    case 0: bytes[i/8] = (byte)((int)bytes[i/8] | 0x80);break;
                    case 1: bytes[i/8] = (byte)((int)bytes[i/8] | 0x40);break;
                    case 2: bytes[i/8] = (byte)((int)bytes[i/8] | 0x20);break;
                    case 3: bytes[i/8] = (byte)((int)bytes[i/8] | 0x10);break;
                    case 4: bytes[i/8] = (byte)((int)bytes[i/8] | 0x8);break;
                    case 5: bytes[i/8] = (byte)((int)bytes[i/8] | 0x4);break;
                    case 6: bytes[i/8] = (byte)((int)bytes[i/8] | 0x2);break;
                    case 7: bytes[i/8] = (byte)((int)bytes[i/8] | 0x1);break;
                }
            }
        }
        File encrapyFile = new File(file.getName().split("\\.")[0] + ".encrapy");
        File keyFile = new File(file.getName().split("\\.")[0] + ".key");
        try{
            FileOutputStream outputStream = new FileOutputStream(encrapyFile);
            outputStream.write(bytes);
            outputStream.flush();
            outputStream.close();
            ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream(keyFile));
            objectOutputStream.writeObject(topNode);
            objectOutputStream.close();
        }catch(Exception e) {
            System.out.println("加密后文件写入失败!");
        }
        System.out.println("\n密码文件为 " + encrapyFile.getName() + "\nKey文件为 " + keyFile.getName());
        System.out.println("压缩前文件大小 " + file.length() + " Byte\n压缩后文件大小 " + encrapyFile.length() + " Byte");
        System.out.printf("压缩率:%.2f%%\n", (((float)file.length() - (float)encrapyFile.length()) / (float)file.length()) * 100);
    }
    

    效果

    GuodeMacBook-Air:HuffmanHomework guoziyang$ javaHuffmanHomework
    
    
    1. 原始文件压缩
    2. 压缩文件解码
    3. 退出
    请输入选择:1
    
    
    请输入加密的文件路径:example4.txt
    
    密码文件为 example4.encrapy
    Key文件为 example4.key
    压缩前文件大小 1015585 Byte
    压缩后文件大小 564063 Byte
    压缩率:44.46%
    

    解码

    解码的方式也是比较简单的,读入密码文件,转化为二进制字符串,读入key文件,转化为哈夫曼树,根据序列查找字符就行了。

    读入文件

    读入key文件很简单,也就是用ObjectInputStream读进来就好了。

    主要是读入密码文件以及处理。

    读入的时候我们当然不可以用字符流,否则将会把01序列认作ascii码序列转化为字符,我们需要的是原始的01序列。所以我们选择字节流。

    同时我们还需要一个类,ByteArrayOutputStream,这个类内部有一个缓冲区,可以使用toByteArray()方法将缓冲区内部的所有byte转化为一个byte数组。

    InputStream inputStream = new FileInputStream(encrapyFileName);
    ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
    byte[] buffer = new byte[1024 * 4];
    int n = 0;
    while((n = inputStream.read(buffer)) != -1) {
        byteArrayOutputStream.write(buffer, 0, n);
    }
    bytes = byteArrayOutputStream.toByteArray();
    

    循环读到的字节直接写到ByteArrayOutputStream里,最后toByteArray()即可。

    现在我们拿到了代表密码内容的字节数组,转化为二进制String的方法如下:

    StringBuilder builder = new StringBuilder();
    for(byte tempByte : bytes) {
        builder.append(Integer.toBinaryString((tempByte & 0xFF) + 0x100).substring(1));
    }
    return builder.toString();
    

    我主要解释下Integer.toBinaryString((tempByte & 0xFF) + 0x100).substring(1))的作用。

    这条语句将byte转化为对应的二进制串。当一个byte类型直接转化为int时,JVM会对它进行补位操作,将8位补为32位。譬如,byte存储的是10000001,转为int之后1111111111111111111111111 10000001(32位),很显然这两个补码保存的十进制数字依旧是相同的。可是问题在于,我们做byte -> int的转化,并不是为了保持十进制的一致性,而是为了拿到其二进制补码,所以我们使用0xFF与这个byte相与,保证前24位依旧是0。将这个码加上0x100(100000000)将第9位置为1,这样即使前几位为0的话也可以不被舍掉,最后使用substring(1)将第九位上的1去掉即可。

    按照哈夫曼树解码

    我们拿到了原始的二进制字串和哈夫曼树,只需要解码就完事了。

    解码算法如下:

    1. 将指针置于哈夫曼树的头节点
    2. 依次读入二进制码
    	2.1 如果读入0,则指针指向当前节点的左支,否则指向右支
    	2.2 判断当前节点是否是叶节点,如果是则将该节点的字符输出并将指针置于头节点
    	2.3 继续循环
    

    由此即可输出原文本内容,注意我们在编码的时候把一个四字节32位的二进制数存在文件头,应当首先读出,以确认有效的二进制码位数。

    代码如下:

    StringBuilder resultBuilder = new StringBuilder();
    binaryNumber = binaryToTen(encraptedContent.substring(0, 32));
    encraptedContent = encraptedContent.substring(32);
    TreeNode tempNode = topNode;
    for(int i = 0; i < binaryNumber; i ++) {
        if(encraptedContent.charAt(i) == '0') {
                tempNode = tempNode.getLeftNode();
        } else {
            tempNode = tempNode.getRightNode();
        }
        if(tempNode.getCurrentChar() != null) {
            resultBuilder.append(tempNode.getCurrentChar());
            tempNode = topNode;
        }
    }
    return resultBuilder.toString()
    

    完整代码

    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.ByteArrayOutputStream;
    import java.io.DataOutputStream;
    import java.io.FileReader;
    import java.io.FileWriter;
    import java.io.IOException;
    import java.io.InputStream;
    import java.io.ObjectInputStream;
    import java.io.ObjectOutputStream;
    import java.io.FileOutputStream;
    import java.io.Serializable;
    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    import java.util.Collections;
    import java.io.File;
    import java.io.FileInputStream;
    
    public class HuffmanHomework {
        private static Scanner scanner = new Scanner(System.in);
        private static HashMap<Character, TreeNode> leafNodes = null;
        private static TreeNode topNode = null;
        private static File file = null;
        private static int binaryNumber = 0;
    
        public static void main(String[] args) {
            while(true) {
                menu();
            }
        }
    
        private static void menu() {
            System.out.println();
            System.out.println();
            System.out.println("1. 原始文件压缩");
            System.out.println("2. 压缩文件解码");
            System.out.println("3. 退出");
            System.out.print("请输入选择:");
            int choice = scanner.nextInt();
            if(choice != 1 && choice != 2 && choice != 3) {
                System.out.println("输入有误,请重新选择!");
                System.out.println();
                System.out.println();
                return;
            }
            System.out.println();
            System.out.println();
            switch(choice) {
                case 1:
                    encrapt();
                    break;
                case 2:
                    decrapt();
                    break;
                case 3:
                    System.exit(0);
            }
        }
    
        private static void encrapt() {
            String fileContent = readFromFile();
            HashMap<Character, Double> perChance =  calculateCharChance(fileContent);
            topNode = buildHuffmanTree(perChance);
            String encraptedContent = encraptContent(fileContent);
            writeIntoFile(encraptedContent);
        }
    
        private static String readFromFile() {
            System.out.print("请输入加密的文件路径:");
            scanner = new Scanner(System.in);
            String fileName = scanner.nextLine();
            file = new File(fileName);
            try{
                BufferedReader reader = new BufferedReader(new FileReader(file));
                StringBuilder fileContentBuilder = new StringBuilder();
                String tempString = null;
                while((tempString = reader.readLine()) != null) {
                    fileContentBuilder.append(tempString);
                    fileContentBuilder.append("\n");
                }
                reader.close();
                return fileContentBuilder.toString();
            }catch(IOException exception) {
                System.out.println("读入文件失败!请检查文件路径!");
                return null;
            }
        }
    
        private static HashMap<Character, Double> calculateCharChance(String fileContent) {
            if(fileContent == null) {
                return null;
            }
            HashMap<Character, Double> charTimes = new HashMap<>();
            for(int i = 0; i < fileContent.length(); i ++) {
                char tempChar = fileContent.charAt(i);
                if(charTimes.containsKey(tempChar)) {
                    charTimes.put(tempChar, charTimes.get(tempChar) + 1d);
                } else {
                    charTimes.put(tempChar, 1d);
                }
            }
            HashMap<Character, Double> perChance = new HashMap<>();
            for(Map.Entry<Character, Double> entry : charTimes.entrySet()) {
                perChance.put(entry.getKey(), entry.getValue() / fileContent.length());
            }
            return perChance;
        }
    
        private static TreeNode buildHuffmanTree(HashMap<Character, Double> perChance) {
            if(perChance == null) {
                return null;
            }
            ArrayList<TreeNode> treeNodes = new ArrayList<>();
            leafNodes = new HashMap<>();
            for(Map.Entry<Character, Double> entry : perChance.entrySet()) {
                TreeNode tempNode = new TreeNode(entry.getKey(), entry.getValue());
                treeNodes.add(tempNode);
                leafNodes.put(tempNode.getCurrentChar(), tempNode);
            }
            TreeNodeComparator comparator = new TreeNodeComparator();
            while(treeNodes.size() != 1) {
                Collections.sort(treeNodes, comparator);
                TreeNode tempNode1 = treeNodes.remove(0);
                TreeNode tempNode2 = treeNodes.remove(0);
                TreeNode tempTop = new TreeNode(tempNode1.getChance() + tempNode2.getChance());
                tempTop.setLeftNode(tempNode1);
                tempTop.setRightNode(tempNode2);
                tempNode1.setParentNode(tempTop);
                tempNode2.setParentNode(tempTop);
                treeNodes.add(tempTop);
            }
            return treeNodes.get(0);
        }
    
        private static String encraptContent(String fileContent) {
            if(fileContent == null) {
                return null;
            }
            HashMap<Character, String> codeMap = new HashMap<>();
            for(Map.Entry<Character, TreeNode> entry : leafNodes.entrySet()) {
                TreeNode tempNode = entry.getValue();
                TreeNode tempHeadNode = null;
                String code = "";
                while(tempNode.getParentNode() != null) {
                    tempHeadNode = tempNode.getParentNode();
                    if(tempNode.equals(tempHeadNode.getLeftNode())) {
                        code += "0";
                    } else {
                        code += "1";
                    }
                    tempNode = tempNode.getParentNode();
                }
                codeMap.put(entry.getValue().getCurrentChar(), new StringBuilder(code).reverse().toString());
            }
            StringBuilder encraptedContent = new StringBuilder();
            for(int i = 0; i < fileContent.length(); i ++) {
                encraptedContent.append(codeMap.get(fileContent.charAt(i)));
            }
            binaryNumber = encraptedContent.length();
            encraptedContent = encraptedContent.insert(0, toFullBinaryString(binaryNumber));
            int moreZero = 8 - encraptedContent.length() % 8;
            for(int i = 0; i < moreZero; i ++) {
                encraptedContent.append("0");
            }
            return encraptedContent.toString();
        }
    
        public static String toFullBinaryString(int num) {
            char[] chs = new char[Integer.SIZE];
            for (int i = 0; i < Integer.SIZE; i++) {
                chs[Integer.SIZE - 1 - i] = (char) (((num >> i) & 1) + '0');
            }
            return new String(chs);
        }
    
        private static void writeIntoFile(String encraptedContent) {
            if(encraptedContent == null) {
                return;
            }
            char num1 = "1".charAt(0);
            int byteLength = encraptedContent.length() / 8;
            byte[] bytes = new byte[byteLength];
            for(int i = 0; i < byteLength; i ++) {
                bytes[i] = (byte)0;
            }
            for(int i = 0; i < encraptedContent.length(); i ++) {
                char tempBinary = encraptedContent.charAt(i);
                if(tempBinary == num1) {
                    switch(i % 8) {
                        case 0: bytes[i/8] = (byte)((int)bytes[i/8] | 0x80);break;
                        case 1: bytes[i/8] = (byte)((int)bytes[i/8] | 0x40);break;
                        case 2: bytes[i/8] = (byte)((int)bytes[i/8] | 0x20);break;
                        case 3: bytes[i/8] = (byte)((int)bytes[i/8] | 0x10);break;
                        case 4: bytes[i/8] = (byte)((int)bytes[i/8] | 0x8);break;
                        case 5: bytes[i/8] = (byte)((int)bytes[i/8] | 0x4);break;
                        case 6: bytes[i/8] = (byte)((int)bytes[i/8] | 0x2);break;
                        case 7: bytes[i/8] = (byte)((int)bytes[i/8] | 0x1);break;
                    }
                }
            }
            File encrapyFile = new File(file.getName().split("\\.")[0] + ".encrapy");
            File keyFile = new File(file.getName().split("\\.")[0] + ".key");
            try{
                FileOutputStream outputStream = new FileOutputStream(encrapyFile);
                outputStream.write(bytes);
                outputStream.flush();
                outputStream.close();
                ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream(keyFile));
                objectOutputStream.writeObject(topNode);
                objectOutputStream.close();
            }catch(Exception e) {
                System.out.println("加密后文件写入失败!");
            }
            System.out.println("\n密码文件为 " + encrapyFile.getName() + "\nKey文件为 " + keyFile.getName());
            System.out.println("压缩前文件大小 " + file.length() + " Byte\n压缩后文件大小 " + encrapyFile.length() + " Byte");
            System.out.printf("压缩率:%.2f%%\n", (((float)file.length() - (float)encrapyFile.length()) / (float)file.length()) * 100);
        }
    
        private static void decrapt() {
            String encraptedContent = readEncraptedContent();
            readKeyFile();
            decraptContent(encraptedContent);
        }
    
        private static String readEncraptedContent() {
            scanner = new Scanner(System.in);
            System.out.print("请输入密码文件路径:");
            String encrapyFileName = scanner.nextLine();
            byte[] bytes = null;
            try{
                InputStream inputStream = new FileInputStream(encrapyFileName);
                ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
                byte[] buffer = new byte[1024 * 4];
                int n = 0;
                while((n = inputStream.read(buffer)) != -1) {
                    byteArrayOutputStream.write(buffer, 0, n);
                }
                bytes = byteArrayOutputStream.toByteArray();
                byteArrayOutputStream.close();
                inputStream.close();
            }catch(IOException e) {
                System.out.println("读入密码文件失败!请检查文件路径!");
                return null;
            }
            StringBuilder builder = new StringBuilder();
            for(byte tempByte : bytes) {
                builder.append(Integer.toBinaryString((tempByte & 0xFF) + 0x100).substring(1));
            }
            return builder.toString();
        }
    
        private static void readKeyFile() {
            scanner = new Scanner(System.in);
            System.out.print("请输入Key文件路径:");
            String keyFileName = scanner.nextLine();
            try{
                ObjectInputStream objectInputStream = new ObjectInputStream(new FileInputStream(keyFileName));
                topNode = (TreeNode)objectInputStream.readObject();
                objectInputStream.close();
            }catch(Exception e) {
                System.out.println("读入Key文件失败!请检查文件路径!");
                topNode = null;
                return;
            }
        }
    
        private static void decraptContent(String encraptedContent) {
            if(encraptedContent == null) {
                return;
            }
            StringBuilder resultBuilder = new StringBuilder();
            binaryNumber = binaryToTen(encraptedContent.substring(0, 32));
            encraptedContent = encraptedContent.substring(32);
            TreeNode tempNode = topNode;
            for(int i = 0; i < binaryNumber; i ++) {
                if(encraptedContent.charAt(i) == '0') {
                    tempNode = tempNode.getLeftNode();
                } else {
                    tempNode = tempNode.getRightNode();
                }
                if(tempNode.getCurrentChar() != null) {
                    resultBuilder.append(tempNode.getCurrentChar());
                    tempNode = topNode;
                }
            }
            System.out.print("解密完成,是否输出(y or n)?");
            String choice = scanner.next();
            if("y".equals(choice)) {
                System.out.println("\n\n" + resultBuilder.toString());
            }
            System.out.print("是否写入文件(y or n)?");
            choice = scanner.next();
            if("y".equals(choice)) {
                System.out.print("请输入待写入文件路径:");
                scanner = new Scanner(System.in);
                String resultFileName = scanner.nextLine();
                try{
                    BufferedWriter writer = new BufferedWriter(new FileWriter(resultFileName));
                    writer.write(resultBuilder.toString());
                    writer.close();
                }catch(Exception e) {
                    System.out.println("写入结果文件失败!请检查文件路径!");
                }
            }
        }
    
        private static int binaryToTen(String binary) {
            int res = 0;
            for(int i = 0; i < 32; i ++) {
                if(binary.charAt(i) == '1') {
                    res += Math.pow(2, 31 - i);
                }
            }
            return res;
        }
    }
    
    class TreeNodeComparator implements Comparator<TreeNode> {
        @Override
        public int compare(TreeNode node1, TreeNode node2) {
            return node1.getChance() > node2.getChance() ? 1 : -1;
        }
    }
    
    class TreeNode implements Serializable{
        private static final long serialVersionUID = 1L;
    
        private Character currentChar = null;
        private Double chance;
        private TreeNode parentNode;
        private TreeNode leftNode;
        private TreeNode rightNode;
    
        public TreeNode(char currentChar, double chance) {
            this.currentChar = currentChar;
            this.chance = chance;
        }
    
        public TreeNode(double chance) {
            this.chance = chance;
        }
    
        public Character getCurrentChar() {
            return currentChar;
        }
    
        public Double getChance() {
            return chance;
        }
    
        public void setParentNode(TreeNode parentNode) {
            this.parentNode = parentNode;
        }
    
        public TreeNode getParentNode() {
            return parentNode;
        }
    
        public void setLeftNode(TreeNode leftNode) {
            this.leftNode = leftNode;
        }
    
        public TreeNode getLeftNode() {
            return leftNode;
        }
    
        public void setRightNode(TreeNode rightNode) {
            this.rightNode = rightNode;
        }
    
        public TreeNode getRightNode() {
            return rightNode;
        }
    }
    
    展开全文
  • 「一本正经的聊数据结构(5):二叉树的存储结构与遍历」 基础知识 感谢某位在后台留言的同学,让我想起来我还有这个没写完的系列。 在最开始,先了解几个基础概念: 路径:在一棵树中,一个结点到另一个结点之间的...
  • 树的存储结构 有三种表示法,分别是 双亲表示法: 每个结点(根结点外)除了数据域还有一个指针域储存其双亲结点的位置。 孩子表示法: 每个结点除了数据域还有多个指针域存放其子树根结点的位置 孩子兄弟法: ...
  • 的存储结构: 孩子链表表示法: 主体为一个数组元素个数和树中结点个数相同的一维数组。树上的一个结点x以及该结点的所有孩子结点组成一个带头结点的单链表,单链表的头结点含有两个域:数据域和指针域。 其中数据...
  • 在编程表示的是一种由N个节点的有限集合而构成的存储结构,它有且仅有一个"根"节点(没有父节点),其余节点形成的(互不相交)称为"根"节点的子树 2、的结构图 如上图所示,A是这棵的"根"节点,A节点有...
  • 1.线索二叉树 上一篇二叉树,我们介绍了基本的二叉树的结构。...如此一来,在遍历的过程,我们便可以直接通过左右子节点,找到叶子节点的前驱和后驱,使用一条线完整的将整刻串起来。 ...
  • 二叉树的顺序存储结构一般仅仅存储完全二叉树,否则的话会浪费大量空间 Realease为私有,只能被本类使用 为了建立一个二叉树,将二叉树每个节点的空指针引出一个虚节点,其值为一特定值#,以标识其为空,把这样...
  • 数据结构关于二叉树建立遍历以及应用二叉树进行编解码 实验要求 必做部分 1. 小明会按照前序方式输入一棵二叉树。例如,输入$ACG##H##D##BE#I##F##话,代表了下面这棵: 2. 请分别按照前序、中序、后序...
  • 对于具有n个节点的二叉树,采用二叉链存储结构时,指针域共有2n个,由于只有n-1个节点被有效指针所指向,则共有n+1个空链域。 遍历二叉树的结果是一个节点的线性序列。可以利用这些空链域存放指向节点的前驱和后...
  • 线索二叉树的思想来源于二叉树的存储结构中,存在一些空的指针域,因此是否能够将这些空间利用起来,存储一些关于节点间先后顺序的信息,由此产生了线索二叉树。线索二叉树,线索反映前驱、后继的关系,而指针则...
  • 节点的路径长度为从该节点到树根之间的路径长度与该节点权(比如字符在某串的使用频率)的乘积。 比如有一串字符串如:3334444555556666667777777,它是由3、4、5、6、7这五个数字组成的,现要使用一种编码...
  • ){ //初始化用于存储哈夫曼树的数组  h[i].ch=0;  h[i].lchild=-1;  h[i].parent=-1;  h[i].rchild=-1;  h[i].weight=0;  }  for(i=0;i&...
  • 哈夫曼树的存储及生成算法。 程序代码: #include #include #define N 50 //叶子结点数 #define M 2*N-1 //树中结点总数 //哈夫曼树节点结构类型 typedef struct { char data; //结点值 double ...
  • NOJ-哈夫曼编/译码器-西工大数据结构

    千次阅读 多人点赞 2018-04-19 16:47:48
     构建哈夫曼树,就是取所有数据权重最小的两个,组成一个小树,这个小树的权重就是这两个数据权重之和,然后反复进行这个操作(已成为叶节点的数据不再进行权重比较),就可以得到一课哈夫曼书。这里并没有用二叉...
  • 树的基本概念

    2017-09-06 16:10:32
    树是一种数据结构,表示n个节点的组织方式就像一颗树,...深度表示树中节点最大的层次。 很多不想交的树构成森林 常见的树有:二叉树,完全二叉树,满二叉树,哈夫曼树。 树的存储结构 一般树的存储是把顺序存储
  • 本设计采用二叉链表的存储结构,建立哈夫曼树;用递归调用的方式对哈夫曼树节点进行编码,生成与字符对应的哈夫曼编码。本设计完全采用C语言进行编程,并在VC++编译器上调试运行通过。本程序使用中文界面,并有...
  • Huffman树的存储结构:结构数组。Huffman树形成的关键:如何在一堆带权节点中每次选取两个权值最小的节点。1.哈夫曼树哈夫曼树又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树,带权路径长度 WPL 最小的...
  • 哈夫曼树由HuffmanTreeNode构成,每个结点包括结点权值,父节点指针域,左右孩子指针域,和存编码code属性。然后把这些结点通过链表按二叉树关系一个个存储到链表。 主要操作设计 DataNode类:用来存储字符...
  • 的存储结构;森林与二叉树的转换;树和森林的遍历 树与二叉树的应用 二叉排序树;平衡二叉树;哈夫曼树和哈弗编码 三、树的基本概念 1、树的定义 树是n(n>=0)个结点的有限集。当n = 0时,称为空树。在...
  • 数据结构之哈弗曼

    2013-06-25 22:00:51
    1.基本概念: 哈夫曼树即最优二叉树,是只有叶节点才能存放数据,且使所有数据到根节点的距离与其权值乘积和最小的二叉树。 2.建立哈夫曼树的步骤: 1.从所有数据找到权值最小的两个数据A和B,把A和B作为两...
  • typedef struct //huffman树存储结构 { unsigned int weight;//权值字符出现频率 int lchild,rchild,parent; }huftree; void select(huftree tree[],int k) //找寻parent为0,权最小两个节点 { int i; for ...

空空如也

空空如也

1 2 3 4
收藏数 70
精华内容 28
关键字:

哈夫曼树中节点的存储结构