树形结构的应用数据结构实验

《树形结构的应用数据结构实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、树形结构应用实验日志实验题目：建立二叉树实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序遍历的操作。实验主要步骤：1.编写源程序，建立二叉树。2.连接—编译—运行该程序，并在过程中调试。3.实现各种遍历的操作。由二叉树的定义可知，一棵树由根结点、左子树和右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。如果限定先左后右，则

2、只有前三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。先序遍历算法：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。中序遍历算法：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。后序遍历算法：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。源程序：#include#include#defineTREE_TYPEinttypedefstructTREE_NODE{TREE_TYPEvalue;structTREE_NODE*left;//左结点指针str

3、uctTREE_NODE*right;//右结点指针}TreeNode;//连接temp和tree两个节点TreeNode*link(TreeNode*temp,TreeNode*tree,intkey){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;returntree;}//插入并建立二叉树T

4、reeNode*insert(TreeNode*tree,intkey){TreeNode*temp=NULL,*p=tree;if(tree!=NULL){while(tree!=NULL&&tree->value!=key){if(tree->value>key){temp=tree;tree=tree->left;}else{temp=tree;tree=tree->right;}}tree=link(temp,tree,key);}else//if(tree==NULL){tree=link(temp,tree,key);//将下面注释掉的代码单独写成了一个

5、函数/*tree=(TreeNode*)malloc(sizeof(TreeNode));tree->value=key;tree->left=NULL;tree->right=NULL;*/}if(p!=NULL)tree=p;returntree;}//先序遍历voidprint1(TreeNode*tree){if(tree){printf("%3d,",tree->value);print1(tree->left);print1(tree->right);}}//中序遍历voidprint2(TreeNode*tree){if(tree){print2(tr

6、ee->left);printf("%3d,",tree->value);print2(tree->right);}}//后序遍历voidprint3(TreeNode*tree){if(tree!=NULL){print3(tree->left);print3(tree->right);printf("%3d,",tree->value);}}intmain(){intkey,i;TreeNode*tree;tree=NULL;printf("请输入整型数：（以任意字符结束）");while(1){i=scanf("%d",&key);if(i!=1)brea

7、k;tree=insert(tree,key);}printf("先序遍历：");print1(tree);printf("中序遍历：");print2(tree);printf("后序遍历：");print3(tree);printf("");system("pause");return0;}实验结果：心得体会：这次实验已经比上一次要熟练一些，并且对于这类算法的大致写法也有了一个了解，那就是递归算法的大量使用。在查错的时候对C语言以前忘记或不熟练的地方也进行了复习，同时，对二叉树的遍历也有了更深的理解。