小甲鱼线索二叉树代码

梅祥

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef char ElemType;
   
5. 
   
6. // 线索存储标志位
   
7. // Link(0):表示指向左右孩子的指针
   
8. // Thread(1):表示指向前驱后继的线索
   
9. typedef enum {Link, Thread} PointerTag;
   
10. 
    
11. 
    
12. 
    
13. typedef struct BiThrNode
    
14. {
    
15.     char data;
    
16.     struct BiThrNode *lchild,*rchild;
    
17.     PointerTag ltag;
    
18.     PointerTag rtag;
    
19. } BiThrNode,*BiThrTree;
    
20. 
    
21. 
    
22. // 定义一个全局变量表示刚刚走过的节点
    
23. BiThrTree pre;
    
24. 
    
25. // 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
    
26. void CreateBiThrTree(BiThrTree *T) {
    
27.     char c;
    
28.     scanf("%c",&c);
    
29. 
    
30.     if ( ' ' == c ){
    
31.         *T = NULL;
    
32.     }else {
    
33.         *T = (BiThrNode *)malloc(sizeof(BiThrNode));
    
34.         (*T)->data = c;
    
35.         (*T)->ltag = Link;
    
36.         (*T)->rtag = Link;
    
37. 
    
38.         CreateBiThrTree(&(*T)->lchild);
    
39.         CreateBiThrTree(&(*T)->rchild);
    
40.     }
    
41. }
    
42. 
    
43. // 中序遍历线索化
    
44. 
    
45. void InThreading(BiThrTree T){
    
46.     if ( T ) {
    
47.         InThreading(T->lchild);  // 递归左孩子线索化
    
48. 
    
49.         if( !T->lchild ){
    
50.             T->ltag = Thread;
    
51.             T->lchild = pre;
    
52.         }
    
53.         if ( !pre->rchild ){
    
54.             pre->rtag = Thread;
    
55.             pre->rchild = T;
    
56.         }
    
57.         pre = T;
    
58.         InThreading(T->rchild);  // 递归右孩子线索化
    
59.     }
    
60. }
    
61. 
    
62. // 初始化一个头指针
    
63. void InOrderThreading( BiThrTree *p, BiThrTree T){
    
64.     *p = (BiThrNode *)malloc(sizeof(BiThrNode));
    
65.     (*p)->ltag = Link;
    
66.     (*p)->rtag = Link;
    
67.     (*p)->rchild = *p;
    
68.     if (!T) {
    
69.         (*p)->lchild = *p;
    
70.     }else {
    
71.         (*p)->lchild = T;
    
72.         pre = *p;
    
73.         InThreading(T);
    
74.         pre->rchild = *p;
    
75.         pre->rtag = Thread;
    
76.         (*p)->rchild = pre;
    
77.     }
    
78. }
    
79. 
    
80. void visit (char c){
    
81.     printf("%c",c);
    
82. }
    
83. // 中序遍历二叉树，迭代
    
84. void InOrderTraverse( BiThrTree T ) {
    
85.     BiThrTree p;
    
86.     p = T->lchild;
    
87. 
    
88.     while( p!=T ){
    
89.         while( p->ltag == Link ){
    
90.             p = p->lchild;
    
91.         }
    
92.         visit(p->data);
    
93. 
    
94.         while( p->rtag == Thread && p->rchild !=T ){
    
95.             p = p->rchild;
    
96.             visit(p->data);
    
97.         }
    
98.         p = p->rchild;
    
99.     }
    
100. 
     
101. 
     
102. }
     
103. int main()
     
104. {
     
105.     BiThrTree P,T = NULL;
     
106. 
     
107.     CreateBiThrTree( &T );
     
108. 
     
109.     InOrderThreading( &P, T );
     
110. 
     
111.     printf("中序遍历二叉树的结果为：");
     
112. 
     
113.     InOrderTraverse( P );
     
114. 
     
115.     printf("\n");
     
116. 
     
117.     return 0;
     
118. }

复制代码

Eugene21

谢谢！

挽星

Eugene21 发表于 2021-3-13 10:51
谢谢！

第66行应该是(*p)->rtag = Thread;