离散数学 --- 根树，根数的遍历，最优树和哈夫曼算法

第一部分 --- 根树

1.由于内点和根都可以进行分支，所以又称它们为分支点

1.根在上，叶在下，默认方向向下 ---- 以此得到简化图

1.成为祖先的要求是可达，而成为父亲的要求是两结点之间具有一条有向边

 1.成为有序树的前提树的是每一层上的结点之间都被排好顺序

 

 

1.方案1在能够进行多线程操作的多核计算机中好用，只需要两次加法的时间就能够得出结果；而方案2则更适合在单核计算机中使用，需要四次加法的时间

---

第二部分 --- 根树的遍历

 

 

 

1.先根：先访问根，然后访问左右子树

2.中根：先访问左子树，然后访问根，然后再访问右子树

3.后根：先访问左右子树，然后再访问根

1.使用中缀形式的时候要给遍历到的左右子树分别加括号

1.通过先根形式遍历到的结果都被按照顺序放入到了栈中，读取的时候以出栈的方式读取

2.当读取到一个运算符的时候就将在这个运算符前面的两个数中的左边那个数作为运算符的左值，右边那个数作为运算符的右值进行计算，然后将计算完后的值入栈，同时将出栈元素中我们没有用到的那个元素跟在后面入栈入栈，接着再继续出栈和计算

后缀形式与前缀形式相同，唯一的区别就是方向反了

 

1.关于根树的遍历我们常用的是先根遍历和后根遍历，中根遍历比较少用

---

第三部分 --- 最优树和哈夫曼算法

 

 要注意前缀码是一个集合

 上面右边那个010改为011 

给定所有叶的权值集合，我们该如何根据这个集合生成最优树呢？

在这里我们使用的是哈夫曼算法

通过哈夫曼算法我们可以保证权值越小的叶越处于生成树的高层，权值越大的叶越处于生成树的低层，此时树的求权公式有最小值，这样就能够得到一个理想的最优树了

 

我们一般规定左边为0，右边为1

1.我们一般认为叶子的权是叶的被访问频率，叶子的访问路径是对应的树的层数，访问频率乘以访问路径长度我们得到的是这个叶子的访问路径长度在总路径中占的实际份量，如果访问速度一样，加权后的实际访问路径越大，访问时间越长

2.最优树可以理解为加权后总访问路径最短的树，在同样的时间下所需的时间最短