树
第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表的形式来实现了一个结点指向另外一个结点。
投递金蝶等公司10个岗位
小天才HR面6人在聊