线索化二叉树的实现..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所示。 图 3.1 CreateBiTree(T ) 创建二叉树 图 3.2 CopyBiTree(rt) 复制一棵二叉树 2.复制二叉树（CopyBiTree(rt)）设计思想：该函数的功能主要是为了避免前后两次的线索化混乱，其实质是重建二叉树以方便下一次的线索化。复制的方法无外乎将各个结点拷贝至另一棵树，因为是完全一样的二叉树,所以连左右标志域也要一起复制,结点位置不能发生任何变化。设计流程如图3.2所示，算法如算法3.1所示。 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;} 算法3.1 3.2 二叉树的遍历 1. 先、中、后遍历二叉树，因为三种遍历方法的区别只是将输出结点的位置调换一下就可以实现，所以在此只列举