第二次直播 清华大学 殷人昆 中央电大 徐孝凯

本次要讲的问题 第五章 递归与广义表 第六章 树与二叉树

第五章 递归与广义表 学习目的 掌握递归问题求解方法 运用递归方法求解应用问题

需要掌握的知识点 递归概念： 什么是递归？ 递归的函数定义 递归的数据结构 递归问题的解法 链表是递归的数据结构 可用递归过程求解有关链表的问题

递归实现时栈的应用 递归求解思路 递归过程与递归工作栈：递归过程实现的机制及递归工作栈的引用 递归的分层(树形)表示 :递归树 递归深度(递归树的深度)与递归工作栈的关系 单向递归与尾递归的迭代实现

广义表 广义表定义 广义表长度、深度、表头、表尾 广义表的表示及操作 用图形表示广义表的存储结构 广义表的递归算法

递归举例 求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n-1) + Fib (n-2); }

考虑使用递归算法求解的思路 递归算法的一般形式 void p ( 参数表 ) if ( 递归结束条件) 可直接求解步骤； 基本项 else p ( 较小的参数 ); 递归项

例 求数组 A 中 n 个整数的和 return A[n] + sum(n-1); //求n-1个整数的和, 再加A[n] int sum ( int n ) { if ( n == 0 ) return A[0]; //直接求解 else return A[n] + sum(n-1); //求n-1个整数的和, 再加A[n] }

递归与回溯 常用于搜索过程 例 n皇后问题 在 n 行 n 列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。

    k = n+i-j-1 0#次对角线 2#次对角线 1#次对角线 4#次对角线 3#次对角线 0 1 2 3 6#次对角线 5#次对角线 0 1 2 3 1 2 3    0#主对角线 2#主对角线 4#主对角线 6#主对角线 1#主对角线 3#主对角线 5#主对角线  k = i+j

解题思路 安放第 i 行皇后时，需要在列的方向从 1 到 n 试探 ( j = 1, …, n ) 在第 j 列安放一个皇后：

设置 4 个数组 col [n] ：col[i] 标识第 i 列是否安放了皇后 md[2n-1] : md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] : sd[k] 标识第 k 条次对角线是否安放了皇后 g[n] : g[i] 记录第 i 行皇后在第几列

