上机作业3 1.输入带空二叉树(信息)的先序遍历序列,生成一棵二叉树; 若结点为字符类型,用空格表示空二叉树;若结点为整数类型,用0(零)表 示空二叉树; 2.作前序遍历,分别用递归算法、非递归算法实现 3.作中序遍历,分别用递归算法、非递归算法实现 4.作后序遍历,用递归算法实现 5.求度分别为0、1、2的结点的数目,分别用递归算法、非递归算法实现; **6.按层次遍历二叉树(提示:使用一个队列实现); **7.求二叉树的高度(深度); **8.判断是否为满二叉树,输出"Yes!"/"No!"; **9.交换每个结点的左右子树; **10.对交换左右子树后的二叉树作中序遍历。 说明和要求 1.选做带“*”的题 2.每一种操作用C函数或C++函数实现,二叉树的根指针为C(或C++)函数的 形式参数 3.第12周交第1,2,5题的程序清单(打印或手抄),关键位置加注释。 4.参考程序结构 # include" stdlib.h”/*或" malloc.h",存储分配头文件*/ # include" stdio.h"/*标准I/0头文件* #define null o /*定义空指针NULL*/ # define leng sizeof( struct Bnode)/*结点所占的字节数*/ typedef char ElemType /*抽象元素类型为整型*/ typedef struct Bnode /* Bnode为结点(结构)类型*/ i Elem Type data /*data为抽象元素类型*/ struct Bnode *lchild. *krchild /*为指针类型*/ creat tree(Bnode *kroot /*root是指向指针的指针*/ /*生成二叉树* ElemType ch scanf("%c", &ch) /*输入结点,字符型*/ )(root)=NULL /*生成空二叉树*/ /*生成非空二叉树*
上 机 作 业 3 1.输入带空二叉树(信息)的先序遍历序列，生成一棵二叉树； 若结点为字符类型,用空格表示空二叉树；若结点为整数类型,用 0(零)表 示空二叉树； 2.作前序遍历，分别用递归算法、非递归算法实现； 3.作中序遍历，分别用递归算法、非递归算法实现； 4.作后序遍历，用递归算法实现； 5.求度分别为 0、1、2 的结点的数目,分别用递归算法、非递归算法实现； **6.按层次遍历二叉树(提示：使用一个队列实现）； **7.求二叉树的高度(深度)； **8.判断是否为满二叉树，输出"Yes!"/"No!"； **9.交换每个结点的左右子树； **10.对交换左右子树后的二叉树作中序遍历。 说明和要求 1.选做带“**”的题； 2.每一种操作用 C 函数或 C++函数实现,二叉树的根指针为 C(或 C++)函数的 形式参数； 3.第 12 周交第 1,2,5 题的程序清单(打印或手抄),关键位置加注释。 4.参考程序结构： #include"stdlib.h" /* 或"malloc.h",存储分配头文件 */ #include"stdio.h" /* 标准 I/O 头文件 */ #define NULL 0 /* 定义空指针 NULL */ #define LENG sizeof(struct Bnode) /* 结点所占的字节数 */ typedef char ElemType; /* 抽象元素类型为整型 */ typedef struct Bnode /* Bnode 为结点(结构)类型 */ { ElemType data； /* data 为抽象元素类型 */ struct Bnode *lchild, *rchild； /* 为指针类型 */ }Bnode； creat_tree(Bnode **root) /*root 是指向指针的指针*/ { /*生成二叉树*/ ElemType ch； scanf("%c",&ch)； /*输入结点,字符型*/ if (ch==’ ’)(*root)=NULL； /*生成空二叉树*/ else /*生成非空二叉树*/
[(*root)=(Bnode *)malloc (LENG) (*root)->data=ch /*生成根结点* creat tree(&(*root)- lchild);/*递归生成左子树*/ creat tree(&(*root)- rchild);/*递归生成右子树*/ return void preorder(Bnode *root) {/米前序遍历二叉树* void main(void)/*主函数*/ I Bnode * root creat tree(&root) preorder(root)
{ (*root)=(Bnode *)malloc(LENG)； (*root)->data=ch； /*生成根结点 */ creat_tree(&(*root)->lchild) ； /*递归生成左子树*/ creat_tree(&(*root)->rchild) ； /*递归生成右子树*/ } return； } void preorder(Bnode *root) { /*前序遍历二叉树*/ if ( … ) ………… } …………… …………… void main(void) /*主函数*/ { Bnode *root； creat_tree(&root)； preorder(root)； ………………… }