数据结构二叉树的运用解析.ppt

数据结构 实验目的及要求 实验目的： 1.了解二叉树是一种非线性数据结构，熟悉二叉树的各种存储和基本操作； 2.掌握二叉树的各种遍历方法，并基于二叉树解决相关实际应用问题。 实验要求： 1.掌握二叉树的存储和表示方法及其各种基本操作； 2.将源代码中函数的指针变量参数改为引用参数； 3.运用二叉树建立和存储通讯录（姓名，联系电话，E-mail），实现对通讯录的查找、修改、增加和删除等功能。 实验内容（算法，程序，运行结果） 实验内容一： 使用递归算法建立计算表达式的二叉树，实现相应二叉树的各种基本操作，输出前序、中序和后序二叉树遍历的结果。 算法思想： 定义二叉树结构体类型时，也定义了一个顺序栈结构体类型,用以辅助完成二c叉树的非递归遍历。 由键盘输入二叉树先序序列，用扩展线序序列函数接受并创建二叉链表。 遍历前先判断二叉树是否为空若为空，执行空操作;否则依次执行各 遍历函数相应操作。 先序遍历算法思想，先访问根节点， 然后按先序遍历左子树， 再按先序遍 历右子树。 中序遍历算法思想，先按中序遍历左子树， 再访问根节点， 然后按中序访 问右子树。 后序遍历算法思想，先按后序遍历左子树， 接着按中序遍历右子树，然后 访问根节点。 谢谢观赏 * * * 程序中具体的算法实现 preorder(bitree root) 先序递归遍历 {if(root!=NULL) { printf(%c ,root-data); preorder( root-lchild); preorder( root-rchild);} } 若二叉树不为空则先访问根节点，再按先序遍历左子和右树。 inorder(bitree root) 中序递归遍历 { if(root!=NULL) { preorder(root-lchild); printf(%c ,root-data); preorder( root-rchild); } } 若二叉树不为空则先遍历左子树，再访问根节点，然后按中序访问右子树 postorder(bitree root) 后序递归遍历 { if(root!=NULL) { preorder(root-lchild); preorder (root-rchild); printf(%c ,root-data); } } 若二叉树不为空则先遍历左子树，再按中序访问右子树，然后访问根节点。 文本 运行结果： 实验内容二 使用递归算法建立计算表达式的二叉树，实现相应二叉树的各种基本操作，输出二叉树层次遍历的结果。 算法思想： 同一层从左到右访问，用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。 程序中具体的算法实现 CreateBinTree(BinTree T)//层次遍历二叉树 char ch; ch=getchar(); if(ch== ) T=NULL; else{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) printf(%c 结点建立失败!); T-data=ch; CreateBinTree(T-lchild); CreateBinTree(T-rchild); } } 同一层从左到右访问，用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。 运行结果： 实验内容三 运用二叉树建立和存储通讯录（姓名，联系电话，E-mail），实现对通讯录的查找、修改、增加和删除等功能。 算法设计： 3.1设计功能 程序运行后的功能有： （1）菜单选择界面 （2）建立通讯录记录 （3）插入联系人记录 （4）查找联系人记录（名称和编号查询） （6）删除联系人记录 （7）输出所有联系人记录 （8）退出程序 3.2系统流程图如图所示： 3.3程序中具体的算法实现 3.3.1建立链表 （1）使链表的头尾指针head、rear指向新生成的头结点（也就是尾结点）； （2）置结束标志为0（假）； （3）while(结束标志不为真) ｛ P指向新生成的结点； 读入一个通讯者数据至新结点的数据域； 将新结点链到尾结点之后； 使尾指针指向新结点； 提示是否继续建表，读入一个结束的标志； ｝ （4）尾结点的指针域置空置NULL。 具体算法程序实现函数：LinkList CreateList(void) 3.3.2通讯者结点信息的插入 插入的基本思想是：使用两个指针变量p1和p2分别指向当前访问过的结点和下一个结点，循环顺序查找链表。寻找插入结点的位置，其中p1指向待插入位置的前一个结点。