实验11：递归综合实验
一、实验目的
1）熟悉递归的定义和递归的算法设计。
2）加深对递归算法的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。 本次实验共计4学时。
三、实验容
以下两个实验任选一个。
1、求解n皇后问题
编写一个程序，求解皇后问题：在n×n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同对角线。 要求：使用递归算法求解；皇后的个数n由用户输入，其值不能超过20。
2、求解汉诺塔问题
设有3个分别命名为X,Y和Z的塔座,在塔座X上有n个直径各不相同,从小到大依次编号为1,2,…,n的盘片,现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放,盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X,Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法。
要求：使用递归算法求解；盘片的个数n由用户输入，其值不能超过12。
实验12：二叉树的操作
一、实验目的
1）熟悉二叉树树的基本操作。
2）掌握二叉树的实现以及实际应用。
3）加深二叉树的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。 本次实验共计4学时。
三、实验容
1、二叉树的基本操作
【问题描述】 现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：
1> 创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的
链式存储结构。
2> 输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。
3> 查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结
点的指针。
4> 求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,
其高度等于左子树与右子树中的最大高度加l。 5> 求二叉树的结点个数NodesCount(BTNode *b) 6> 先序遍历的递归算法：void PreOrder(BTNode *b) 7> 中序遍历的递归算法：void InOrder(BTNode *b) 8> 后序遍历递归算法：void PostOrder(BTNode *b) 9> 层次遍历算法void LevelOrder(BTNode *b)
【基本要求】
实现以上9个函数。 主函数中实现以下功能： 创建下图中的树b 输出二叉树b
找到’H’节点，输出其左右孩子值 输出b的高度
输出b的节点个数 输出b的四种遍历顺序
A B C D E F H J K L M N
【实验提示】
数据结构的定义： #include
各个函数的定义：
void CreateBTNode(BTNode *&b,char *str); BTNode *FindNode(BTNode *b,ElemType x); int BTNodeDepth(BTNode *b); void DispBTNode(BTNode *b); int NodesCount(BTNode *b); void PreOrder(BTNode *b); void InOrder(BTNode *b); void PostOrder(BTNode *b); void TravLevel(BTNode *b); 主函数的结构： void main() {
G I
}
BTNode *b,*p,*lp,*rp;;
char str[]=\CreateBTNode(b,str); printf(\
printf(\输出二叉树:\printf(\结点:\p=FindNode(b,'H'); if (p!=NULL) { //此处输出p的左右孩子节点的值 }
printf(\
printf(\二叉树b的深度:%d\\n\printf(\二叉树b的结点个数:%d\\n\printf(\
printf(\先序遍历序列:\\n\
printf(\ 递归算法:\printf(\中序遍历序列:\\n\
printf(\ 递归算法:\printf(\后序遍历序列:\\n\
printf(\ 递归算法:\printf(\层次遍历序列:\TravLevel(b); printf(\
2.2 二叉树的线索化
【问题描述】
编写一个程序，实现中序线索化二叉树，输出线索中序序列。
【基本要求】
用上图的二叉树b来验证你的程序。
【实验提示】
数据结构的定义： #include
struct node *lchild; struct node *rchild; } TBTNode; TBTNode *pre; 各个函数的定义：
void CreateTBTNode(TBTNode * &b,char *str) void DispTBTNode(TBTNode *b) void Thread(TBTNode *&p)
TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树*/ void ThInOrder(TBTNode *tb)
主函数的结构： void main() { TBTNode *b,*tb; CreateTBTNode(b,\ printf(\二叉树:\ tb=CreaThread(b); printf(\线索中序序列:\}
3．实验结果
此处填写程序运行结果。
4．实验心得
此处填写你的实验心得体会。
[11]实验指导手册范本
