线索二叉树的运算程序报告.doc

问题分析和任务定义： 1、题目：线索二叉树的运算 2、要求和任务：在这个问题中，要解决的任务是：实现线索树建立、插入、删除、恢复线索的实现 二、数据结构的选择和概要设计 1、数据结构 二叉树是由n（n=0） 约定： Ltag=0 //表示lchild域指示该结点的左孩子 Ltag=1 //表示lchild域指示该结点的前驱 Rtag=0 //表示rchild域指示该结点的右孩子 Rtag=1 //表示rchild域指示该结点的后继 (2)线索链表中结点类型说明： Typedef char datatype; Typedef struct node{ Int ltag,rtag; Datatype data; Struct node *lchild,*rchild; }bithptr; (3)线索化算法：结点*pre 是结点*p的前驱，而*p是*pre的后继。这样，当遍历到结点*p时，可以进行以下三步操作： 1）若*p有空指针域，则将相应的标志置1. 2）若*p的左线索标志已经建立（p-ltag=1））Bitree *crt_bt_pre(bitree *bt){ Char ch; Ch=getchar( ); If(ch==‘＃’) Bt=null; Else{ Bt=(bitree *)malloc(sizeof(bitree)); Bt-data=c; Bt-lchild=crt_bt_pre(bt-lchild); Bt-rchild=crt_bt_pre(bt-rchild); } Return(bt); } 2、设计思想 建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。 关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。 操作：（1）令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针rear指向当前输入的结点，初始：front=1,rear=0; （2）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。 （3）若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。 二叉树的中序线索化算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。 结点插入算法：由线索二叉树的定义易知插入的节点定是个叶子节点，需注意线索的修改，可分为两种情况： 1）：插入的节点t是右儿子，t的中序后继是其父亲的中序后继，中序前驱是其父亲。 2）：插入的节点t是左儿子，t的中序前驱是其父亲的中序前驱，中序后继是其父亲。 结点删除算法：删除的情况与有哪些信誉好的足球投注网站二叉树的删除的类似 1）：删除的节点p是叶子节点，直接删除，修改其父亲的线索。 2）：删除的节点p有一个儿子，p有一个左儿子，以p为根的左子树中的具有最大值节点的t中序后继是p的中序后继，中序前驱不变；p有一个右儿子，以p为根的右子中的具有最小值节点t中序前驱是p的中序前驱，中序后继不变。 3）：删除的节点p有二个儿子，转化为叶子节点或只有一个儿子节点的删除。 3、流程图 详细设计和编码 1、主函数 void main() { Bithptr *T; int i; //system(color 1a); T=CreatTree(); printf(\n); i=1; while(i) { printf(\t1 进行二叉树线索化\n); printf(\t2 进行插入操作\n); printf(\t3 进入删除操作\n); printf(\t4 中序输出\n); printf(\t5 线索输出\n); printf