线索二叉树的创建及遍历.doc

实验九 线索二叉树的创建及遍历实验目的：掌握二叉树的线索链表存储结构，能够实现二叉树的线索链表的创建、遍历等基本操作实验要求：1、认真阅读和掌握教材上和本实验相关的内容及算法2、上机将线索二叉树的线索链表存储表示的创建和遍历算法实现。3、进行简单的输入输出验证。实验内容：编程实现二叉树的线索链表存储表示的基本操作，这些基本操作包括：线索二叉树的创建、线索二叉树的中序遍历算法的实现。要求对程序中的一些关键语句要有注释，并能够进行简单的输入输出验证。参考代码#include #include #define OVERFLOW 0/线索二叉树的二叉链表存储定义typedef enum PointerTag LINK=0,THREAD=1;struct BiThrNodechar data;struct BiThrNode * lchild, * rchild;PointerTag LTag, RTag;typedef struct BiThrNode BiThrNode;typedef BiThrNode * BiThrTree;/* 按先序次序输入二叉树中的结点的值（一个字符）构造二叉链表表示的二叉树，* 字符#表示空树。* * 例如，一棵二叉树的三种遍历次序为：* 先序：-+a*b-cd/ef 中序：a+b*c-d-e/f 后序：abcd-*+ef/* 程序中应该输入：-+a#*b#-c#d#/e#f#* * 又如，一棵二叉树的三种遍历次序为：* 先序：ABDFGCEH 中序：BFDGACHE 后序：FGDBHECA* 程序中应该输入：AB#DF#G#C#EH#*/void CreateBiTree(BiThrTree &T)char ch;ch = getchar();if (ch=#) T=NULL;elseif (!(T = (BiThrNode *)malloc(sizeof(BiThrNode) exit(OVERFLOW);T-data = ch;T-LTag = LINK;T-RTag = LINK;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return;/CreateBiTreevoid PrintBiTree(BiThrTree T)/按中序遍历次序输出二叉树T中的结点的值（一个字符），二叉树T用二叉链表存储。if (T) PrintBiTree(T-lchild);printf(%c,T-data);/coutdata;PrintBiTree(T-rchild);return;/PrintBiTreevoid InThreading(BiThrTree p,BiThrNode * &pre)if (p)InThreading(p-lchild,pre);if (!p-lchild)p-LTag = THREAD;p-lchild = pre;if (!pre-rchild)pre-RTag = THREAD;pre-rchild = p;pre = p;InThreading(p-rchild,pre);/InThreadingvoid InOrderThreading(BiThrTree & ThrT, BiThrTree T)/中序遍历二叉树T，并将其中序线索化，ThrT指向头结点。BiThrNode * pre;if (!(ThrT = (BiThrNode *)malloc(sizeof(BiThrNode) exit(OVERFLOW);ThrT-LTag = LINK;ThrT-RTag = THREAD;ThrT-rchild = ThrT;if (!T) ThrT-lchild = ThrT;elseThrT-lchild = T;pre = ThrT;InThreading(T,pre);pre-rchild = ThrT;pre-RTag = THREAD;ThrT-rchild = pre;return;/InOrderThreadingvoid InOrderTraverse_Thr(BiThrTree T)/T指向头结点，头结点的左链lchild指向根结点，可参见线索化算法。/中序遍历二叉线索树T的非递归算法，输出每个元素。BiThrNode *p;p = T-lchild;while (p != T)while (p-LTag = LINK) p = p-lchild;printf(%c,p-data);/cout data;while (p-RTag = THREAD & p-rchild != T)p = p-rchild;printf(%c,p-data);/cout data;p = p-rchild;return;/InOrderTraverse_Thrvoid main()BiThrTree T=NULL;BiThrTree ThrT=NULL;printf(请按先序顺序输入二叉树中的结点（其中，#表示空树）：n);CreateBiTree(T);printf(中序遍历该二叉树得到的序列为：n);PrintBiTree(T);printf(nn);printf(开始对该二叉树进行中序线索化.n);InOrderThread