虚心请教，对于线索二叉树的一些问题

ByTime

问题为:

不知道怎么把线索为1的前后驱元素的地址放在对应的指针区域中

例如下面的二叉树:

                        A
                B                E
         C          D                        F


就是不知道怎么把C的后驱元素的地址指针指向B   D的前驱元素指向B  后驱指向A  。。。。

希望能有大佬可以完善一下代码，或者讲一下方法，我再去琢磨一下

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. typedef char TYPE;
   
4. 
   
5. //线索为0为孩子节点
   
6. //线索为1为前后驱线索
   
7. typedef struct tree
   
8. {
   
9. 
   
10.         struct tree *left;
    
11.         char clue_left;//左
    
12.         TYPE data;
    
13.         char clue_right;//右
    
14.         struct tree *right;
    
15. 
    
16. }clue_pot,*tree;
    
17. 
    
18. inclute_tree(tree *p)
    
19. {
    
20.         char c;
    
21.         scanf("%c",&c);
    
22.         if(c==' ')
    
23.         {
    
24.                 *p = NULL;
    
25.         }
    
26.         else
    
27.         {
    
28. 
    
29.         *p = (clue_pot *)malloc(sizeof(clue_pot));
    
30.         (*p)->data = c;
    
31.                 (*p)->clue_left = '0';
    
32.                 (*p)->clue_right = '0';
    
33.         inclute_tree(&(*p)->left);
    
34.         inclute_tree(&(*p)->right);
    
35.         }
    
36. }
    
37. 
    
38. 
    
39. change_tree(clue_pot *head)
    
40. {
    
41.        
    
42.         if( head != NULL)
    
43.         {
    
44. 
    
45.                 if(change_tree(head->left)==1)
    
46.                 {
    
47.                        
    
48. 
    
49.                         head->clue_left='1';
    
50. 
    
51. 
    
52.                 }
    
53.        
    
54. 
    
55. 
    
56.                 if(change_tree(head->right)==1)
    
57.                 {
    
58.                         head->clue_right='1';
    
59.                         head->right = pre->left;
    
60.                 }
    
61.                
    
62.         }
    
63.         else
    
64.         {
    
65.                 return 1;
    
66.         }
    
67. }
    
68. 
    
69. check_tree(tree root,int numb)
    
70. {
    
71.     if(root != NULL)
    
72.     {
    
73.         printf("%c在第%d层\n",root->data,numb);
    
74.         printf("左线索:%c,左边指针地址:%p,本身地址:%p,右线索:%c,右边指针地址:%p\n",root->clue_left,root->left,root,root->clue_right,root->right);
    
75.         check_tree(root->left,numb+1);
    
76.         check_tree(root->right,numb+1);
    
77.     }
    
78. }
    
79. 
    
80. int main()
    
81. {
    
82.         tree test=NULL;
    
83.         inclute_tree(&test);
    
84.         change_tree(test);
    
85.         check_tree(test,1);
    
86.         return 0;
    
87. 
    
88. }

复制代码

ByTime

琢磨一晚上了

ByTime

自己琢磨出来了，代码分享一下，做了挺多注释的

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. typedef char TYPE;
   
4. 
   
5. //线索为0为孩子节点
   
6. //线索为1为前后驱线索
   
7. typedef struct tree
   
8. {
   
9. 
   
10.         struct tree *left;//存放左下节点的地址
    
11.         char clue_left;//如果左下还有节点，值为0，代表当前为左下的父节点，left存放的为下一个节点地址；如果左下为空，值为1。当值为1时候按中序排序left存放上一个节点地址
    
12.         TYPE data;//储存节点存放的信息
    
13.         char clue_right;//如果右下还有节点，值为0，代表当前为右下的父节点，left存放的为下一个节点地址；如果左下为空，值为1。当值为1时候按中序排序left存放上一个节点地址
    
14.         struct tree *right;//存放右下节点的地址
    
15. 
    
16. }clue_pot,*tree;//定义一个树的节点；定义一个指向树的节点的指针
    
