太原理工数据结构实验报告实验二树.doc

实验报告 课程名称： 数据结构B 实验项目： 树 实验地点： 实验楼110 专业班级：计科1301班 学号： 2013001989 学生姓名： 杨喆 指导教师： 孟亮 2015年 1 月 1 日 一、实验目的和要求 熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。 二、实验内容和原理 编写递归算法，计算二叉树中叶子结点的数目。 编写递归算法，在二叉树中求位于先序序列中第K个位置的结点。 将上述例题用非递归程序实现。 三、主要仪器设备 1.设备: PC微机; 2.实验环境: windows操作系统；VC++6.0, 四、实验结果与分析（必填） （1）程序代码： 实验2_1,2_2: #include stdio.h #include malloc.h #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define NULL 0 int n=0; typedef char TElemType; typedef int Status; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree; Status CreateBiTree(BiTree T) // 递归创建一棵树 { char ch; ch = getchar(); // need input 12##3## if (ch==#) T=NULL; else { if (!(T=(BiTNode *) malloc(sizeof (BiTNode)))) return (OVERFLOW); //**********————————为什么要加括号 T-data = ch ; CreateBiTree(T-lchild); CreateBiTree(T-rchild); } return OK; }//CreateBiTree Status PreOrderTraverse(BiTree T,int n) { if (T) { printf( %c,T-data); n++; if (PreOrderTraverse(T-lchild,n)) { if(T-data) if(PreOrderTraverse(T-rchild,n)) { return OK; } } //if (InOrderTraverse(T-lchild,Visit)) // if (Visit(T-data)) // if (InOrderTraverse(T-rchild,Visit)) // return OK; return ERROR; }else return OK; }//PreOrderTraverse void CountLeaf(BiTree T, int count) //实验一 { if (T) { //if (( !T-lchild) || (!T-rchild)) count++; // 对叶子结点及数 CountLeaf(T-lchild, count); CountLeaf(T-rchild, count); } // CountLeaf } Status Find_k_Node(BiTree T, int k,int i) //实验二 { if(T) { i++; if(i == k) printf(您得到的结点为%c,T-data); Find_k_Node(T-lchild,k,i); Find_k_Node(T-rchild,k,i); } return OK; } Status menu_select