线索二叉树的运算.docx

文档来源为 : 文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持 . PAGE 10 PAGE 10文档来源为 : 从网络收集整理 .word 版本可编辑 .欢迎下载支持 . 计算机科学与技术系 课程设计报告 2008 ～2009 学年第 2 学期 线索二叉树的运算屠菁、张贯红课 程 数据结构课 程 设 计 名 线索二叉树的运算 屠菁、张贯红 学 生 姓 名 学 专 业 班 号 级 指 导 教 师 2009 年 5 月 题目：（线索二叉树运算）实现线索二叉树的建立、插入、删除、恢复线索的实现。 一、 问题分析和任务定义 任务定义： 此程序需要完成如下要求：建立线索二叉树，并实现线索二叉树的插入、删除和恢复线索的实现。 实现本程序需要解决以下几个问题： 1、 如何建立线索二叉树。 2、 如何实现线索二叉树的插入。 3、 如何实现线索二叉树的删除。 4、 如何实现线索二叉树恢复线索的实现。 此题目是线索二叉树的一系列操作问题。 首先就要明白线索二叉树是什么， 利用二叉链表的空指针域将空的左孩子指针域改为指向其前驱， 空的右孩子指针域改为指向其后继， 这种改变指向的指针称为线索， 加上了线索的二叉链表称为线索链表， 相应的二叉树称为线索 二叉树。 在这个问题中，要解决的任务是：实现线索二叉树的建立、插入、删除、恢复线索的实 现。 n 个结点的二叉链表中含有 n+1 个空指针域。利用二叉链表中的空指针域，存放指向结 点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为 线索 ）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树 (Threaded BinaryTree) 。根据线索性质的不同， 线索二叉树可分为前序线索二叉树、 中序线索二叉树和后序线索二叉 树三种。在此次课程设计中，采用的是中序线索二叉树。 问题分析： 既然题目要求要分别实现建立、删除、和恢复线索化三种功能，建立和删除一定是相 互独立的模块， 可分别建立两个函数来实现功能。 第三个功能是恢复线索， 就要考虑这个线索恢复是怎样的恢复过程， 是怎样恢复的。 恢复线索是对二叉树当进行了插入和删除操作过 程后， 因为过程中有结点的变动， 而进行的在操作结束以后对整个二叉树的恢复线索， 还是在实现插入和删除的过程中就对操作的结点实现局部的恢复线索。 从设计的目标来说应该是 要在删除和插入的过程中实现对线索的恢复。 而在线索二叉树中插入一个结点或删除一个结 点，一般情况下，这些操作有可能破坏原来已有的线索，因此，在修改指针时，还需要对线索做相应的修改。因此一般来说，这个过程花费的代价几乎与重新进行线索化相同。 二、概要设计和数据结构选择 首先建立二叉树，然后对二叉树进行线索化。线索链表的结点结构 线索链表中的结点结构为： 中序线索二叉树的图示 图(1) 线索链表中的结点结构 图(2) 中序线索二叉树 建立二叉树 （即指在内存中建立二叉树的存储结构） ，建立一个二叉链表， 需按某种顺序一次输入二叉树中的结点， 且输入顺序必须隐含结点间的逻辑结构信息。 对于一般的二叉树， 需添加虚结点，使其成为完全二叉树。 关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列， 该队列是一个指针类型的数组，保存已输入的结点地址。 操作：（1）令队头指针 front 指向其孩子结点当前输入的建立链接的父结点，队尾指针 rear 指向当前输入的结点，初始： front=1,rear=0; 若 rear 为偶数，则该结点为父结点的左孩子； 若 rear 为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。 若父结点与其两个孩子结点的链接完毕，则令 front=front+1, 使 front 指向下一个等待链接的父结点。 二叉树的中序索化算法与中序历算法类似。只需要将遍历算法中访问结点的操作具体化 为建立正在访问的结点与其非空中前趋结点间线索。 该算法应附设一个指针 pre 始终指向刚刚访问过的结点（ pre 的初值应为 NULL），而指针 p 指示当前正在访问的结点。结点 *pre 是结点 *p 的前趋，而 *p 是*pre 的后继。 程序流程图 : 图(3) 程序流程图 三、详细设计和编码 建树算法 ： 1、分析 ：建立一个二叉链表，需要按照某种顺序依次输入二叉树中的结点，且该输入 顺序必须隐含结点间的逻辑结构的信息。 这个建立的方法， 按完全二叉树的层次顺序， 依次输入结点信息建立二叉链表的过程。以 @表示空结点，以 #表示输入结束的标志 。 2、算法思想 ：依次输入结点信息，若其不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点，否则将新结点作为孩子链接到它的父亲结点上。 3