binarytree.cs

PDF文件格式解析库源代码

using System;
using System.Collections.Generic;
using System.Text;

namespace QiHe.CodeLib.Compress
{
    public class BinaryTree
    {
        public BinaryTreeNode Root;

        public BinaryTree(BinaryTreeNode root)
        {
            Root = root;
        }

        public List<Pair<int, string>> GetSymbolCodePairs(bool sort)
        {
            List<Pair<int, string>> symbolCodes = new List<Pair<int, string>>(ListSymbolCodes(Root, null));
            if (sort)
            {
                symbolCodes.Sort(delegate(Pair<int, string> pair1, Pair<int, string> pair2)
                {
                    return pair1.Left - pair2.Left;
                });
            }
            return symbolCodes;
        }

        private IEnumerable<Pair<int, string>> ListSymbolCodes(BinaryTreeNode node, string code)
        {
            if (node is BinaryTreeLeafNode)
            {
                yield return new Pair<int, string>(((BinaryTreeLeafNode)node).Symbol, code);
            }
            else if (node is BinaryTreeInternalNode)
            {
                BinaryTreeInternalNode interNode = node as BinaryTreeInternalNode;
                for (int i = 0; i < interNode.ChildNodes.Length; i++)
                {
                    foreach (Pair<int, string> pair in ListSymbolCodes(interNode.ChildNodes[i], code + i))
                    {
                        yield return pair;
                    }
                }
            }
            else
            {
                //do nothing
            }
        }

        public IEnumerable<Pair<int, int>> GetSymbolCodeLengths()
        {
            return ListSymbolCodeLengths(Root, 0);
        }

        private IEnumerable<Pair<int, int>> ListSymbolCodeLengths(BinaryTreeNode node, int codeLength)
        {
            if (node is BinaryTreeLeafNode)
            {
                yield return new Pair<int, int>(((BinaryTreeLeafNode)node).Symbol, codeLength);
            }
            else if (node is BinaryTreeInternalNode)
            {
                BinaryTreeInternalNode interNode = node as BinaryTreeInternalNode;
                for (int i = 0; i < interNode.ChildNodes.Length; i++)
                {
                    foreach (Pair<int, int> pair in ListSymbolCodeLengths(interNode.ChildNodes[i], codeLength + 1))
                    {
                        yield return pair;
                    }
                }
            }
            else
            {
                //do nothing
            }
        }
    }

    public abstract class BinaryTreeNode { }

    public class BinaryTreeInternalNode : BinaryTreeNode
    {
        public BinaryTreeNode[] ChildNodes = new BinaryTreeNode[2];
    }

    public class BinaryTreeLeafNode : BinaryTreeNode
    {
        public int Symbol;

        public BinaryTreeLeafNode(int symbol)
        {
            Symbol = symbol;
        }
    }
}