一、实验目的
1.理解线索二叉树的存储结构；
2.熟练掌握线索二叉树的生成、遍历等常见操作
二、实验内容及步骤
（一）实验内容
1. 练习线索二叉树的建立与存储
2. 练习线索二叉树的遍历
（二）实验步骤
建立线索二叉树,并通过调用函数，输出中序遍历的结果。
1. #include<iostream> 2. using namespace std; 3. 4. //二叉树的二叉线索类型存储表示 5. typedef struct BiThrNode 6. { 7. char data; 8. struct BiThrNode *lchild,*rchild; 9. int LTag,RTag; 10. }BiThrNode,*BiThrTree; 11. 12. //全局变量pre 13. BiThrNode *pre=new BiThrNode; 14. 15. //用算法5.3建立二叉链表 16. void CreateBiTree(BiThrTree &T) 17. { 18. //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T 19. char ch; 20. cin >> ch; 21. if(ch=='#') T=NULL; //递归结束，建空树 22. else 23. { 24. T=new BiThrNode; 25. T->data=ch; //生成根结点 26. CreateBiTree(T->lchild); //递归创建左子树 27. CreateBiTree(T->rchild); //递归创建右子树 28. } //else 29. } //CreateBiTree 30. 31. //用算法5.7以结点P为根的子树中序线索化 32. void InThreading(BiThrTree p) 33. { 34. //pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索 35. if(p) 36. { 37. InThreading(p->lchild); //左子树递归线索化 38. if(!p->lchild) 39. { //p的左孩子为空 40. p->LTag=1; //给p加上左线索 41. p->lchild=pre; //p的左孩子指针指向pre（前驱） 42. } 43. else 44. p->LTag=0; 45. if(!pre->rchild) 46. { //pre的右孩子为空 47. pre->RTag=1; //给pre加上右线索 48. pre->rchild=p; //pre的右孩子指针指向p（后继） 49. } 50. else 51. pre->RTag=0; 52. pre=p; //保持pre指向p的前驱 53. InThreading(p->rchild); //右子树递归线索化 54. } 55. }//InThreading 56. 57. //用算法5.8带头结点的中序线索化 58. void InOrderThreading (BiThrTree &Thrt,BiThrTree T) 59. { 60. //中序遍历二叉树T，并将其中序线索化，Thrt指向头结点 61. Thrt=new BiThrNode; //建头结点 62. Thrt->LTag=0; //头结点有左孩子，若树非空，则其左孩子为树根 63. Thrt->RTag=1; //头结点的右孩子指针为右线索 64. Thrt->rchild=Thrt; //初始化时右指针指向自己 65. if(!T) Thrt->lchild=Thrt; //若树为空，则左指针也指向自己 66. else 67. { 68. Thrt->lchild=T; pre=Thrt; //头结点的左孩子指向根，pre初值指向头结点 69. InThreading(T); //调用算法5.7，对以T为根的二叉树进行中序线索化 70. pre->rchild=Thrt; //算法5.7结束后，pre为最右结点，pre的右线索指向头结点 71. pre->RTag=1; 72. Thrt->rchild=pre; //头结点的右线索指向pre 73. } 74. } //InOrderThreading 75. 76. void InOrderTraverse_Thr(BiThrTree T) 77. { BiThrNode *p; 78. //T指向头结点，头结点的左链lchild指向根结点，可参见线索化算法5.8。 79. //中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出 80. p=T->lchild; 81. while(p!=T) 82. { 83. while(p->LTag==0) p=p->lchild; 84. cout<<p->data; 85. while(p->RTag==1&&p->rchild!=T) 86. { 87. p=p->rchild;cout<<p->data; 88. } 89. p=p->rchild; 90. }} 91. int main() 92. { 93. pre->RTag=1; 94. pre->rchild=NULL; 95. BiThrTree tree,Thrt; 96. cout<<"请输入建立二叉链表的序列：\n"; 97. CreateBiTree(tree); 98. InOrderThreading(Thrt,tree); 99. cout<<"中序遍历线索二叉树的结果为：\n"; 100. InOrderTraverse_Thr(Thrt); 101. cout<<endl; 102. return 0; 103. }
