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

树形结构应用 实验日志实验题目：建立二叉树实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序遍历的操作。 实验主要步骤：1. 编写源程序，建立二叉树。2. 连接编译运行该程序，并在过程中调试。3. 实现各种遍历的操作。由二叉树的定义可知，一棵树由根结点、左子树和右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、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 *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; else temp-right = tree; tree-value = key; tree-left = NULL; tree-right = NULL; return tree;/插入并建立二叉树 TreeNode * insert(TreeNode *tree,int key) 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); /将下面注释掉的代码单独写成了一个函数 /*tree = (TreeNode*)malloc(sizeof(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(tree-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,&key); 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; 实验结果：心