《树形结构的应用数据结构实验》由会员分享，可在线阅读，更多相关《树形结构的应用数据结构实验（7页珍藏版）》请在金锄头文库上搜索。
1、树形结构应用树形结构应用 实验日志实验日志实验题目：实验题目：建立二叉树实验目的：实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序遍历的操作。 实验主要步骤：实验主要步骤：1. 编写源程序，建立二叉树。2. 连接编译运行该程序，并在过程中调试。3. 实现各种遍历的操作。由二叉树的定义可知，一棵树由根结点、左子树和右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以 D、L、R 分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LR
2、D、DRL、RDL 和 RLD。如果限定先左后右，则只有前三种方式，即 DLR（称为先序遍历） 、LDR（称为中序遍历）和 LRD（称为后序遍历） 。 先序遍历算法：（1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 中序遍历算法：（1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 后序遍历算法：（1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。源程序：源程序：#include#include#define TREE_TYPE inttypedef struct TREE_NODETREE_TYPE value;struct TREE_NODE
3、*left; /左结点指针struct TREE_NODE *right; /右结点指针TreeNode;/连接 temp 和 tree 两个节点 TreeNode* link(TreeNode *temp,TreeNode *tree,int key)tree = (TreeNode*)malloc(sizeof(TreeNode);if(temp != NULL)if(temp-value key)temp-left = tree;elsetemp-right = tree;tree-value = key;tree-left = NULL;tree-right = NULL;return
4、 tree;/插入并建立二叉树 TreeNode * insert(TreeNode *tree,int key)TreeNode *temp = NULL,*p = tree; if(tree != NULL) while(tree != NULL tree = tree-left;elsetemp=tree;tree = tree-right;tree = link(temp,tree,key); else/if(tree = NULL)tree = link(temp,tree,key);/将下面注释掉的代码单独写成了一个函数 /*tree = (TreeNode*)malloc(siz
5、eof(TreeNode);tree-value = key;tree-left = NULL;tree-right = NULL;*/if(p != NULL)tree = p;return tree;/先序遍历 void print1(TreeNode *tree)if(tree)printf(“%3d,“,tree-value);print1(tree-left);print1(tree-right); /中序遍历 void print2(TreeNode *tree)if(tree)print2(tree-left);printf(“%3d,“,tree-value);print2(t
6、ree-right);/后序遍历 void print3(TreeNode *tree)if(tree != NULL)print3(tree-left);print3(tree-right);printf(“%3d,“,tree-value);int main()int key,i;TreeNode *tree;tree = NULL;printf(“请输入整型数：（以任意字符结束）n“); while(1)i = scanf(“%d“,if(i != 1)break;tree = insert(tree,key); printf(“n 先序遍历：“);print1(tree);printf(“n 中序遍历：“);print2(tree);printf(“n 后序遍历：“);print3(tree);printf(“n“);system(“pause“);return 0; 实验结果：实验结果：心得体会：心得体会：这次实验已经比上一次要熟练一些，并且对于这类算法的大致写法也有了一个了解，那就是递归算法的大量使用。在查错的时候对 C 语言以前忘记或不熟练的地方也进行了复习，同时，对二叉树的遍历也有了更深的理解。
