树

第1节 二叉树

二叉树的重要性质：1）二叉树的叶子结点个数=度为2的结点个数+1为什么呢？假设一个有两个子树的根结点：如果子树的孩子的度为1或者度为0，那么都只产生两个叶子结点，叶子结点个数等于度为2的结点+1。如果子树的孩子的度全为2，那么产生的叶子结点个数等于度为2的结点个数+1。综上，再加上根结点，那么可以推出性质1。由于度为1的结点只产生一个叶子结点，所以度为1的结点根本不影响叶子结点的个数。所以，只有度为2的结点影响叶子结点数目。这样，实际上任意一棵二叉树的叶子结点数量等于相同条件（相同条件指的是度为2的结点数目相同）下的完全二叉树的叶子结点的数量。其实我们可以尝试一下，给出一棵二叉树，在不改变叶子结点数目的情况下，去掉所有度为1的结点，这样就可以得出以上的结论。

二叉树的顺序存储结构

对于完全二叉树，可以将其所有的结点按照层序遍历的方式编号，然后每个结点都可以用一个数组元素来表示。这样就将一棵完全二叉树用数组来表示了。

#define MAXSIZE 100 // 二叉树的最大结点数目
typedef int SqBiTree[MAXSIZE]; //0号单元存储根结点
SqBiTree bt; //定义一棵二叉树

二叉树的链式存储结构

typedef struct BiTNode
{
    int data;
    struct BiTNode *left;
    struct BiTNode *right;
}BiTNode,*BiTree;

第2节 二叉树算法

先序遍历二叉树

中序遍历二叉树

后续遍历二叉树

层序遍历二叉树

第3节 线索二叉树（未完成）

当以先序、中序或者后续遍历二叉树时，实际上就是对非线性结构进行线性化操作。这样，二叉树中的每个结点就有前驱结点和后续结点。但是以二叉链表的形式作为存储结构时，只能知道每个结点的左、右孩子信息，而不能得到前驱结点与后继结点信息（除非先遍历二叉树）。现在，我们在二叉树的每个结点中记录该结点的前驱结点与后续结点，这样含有前驱结点与后继结点信息的二叉树叫做线索二叉树。

根据遍历的先后顺序，二叉树可以分为先序线索二叉树、中序线索二叉树和后续线索二叉树。

第4节 哈夫曼树

重要概念：1）路径长度：从一个结点到另外一个结点的路径中间的长度2）权：赋予实体的权重属性。分为结点权和边权。3）树的带权路径长度：所有叶子结点到根结点的路径长度与该叶子结点的权的乘积之和。

哈夫曼树就是带权路径长度最小的树。哈夫曼树又称最优树。

哈夫曼树构造方法：1）构造森林全是根2）选用两小造新树3）删除两小添新树4）重复2，3只剩根（只剩一棵树）

哈夫曼树的结点总数：哈夫曼树中没有度为1的结点，n个叶子结点，n-1个度为2的结点，因此共有2n-1个结点。

哈夫曼树的作用：用于哈夫曼编码，压缩文件大小。

哈夫曼编码的两个问题：1）为什么哈夫曼编码能够保证是前缀码？前缀码是指任意一个字符的编码都不是其它任意字符编码的前缀，这样就保证不等长编码进行解码时不会产生冲突。而哈夫曼树的每个字符用叶子结点来表示，而每个叶子结点必然不会是其它叶子结点的祖先，因此不会有字符的编码是其它字符的前缀。2）为什么哈夫曼编码能够保证字符编码总长度最小？哈夫曼树的带权路径长度最短，哈夫曼编码能够让出现概率大的字符的编码长度最小，因此字符长度编码最短。

哈夫曼树的存储结构

//哈夫曼树结点结构
typedef struct {
    int weight;//结点权重
    int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
}HTNode, *HuffmanTree;

哈夫曼树的构造实现

算法实现：实现过程就相当于填写一个数组，通过哈夫曼树的构造方法很容易写出代码。参考严蔚敏《数据结构与算法》

