二叉树的操作及应用(新20151126)课案.doc

实验四 二叉树的操作及应用 实验学时：4 实验类型：（设计型） 一、实验目的 1.理解并掌握二叉树的逻辑结构和物理结构——二叉链表； 2.掌握二叉树的遍历方法； 3.掌握二叉树的构造方法； 4. 掌握计算二叉树结点个数、高度、叶子结点个数算法实现； 5. 掌握交换二叉树左右子树以及复制一棵二叉树算法的实现。 二、实验条件 Visual C++ 6.0 三、实验原理及相关知识 四、实验步骤 (1)中序、前序、后序、层次遍历的递归算法的基本思想及算法实现； (2利用(3)求结点个数、高度、叶子结点个数、交换二叉树左右子树以及复制一棵二叉树的递归算法的基本思想及算法实现 1.线索二叉树的构造及线索化方法的算法实现。 【参考程序1】 #includestdio.h #includemalloc.h #include math.h #define MaxSize 20 typedef int ElemType; #define OK 1 typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; //建立二叉树（按先序序列生成二叉树,#表示空节点） void CreateBiTree(BiTree *T) { char ch; scanf(%c,ch); getchar();/*回车键（每次输入一个字符后，需敲回车键）*/ if(ch==#) { printf(不产生子树。\n); *T=NULL; } else { if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))) { printf(分配空间失败); return; }//生成一个新节点 (*T)-data = ch; printf(产生左右子树。\n); ; ; } } //递归前序遍历 void Preorder(BiTNode *T) { if(T) { printf(%c ,T-data); Preorder(T-lchild); Preorder(T-rchild); } } //递归中序遍历 void Inorder(BiTNode *T) { if(T) { ; ; ; } } //递归后序遍历 void Postorder(BiTNode *T) { if(T) { ; ; ; } } //层次遍历二叉树 void Translever(BiTNode *T) { struct node { BiTNode *vec[MaxSize]; int f,r; //r为队尾，f为队头 }queue; BiTNode *p; p=T; queue.f=0; queue.r=0; if(T) printf(%c , p-data); queue.vec[queue.r]=p; queue.r=queue.r+1; while(queue.fqueue.r) { p=queue.vec[queue.f]; queue.f=queue.f+1; if(p-lchild) { printf(%c ,p-lchild-data); queue.vec[queue.r]=p-lchild; queue.r=queue.r+1; } if(p-rchild) { ; ; ; } } printf(\n); } //按广义表形式输出二叉树 void Disptree(BiTNode *T) { if(T) { printf(%c,T-data); if(T-lchild || T-rchild) { printf((); Disptree(T-lchild); i