httpreadpudncomdownloads13sourcecodeasm54602数据结构实习报告doc.docVIP

数据结构实习报告 二叉树的集合操作 链表、堆栈和队列都是线性数据结构，而树则是一种某些特定特点的非线性的二维数据结构。大家知道，数组和链表在处理大批量数据的时候各有优劣，前者可以实现随机访问但是在添加、删除和移动数据时要作大量的数据移动；后者在修改数据时操作简便，但查找数据则颇为不便。树可以说是两者的折衷，它虽然不能直接实现随机访问，但是查找的效率要比链表高的多，同时也可以快捷地实现数据的变动和修改，这使得它在查找领域用途广泛。同时，由于树在层次划分方面的特性，使得它能够抽象许多现实问题，实现一些常用的算法。二叉树是树中最常用到的一种，它在查找，排序，模拟子集问题等等方面都有着重要的应用。 二、算法的设计 要实现上述的功能，我们首先要深刻的了解二叉树的数据结构，然后依据它的特点，着手如何去创建一棵二叉树，然后，用不同的方法对这棵二叉树进行不同的遍历，实现其它的功能，包括用户友好界面的实现等等一系列的后续操作。 三、数据结构的设计 本程序要用到的数据类型 struct BinTreeNode { DataType info； PBinTreeNode llink； PBinTreeNode rlink； }； 然后定义我们需要的指针类型 typedef struct BinTreeNode *PBinTreeNode；/ 定义指向二叉树结点的指针类型/ typedef PBinTreeNode *PBinTree; /定义指向树型结点的指针类型/ 　 四、 程序需要用到的自定义函数 1．创建一个二叉树根节点 PBinTree Create_BinTreeRoot(void) 2．创建一个二叉树的节点 PBinTreeNode Create_BinTreeNode(void) 3．创建一棵二叉树 PBinTreeNode Create_BinTree(void) 4．用先根的方法遍历一棵二叉树 void preOrder(PBinTreeNode pbnode) 5．用中根的方法遍历一棵二叉树 void inOrder(PBinTreeNode pbnode) 6．用后根的方法遍历一棵二叉树 void postOrder(PBinTreeNode pbnode) 7．打印出我们创建的二叉树的树型结构 void outputTree(PBinTreeNode pbnode,int totalSpace) 8．打印出二叉树的叶子结点 void leaves(PBinTreeNode pbnode) 9．释放我们所申请的所有结点空间 void freeAllNodes(PBinTreeNode pbnode) 10．判断我们输入的是否是合格的字符，我们把它们定义为a-z或者是A-Z之间的字符，用‘@’字符作为结束当前结点的标识符 int isalphabet(char i) 五、具体程序的实现 1． PBinTreeNode Create_BinTreeNode(void) 我们定义一个指向二叉树结点类型的指针PBinTreeNode，然后，申请一个二叉树结点大小的空间，对左右子结点赋为空。 2．创建一个二叉树根节点 定义一个指向二叉树结点的指针的指针即：BinTreeNode ** pbtree, 或者是：PBinTreeNode *pbtree；用于存放树的根结点，同时，将我们创建的二叉树的地址传给它即：*pbtree=Create_BinTree()； 3． 创建一棵二叉树 首先我们定义一个DataType类型的变量i,用于存放我们输入的字符（即作为缓冲区），并用scanf函数去接收它，由于使用scanf函数时，会出现吸收我们输入的回车字符，并将会车作为接收的字符的情况发生，为了避免这种情况，我们用函数fflush(stdin)将缓冲区的字符全部冲掉，然后再吸收我们输入的字符，就可以完全避免此类问题的发生。我们定义我们输入的字符是从a-z或者是A-Z，用字符@为我们结束当前结点左或者右结点的字符，然后递归调用左右子树，此时我们将一棵二叉树全整的创建出来了。 4．用先根的方法遍历一棵二叉树 先访问根结点，打印出它里面的信息，然后递归调用左子树和右子树。 5．用中根的方法遍历一棵二叉树 先递归调用左子树，打印出里面的信息，在打印出根结点信息，然后递归调用右子树，打印出里面的信息。 6．用后根的方法遍历一棵二叉树 先递归调用左子树，打印出里面的内容，然后递归调用右子树，打印出里面的内容，然后是根结点的内容。 7. 打印出我们创建的二叉树的树型结构 先递归调用右子树，如果结点不为空的话，空格数加5，如果为空的话，就打印出右子树的内容，然后递归调用左子树。 8．打印出二叉树的叶子结点 如果当前结点的左右子树都为空的话，就打印出此