//构造哈夫曼树 H
void ( CreateHuffmanTree (HuffmanTree &HT,int n)
{
    if(n<=1) 
    {
        return; 
    }
    //下面进行初始化工作
    int m=2*n-1;
    HT=new HTNode[m+1]; //0 号单元未用,所以需要动态分配m+1个单元,在最开始HT[m]都表示根结点
    for(i=1;1<=m;++i) //将 1~m 号单元中的双亲、左孩子,右孩子的下标都初始化为0
    {
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    for(i=1;1<=n;i++) //输人前n个单元中叶子结点的权值 
    {
        cin>>HT[i].weight; 
    }
    //经过以上，初始化成功，下面开始构造哈夫曼树

    //通过 n-1 次的选择、删除、合并来创建哈夫曼树
    for(i=n+1;1<=m;i++)
    {
        //在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,并返回它们在HT中的序号s1和s2
        //i-1表示挑选范围在1到i-1之间
        Select(HT,i-1, s1, s2);
        //得到新结点 i,从森林中删除 s1,s2,将s1和 s2 的双亲域由0改为i 
        HT[s1].parent=i;
        HT[s2].parent=i; 
        //i的权值为左右孩子权值之和 
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
}

第5节 二叉搜索树

第6节 平衡二叉树（AVL树）

第7节 前缀树

前缀树以边来代表字符，而不是以结点来代替字符，这样的优势是什么？一个结点代表什么字符是由什么来决定的？由它的父节点的下标来决定。

public static class TrieNode
{
    public int pass;
    public int end;
    public TrieNode[] nexts;

    public TriNode()
    {
        pass=0;
        end=0;
        nexts=new TrieNode[26]; //当字符种类不固定时，也可以使用hash表 HashMap<Char,Node> nexts;
    }
}

public static class Trie
{
    private TrieNode root;

    public Trie()
    {
        root =new TriNode();
    }

    // 在字典树中插入新的单词
    public void insert(String word)
    {
        if(word==null)
        {
            return;
        }
        char[] chs=word.toCharArray();
        TrieNode node=root;
        nod.pass++;
        int index=0;
        for(int i=0;i<chs.length;i++)
        {
            index=chs[i]-'a';
            if(node.nexts[index]==null)
            {
                node.nexts[index]=new TrieNode();
            }
            node=node.nexts[index];
            node.pass++;
        }
        node.end++;
    }

    // 查询word这个单词之前加过几次
    public int search(String word)
    {
        if(word==null)
        {
            return 0;
        }
        char[] chs=word.toCharArray();
        TriNode node=root;
        int index=0;
        for(int i=0;i<chs.length;i++)
        {
            index=chs[i]-'a';
            if(node.nexts[index]==null)
            {
                return 0;
            }
            node=node.nexts[index];
        }
        return node.end;
    }
    
    // 删除字典树中的单词
    public void delete(String word)
    {
        if(search(word)!=0)
        {
            char[] chs=word.toCharArray();
            TrieNode mode=root;
            node.pass--;
            int index=0;
            for(int i=0;i<chs.length;i++)
            {
                index=chs[i]-'a';
                if(--node.nexts[index].pass==0)
                {
                    // java代码可以这样写 c++代码要遍历到底去析构，释放内存
                    node.nexts[index]==null;
                    return;
                }
                node=node.nexts[index];
            }
            node.end--;
        }
    }

}

第8节 并查集

一个矩阵中只有0和1两种值, 每个位置都可以和自己的上、下、左、右 四个位置相连,如 果有一片1连在一起,这个部分叫做一个岛,求一个矩阵中有多少个岛?【举例】001010111010100100000000这个矩阵中有三个岛

如何设计一个并行算法来解决这个问题？

// 样本进来都会包一层，叫做元素。这是为什么？这似乎是没有必要的
public static class Element<V>
{
    public V value;

    public Element(V value)
    {
        this.value=value;
    }
}

public static class UnionFindSet<V>
{
    public HashMap<V,Element<V>> elementMap;
    // key——某个元素 value——该元素的父亲
    public HashMap<Element<V>,Element<V>> fatherMap;
    // key某个集合的代表元素 value-该集合的大小
    public HashMap<Element<V>,Integer> sizeMap;

    public UnionFindset(List<V> list)
    {
        elementMap=new HashMap<>();
        fatherMap=new HashMap<>();
        sizeMap=new HashMap<>();
        for(V value:list)
        {
            Element<V> element=new Element<V>(value);
            elementMap.put(value,element);
            fatherMap.put(element,element);
            sizeMap.put(element,1);
        }
    }

    // 查找两个元素是否属于同一个集合
    public boolean isSameSet(V a,V b)
    {
        if(elementMap.containsKey(a)&&elementMap.containsKey(b))
        {
            return findHead(elementMap.get(a)==elementMap.get(b));
        }
        return false;
    }

    // 查找一个元素所在集合的代表元素
    private Element<V> findHead(Element<V> element)
    {
        Stack<Element<V>> path=new Stack();
        while(element!=fatherMap.get(element))
        {
            path.push(element);
            element=fatherMap.get(element);
        }
        while(!path.isEmpty())
        {
            fatherMap.put(path.pop(),element);
        }
        return element;
    }

    // 合并两个集合
    public void union(V a, V b) 
    { 
        if (elementMap.containsKey(a) && elementMap.containsKey(b)) 
        { 
            Element<V> aF = findHead(elementMap.get(a)); 
            Element<V> bF = findHead(elementMap.get(b)); 
            if (aF != bF)
            { 
                Element<V> big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF; 
                Element<V> small = big == aF ? bF :aF?
                fatherMap.put(small, big); 
                sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF)); 
                sizeMap.remove( small); 
            }
        }
    }

}

用链表的方式来实现并查集似乎也是可行的。在上面的代码中，通过Hash表的形式来实现了一个结点指向另外一个结点。