线索化二叉树的实现.doc

目 录 1 课题描述 1 2 任务分析 2 3 逻辑设计及描述 3 3.1二叉树的存储 3 3.2 二叉树的遍历 4 3.3 二叉树的线索化 4 3.4 线索化二叉树的遍历 7 3.5 主函数 10 4 程序编码 12 总结 21 参考文献 22 1 课题描述 本程序重在设计二叉树的各种线索化实现，以C语言作为编程语言，实现对二叉树的先、中、后三种序列的线索化。旨在使用户在使用过程中能直接调用各种所需函数，以及了解二叉树的各种线索化过程。其中各函数分别为： BiThrTree CreateBiTree()；//创建二叉树; BiThrTree CopyBiTree(BiThrTree rt)//复制一棵二叉树; void PreOrderTraverse(BiThrTree T)//先序遍历二叉树; void InOrderTraverse(BiThrTree T) //中序遍历二叉树; void PostOrderTraverse(BiThrTree T)//后序遍历二叉树; bool PreOrderThreading(BiThrTree Thrt, BiThrTree T)//先序线索化二叉树; void PreThreading(BiThrTree p)//先序搜索结点的建立; bool InOrderThreading(BiThrTree Thrt, BiThrTree T)//中序线索化二叉树; void InThreading(BiThrTree p)//中序搜索结点的建立; void backThreading(BiThrTree p)//后序搜索结点的建立; BiThrTree backorderThreading(BiThrTree rt)//后序线索化二叉树; BiThrTree parent(BiThrTree thrt,BiThrTree p)//查找结点 void PreOrderTraverse_Thr(BiThrTree Thrt)//遍历先序线索化二叉树; void InOrderTraverse_Thr(BiThrTree Thrt)//遍历中序线索化二叉树; void backorderTraver(BiThrTree Thrt)//遍历后序线索化二叉树; void InOrder_Thr_T(BiThrTree Thrt,BiThrTree T)//将线索化后的二叉树还原; 开发工具：C语言 运行环境：Visual c++6.0。 2 任务分析 这是一个能对二叉树线索化的程序，其中包括对二叉树的先序、中序、后序线索化，最后遍历线索化并输出遍历结果。其中线索化要实现对同一个树的线索化，即应具备还原线索化后二叉树的程序，并重新对二叉树线索化。主要的功能模块流程图如图2.1所示。 图 2.1 模块流程图 3 逻辑设计及描述 3.1二叉树的存储 1.创建二叉树（ CreateBiTree(T) 图 3.1 CreateBiTree(T ) 创建二叉树 图 3.2 CopyBiTree(rt) 复制一棵二叉树 2.复制二叉树（CopyBiTree(rt)）BiThrTree CopyBiTree(BiThrTree rt){ BiThrTree tree;if(rt==NULL) tree=NULL; else{ if(!(tree=(BiThrTree)malloc(sizeof(BiThrNode)))) return 0; tree-data=rt-data;//复制结点 tree-LTag=rt-LTag;tree-RTag=rt-RTag;//复制左右标志域 tree-lchild=CopyBiTree(rt-lchild); tree-rchild=CopyBiTree(rt-rchild);//复制左右孩子} return tree;} void PreOrderTraverse(BiThrTree T){//前序遍历 if (T!=NULL){printf(%c ,T-data); /*访问根结点*/ PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); }} 图 PreOrderTraverse(T) 先序遍历二叉树 图PreOrderThreading(Thrt,T) 先序线索化二叉树 （PreOrderThreading(Thrt,T)） 图 3.5 PreThreading(p) 先序搜索结点的建立 图3.6 InThre