} PTree;
2孩子表示法 ○
3带双亲的孩子链表 ○
4孩子兄弟表示法 ○
链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。
typedef struct node { datatype data;
struct node *fch, *nsib; }JD;
13、树和森林与二叉树的转换 加线：在兄弟之间加一连线 。
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系， 旋转：以树的根结点为轴心，将整树顺时针转45°。 14、 将二叉树转换成树
? 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来.
? 抹线：抹掉原二叉树中双亲与右孩子之间的连线 ? 调整：将结点按层次排列，形成树结构 14、森林转换二叉树
（1）将各棵树分别转换成二叉树.
（2）将每棵树的根结点用线相连.
（3）以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 15、 二叉树转换成森林
抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树. 还原：将孤立的二叉树还原成 16、 树和森林的遍历 树的遍历
两种次序遍历树的方法：一种是先根（次序）遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树；
一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后访问根结点。
森林的遍历
先序遍历：A B C D E F G H I J 中序遍历：B C D A F E H J I G 17、 赫夫曼树及其应用
例题： w={5, 29, 7, 8, 14, 23, 3, 11}
习题：
1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 B 。
（A）正确 （B）错误 2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 D 。
（A）空或只有一个结点 （B） 完全二叉树
（C）二叉排序树 （D） 高度等于其节点数 3、 深度为5的二叉树至多有C 个结点。
（A）16 （B）32 （C）31 （D）10 4、根据使用频率为5个字符设计的赫夫曼编码不可能是C . （A）111，110，10，01，00 （B）000，001，010，011，1 （C）100，11，10，1，0 （D）001，000，01，11，10
5、树和二叉树的主要差别是（1） 树的结点个数至少为1，而二叉树的结点个数可以为 0（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为2（3）树的结点无左、右之分，而二叉树的结点右左、右之分。
6、深度为k的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号 。
7、一棵二叉树的第i(i?1)层最多有 个结点；一棵有n（n>0）个结点的满二叉树共有 个叶子结点和
个非叶子结点。
8、已知二叉树的先序、中序和后序序列分别如下，其中有一些看不清的字母用*表示，请构造出一棵符合条件的二叉树并画出该二叉树。
? 先序序列是：*BC**FG ? 中序序列是：CB*EAG* ? 后序序列是：*EDB*FA
9、将右图所示的树转化为二叉树，并写出先序遍历，中序遍历和后序遍历的结果。 解：
先序：ABEFGCDHI 中序：EFGBCHIDA 后序：GFEIHDCBA
10、设给定权集w={2，3，4，7，8，9}，试构造关于w的一棵赫夫曼树，并求其加权路径长度WPL。
WPL=(9+7+8)*2+4*3+(2+3)*4=80
第十章 内部排序
1、内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序和分配排序。 2、直接插入排序 ? 直接插入的算法实现
void sort(NODE array[],int n)
//待排序元素用一个数组array[ ] 表示，数组有n个元素 { int i, j;
NODE x; // x 为中间结点变量 for ( i=1; i while ((j>=0)&& ( x.key {array[j+1]=array[j]; j--; } // 顺序比较和移动 array[j+1]=x; } } 例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如图7-1所示。 0 1 2 3 4 5 初始状态 (17 ) 3 25 14 O （ n2 20 直接插入排序的时间复杂度为）。 9 直接插入算法的元素移动是顺序的，该方法是稳定的。 第一次插入 (3 17 ) 25 14 20 9 3、希尔排序 (3 17 25 ) 14 20 9 第二次插入 希尔排序的时间复杂性在O（nlog2n）和O（n2 ）之间，大致为 第三次插入 (3 14 17 25 ) 20 9 n1.3）O （。 第四次插入 (3 14 17 20 25 ) 9 由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。 例如，n=8，数组array[ ]的八个元素分别为：91，67，35，62，29，72，46，57。下面用图10-2给出希尔排序算法的执行过程。 图10-1直接插入排序示例 第五次插入 (3 9 14 17 20 25)
数据结构 清华大学出版社 严蔚敏吴伟民编著
