第二次讨论课总结报告
知识点：
树的概念:
树是有根结点和若干颗子树构成的。

树是由一个集合以及在该集合上定义的一种关系构成的。

集合中的元素称为树的结点，所定义的关系称为父子关系。

父子关系在树的结点之间建立了一个层次结构。

在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

二叉树:
二叉树是一个连通的无环图，并且每一个顶点的度不大于3。

有根二叉树还要满足根结点的度不大于2。

有了根结点之后，每个顶点定义了唯一的根结点，和最多2个子结点。

然而，没有足够的信息来区分左结点和右结点。

如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

完全二叉树:
由满二叉树而引出来的。

对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

满二叉树:
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。

也可以这样理解，除叶子结点外的所有结点均有两个子结点。

节点数达到最大值。

所有叶子结点必须在同一层上。

讨论问题：
Q1. 二叉排序树
它或者是一棵空树；或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值
右子树不空，则右子树上所有结点的值均大于它的根结点的值
左、右子树也分别为二叉排序树
请思考：
（1）请给出一棵二叉排序树；
答：二叉排序树的生成是随机的，也就是说给定的几个数字节点是可以组成多个二叉排序树的，一下随便给出一个：
（2）如何利用该二叉排序树得到一个递升序列？
答：采用中序遍历的方法遍历二叉树，直接就可以得到递升序列。

（3）如何利用该二叉排序树得到一个递减序列？
答：一般来讲采用逆中序遍历的方法遍历二叉树就可以了，但是这样需要重新写一个坑长子程序，在实际编程中可以直接调用中序遍历，获得一个递升序列之后通过栈输出的方式将其倒置成降序就好了。

Q2 树形结构在文件管理中的应用
（1）怎样利用树形结构来管理文件目录，并能够将文件
和文件夹加以区分；
答：在树的节点中加入一个辨识的布尔型变量来分别文件和文件夹，这样就可以分辨出空的文件夹和文件了。

（2）如何统计一个节点下文件夹和文件的数目；
答：通过遍历的方法，将数遍历一遍，扫过每个节点的时候，通过判定节点的布尔型变量来确定其是文件或者文件夹，从而再进行统计。

（3）从目录树的管理上看，要实现文件夹或文件的删除、复制、移动，请描述算法实现的思路；
答：如果要实现文件的删除、复杂、移动就必须先在树中找到需要操作的节点，然后进行操作。

而如果操作对象是文件夹的话，就必须将此文件夹的子树完全遍历一遍，再逐一操作，否则会造成操作不完全。

（4）地址路径和目录树结构怎么映射，给定一个地址路径（例如：D:\Program Files\Microsoft Office\Office14 ），怎么实现定位。

反之，给定一个节点，获得相应路径地址。

请描述算法实现的思路。

答：定位时，按string类读入路径地址，再从头扫描此路径，从一个“\”到下一个“\”之间的部分作为关键词在当前根的儿子中遍历查找，将找到的儿子作为根再重复之前的操作，直至找到目的文件。

在给定一个节点时，从此节点往回查找其父亲，找到后放入栈内，重复操作直至到root目录。

3.字典树应用
有一千万条短信，有重复，以文本文件（ASCII）形式保存，一行一条，请找出重复出现最多的前10条。

答：通过字典树实现
搜索字典项目的方法为
(1) 从根结点开始一次搜索；
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
(3)在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。

(4) 迭代过程……
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

字典树的搜索虽然快捷，但是会生成一个非常庞大的树，会占据大量的空间，这就是经典的空间换时间的思路。

102435 电子3班
鲁思瑜。