void green( int i ) { for ( int j = 1; j <= n; j++ ) { if ( 第 i 行第 j 列没有攻击 ) { 在第 i 行第 j 列安放皇后； if ( i == n ) 输出一个布局； else green ( i+1 ); } 撤消第 i 行第 j 列的皇后；

算法求精 void green( int i ) { for ( int j = 1; j <= n; j++ ) { if ( !col[j] && !md[n+i-j-1] && !sd[i+j] ) { /*第 i 行第 j 列没有攻击 */ col[j] = md[n+i-j-1] = sd[i+j] = 1; g[i] = j; /*在第 i 行第 j 列安放皇后*/

cout << g[j] << ‘,’; cout << endl; } if ( i == n ) { /*输出一个布局*/ for ( j = 0; j <= n; j++ ) cout << g[j] << ‘,’; cout << endl; } else green ( i+1 ); col[j] = md[n+i-j-1] = sd[i+j] = 0; g[i] = 0; /*撤消第i行第j列的皇后*/

第六章 树与二叉树 学习目的 理解树与二叉树的结构特点 掌握树与二叉树的特定应用（如堆、霍夫曼树等）

需要掌握的知识点 树 树的定义、树的基本运算 树的分层定义是递归的 树中结点个数与高度的关系 二叉树 二叉树定义、基本运算 二叉树性质 树 树的定义、树的基本运算 树的分层定义是递归的 树中结点个数与高度的关系 二叉树 二叉树定义、基本运算 二叉树性质 二叉树结点个数与高度的关系 不同二叉树的棵数

完全二叉树的顺序存储 完全二叉树的双亲、子女和兄弟的位置 二叉树的前序 · 中序 · 后序 · 层次遍历 前序 · 中序 · 后序的线索化二叉树中前驱与后继的查找方法 应用二叉树遍历的递归算法

霍夫曼树 霍夫曼树的构造方法 霍夫曼编码 带权路径长度的计算 树的存储 树的广义表表示与双亲表示 树与二叉树的对应关系 树的先根 · 后根 · 层次遍历

堆 堆的定义、堆的插入与删除 形成堆时用到的向下调整算法 形成堆时比较次数的上界估计 堆插入时用到的向上调整算法 堆的插入与删除算法

【例1】在结点个数为n (n > 1)的各棵树中，高度最小的树的高度是多少？它有多少叶结点？多少分支结点？高度最大的树的高度是多少？它有多少叶结点？多少分支结点？

【解答】结点个数为 n 时, 高度最小的树的高度为 1, 有 2层；有 n-1 个叶结点，1 个分支结点；

【例2】已知一棵二叉树的前序遍历的结果序列是 ABECDFGHIJ 中序遍历的结果序列是 EBCDAFHIGJ 试画出这棵二叉树。

【解答】前序序列 ABECDFGHIJ，中序序列 EBCDAFHIGJ 时：

前序序列 ABECDFGHIJ 中序序列 EBCDAFHIGJ A A B F B F E C G E C G D H J D HI J I

【例3】若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法： (1) 统计二叉树中叶结点个数。 (2) 以二叉树为参数, 交换每个结点的左子女和右子女。

【解答】 (1) 定义二叉树结构 template <class Type> class BinaryTree; //二叉树 class BinTreeNode //二叉树结点 leftChild data rightChild

(2) 统计二叉树中叶结点个数 3 2 1 1 1 1 1

template <class Type> int leaf ( BinTreeNode<Type>* t ) { if ( !t ) return 0; else if ( !t→leftChild && !t→rightChild ) return 1; else return leaf ( t→leftChild ) + leaf ( t→rightChild ); }

(3) 交换每个结点的左子女和右子女

template <class Type> void exchange ( BinTreeNode<Type>* t ) { BinTreeNode<Type>* p; if ( t→leftChild || t→rightChild ) { //非叶结点，交换左、右子女 p = t→leftChild; t→leftChild = t→rightChild ; t→rightChild = p;

exchange ( t→leftChild ); exchange ( t→rightChild ); }

【例4】假定用于通信的电文仅由 8 个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成, 各字母在电文中出现的频率分别为 5, 25, 3, 6, 10, 11, 36, 4。试为这 8 个字母设计不等长 Huffman 编码, 并给出该电文的总码数。

【解答】

则Huffman编码为 电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + c1 c2 c3 c4 c5 c6 c7 c8 1110 00 1100 1111 100 101 01 1101 电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257

【例5】下面是对二叉树进行中序遍历的递归算法。 template <class Type> void inorder ( BinTreeNode<Type>* t ) { if ( t ) { inorder ( t→leftChild )； cout << t→data； inorder ( t→rightChild )； }

将算法中的第二个递归语句消去, 这相当于尾递归，可用循环实现 template <class Type> void inorder ( BinTreeNode<Type>* t ) { while ( t ) { inorder ( t→leftChild )； cout << t→data； t = t→rightChild； }

接着, 将算法中的第一个递归语句消去, 这必须借助于栈, 记忆回退的路径. template <class Type> void InOrder ( BinTreeNode<Type>* t ) { StackType S; BinTreeNode<Type>* p = t; S.makeEmpty( ); //初始化

do{ while ( p ) { S.Push(p); p = p→leftChild; } if ( !S.IsEmpty( ) ) { p = S.getTop( ); S.Pop( ); cout << p→data << endl; p = p→rightChild; } } while ( p || !S.IsEmpty( ) );

下一次直播时间：5月10号 同学们：再见！