17. 
    
18. 
    
19. //初始化二叉树，递归方法
    
20. //用前序输入  空格代表没有下一个节点
    
21. inclute_tree(tree *p)
    
22. {
    
23.         char c;
    
24.         scanf("%c",&c);
    
25.         if(c==' ')
    
26.         {
    
27.                 *p = NULL;
    
28.         }
    
29.         else
    
30.         {
    
31. 
    
32.         *p = (clue_pot *)malloc(sizeof(clue_pot));
    
33.         (*p)->data = c;
    
34.                 (*p)->clue_left = '0';
    
35.                 (*p)->clue_right = '0';
    
36.         inclute_tree(&(*p)->left);
    
37.         inclute_tree(&(*p)->right);
    
38.         }
    
39. }
    
40. 
    
41. tree pre; //定义一个全局变量（指向二叉树节点的指针类型）
    
42. //如果线索为0的话 在叶子层的左右指针要按 中序排序 指回上一个节点，此时pre的作用就来了
    
43. //作用：用于递归到最后一层时把最后一层节点赋值到这，结束后回到上一层时，此时操作这个变量（最后一层节点）的右节点指针指向当前节点（从最后一层回退）的地址
    
44. 
    
45. 
    
46. tree two;
    
47. 
    
48. change_tree(clue_pot *head)
    
49. {
    
50. 
    
51.         if( head != NULL)
    
52.         {
    
53.                 //首先递归到最左下角的树节点
    
54.                 if(change_tree(head->left)==1)
    
55.                 {               
    
56.                         head->clue_left='1';
    
57.                         head->left = pre;
    
58.                 }
    
59. 
    
60.                 if(pre->right==NULL)
    
61.                 {
    
62.                         pre->right = head;
    
63.                         pre = head;
    
64.                 }
    
65.                 pre = head;
    
66.                 if(change_tree(head->right)==1)
    
67.                 {
    
68.                         head->clue_right='1';
    
69.                 }
    
70.         }
    
71.         else
    
72.         {
    
73.                 return 1;
    
74.         }
    
75. }
    
76. 
    
77. check_tree(tree root,int numb)
    
78. {
    
79.     if(root != NULL)
    
80.     {
    
81.                
    
82.         printf("%c在第%d层\n",root->data,numb);
    
83.                 printf("左线索:%c,左边指针地址:%p,本身地址:%p,右线索:%c,右边指针地址:%p\n",root->clue_left,root->left,root,root->clue_right,root->right);
    
84.                 if(root->clue_left=='1'&&root->clue_right=='1')
    
85.                         return 0;
    
86.                 getchar();
    
87.         check_tree(root->left,numb+1);
    
88.         check_tree(root->right,numb+1);
    
89.     }
    
90. }
    
91. 
    
92. 
    
93. //迭代查询二叉树
    
94. //打印则为按照中序排序的顺序进行打印
    
95. check_tree2(tree root,tree end)
    
96. {
    
97.         while(root->left != end)
    
98.         {
    
99.                 root = root->left;
    
100.         }
     
101.        
     
102.         //循环出来  root 为左边最末的节点
     
103. 
     
104.         while(root != NULL)
     
105.         {
     
106.                 printf("左线索:%c,左边指针地址:%p,本身地址:%p,data内容:%c,右线索:%c,右边指针地址:%p\n",root->clue_left,root->left,root,root->data,root->clue_right,root->right);
     
107.                 root = root->right;
     
108.         }
     
109. }
     
110. 
     
111. 
     
112. 
     
113. 
     
114. int main()
     
115. {
     
116.         tree test=NULL;
     
117.         inclute_tree(&test);
     
118.         two = (clue_pot *)malloc(sizeof(clue_pot));
     
119.         two->left = test;
     
120.         two->right = two;
     
121.         two->clue_right='0';
     
122.         pre = two;
     
123.         change_tree(test);
     
124.         pre->left = two;
     
125.         check_tree2(test,two);
     
126.         return 0;
     
127. 
     
128. }

复制代码