5677: 数据结构实验：二叉树线索化

二叉树遍历时，需要多次的压栈和出栈过程，效率比较低。对二叉树进行线索化可以有效解决此问题。

每一棵二叉树上，很多结点都含有未使用的指向NULL的指针域。二叉树线索化时：

如果结点有左子树，则 left 指针域指向左孩子，否则 left 指针域指向该结点的直接前趋；

如果结点有右子树，则 right 指针域指向右孩子，否则 right 指针域指向该结点的直接后继。

为了避免指针域指向的结点的意义混淆，需要改变结点本身的结构，增加两个标志域，最终结构如下：

typedef struct BNode

{

int data;

struct BNode* left, *right;

int lTag, rTag;//0表示有孩子，1表示无孩子

}BNode;

后台已经完成了二叉树的创建，以及对线索化后的二叉树进行中序遍历。你需要补充完成二叉树中序线索化函数：

void InThreading(BNode* p);//主函数会调用此函数并将p指向根节点

输入

单组数据，占一行，代表一棵二叉树。结点均为正整数，数据为0代表当前结点为空，数据为-1代表二叉树数据输入结束，-1不作处理。二叉树的构造按照层次顺序（即第1层1个整数，第2层2个，第3层4个，第4层有8个......，如果某个结点不存在以0代替）。

输出

输出中序遍历二叉树得到的序列，每个结点之前空一格。

样例输入

1 2 0 3 4 -1

样例输出

3 2 4 1

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 typedef struct BNode
 6 {
 7 int data;
 8 struct BNode* left, *right;
 9 int lTag, rTag;//0表示有孩子，1表示无孩子
10 }BNode;
11 
12 struct BNode *pre;  //全局变量pre为空
13 
14 
15 void InThreading(struct BNode* p)
16 {
17     if(p){
18         InThreading(p->left);
19         if(p->left==NULL){
20             p->lTag=1;
21             p->left=pre;
22         }
23         if(pre&&pre->right==NULL){
24             pre->rTag=1;
25             pre->right=p;
26         }
27         pre=p;
28         InThreading(p->right);
29     }
30 }
31 
32 BNode* Creattree()
33 {
34     struct BNode *A[105];
35     struct BNode *u,*root;
36     root=(struct BNode*)malloc(sizeof(struct BNode));
37     int num,jishu=0,flag=0;
38     while(scanf("%d",&num)&&num!=-1)
39     {
40         if(flag==0){
41             if(num==0){
42                 root=NULL;
43             }
44             else{
45                 root->data=num;
46                 root->left=NULL;
47                 root->right=NULL;
48                 root->lTag=0;
49                 root->rTag=0;
50             }
51             A[++jishu]=root;
52             flag=1;
53         }
54         else{
55             u=(struct BNode*)malloc(sizeof(struct BNode));
56             if(num==0){
57                 u=NULL;
58             }
59             else{
60                 u->data=num;
61                 u->left=NULL;
62                 u->right=NULL;
63                 u->lTag=0;
64                 u->rTag=0;
65             }
66             A[++jishu]=u;
67             if(jishu%2==0){
68                 A[jishu/2]->left=u;
69             }
70             else{
71                 A[jishu/2]->right=u;
72             }
73         }
74     }
75     return root;
76 }
77 void InOrderThread(BNode* p)
78 {
79     while(p){
80         while(p->lTag==0){
81             p=p->left;
82         }
83         printf(" %d",p->data);
84         while(p->rTag==1&&p->right!=NULL){
85             p=p->right;
86             printf(" %d",p->data);
87         }
88         p=p->right;
89     }
90 }
91 int main()
92 {
93     BNode *head;
94     head=Creattree();
95     InThreading(head);
96     InOrderThread(head);
97 }

View Code