本文实例为大家分享了C语言递归实现线索二叉树的具体代码，供大家参考，具体内容如下
描述：将二叉树中结点的空左孩子指针域指向前驱结点，将空的右孩子指针域指向后继结点。
code:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode *lchild, *rchild;
int ltag, rtag;
}Tree,*BTree;
BTree Build_Tree(void) {
BTree T;
char ch;
scanf("%c", &ch);
if (ch == '#') {
T = NULL;
}
else {
T = (BTree)malloc(sizeof(Tree));
T->data = ch;
T->ltag = 0;
T->rtag = 0;
T->lchild = Build_Tree();
T->rchild = Build_Tree();
}
return T;
}
//先序线索化
void Pre_Thread(BTree cur, BTree *pre) {
if (cur && cur->ltag==0) {
printf("%c ", cur->data);
if (cur->lchild == NULL) {
cur->lchild = *pre;
(*pre)->ltag = 1;
cur->ltag = 1;
}
if (cur->rchild == NULL) {
cur->rtag = 1;
}
if (*pre && (*pre)->rtag == 1) {
(*pre)->rchild = cur;
}
*pre = cur;
Pre_Thread(cur->lchild, pre);
Pre_Thread(cur->rchild, pre);
}
}
//中序线索化
void In_Thread(BTree cur, BTree *pre) {
if (cur) {
In_Thread(cur->lchild, pre);
printf("%c ", cur->data);
if (cur->lchild==NULL) {
cur->lchild = *pre;
cur->ltag = 1;
}
if (cur->rtag == NULL) {
cur->rtag = 1;
}
if (*pre && (*pre)->rtag == 1) {
(*pre)->rchild = cur;
}
*pre = cur;
In_Thread(cur->rchild, pre);
}
}
//后序线索化
void Post_Thread(BTree cur, BTree *pre) {
if (cur) {
Post_Thread(cur->lchild, pre);
Post_Thread(cur->rchild, pre);
printf("%c ", cur->data);
if (cur->lchild == NULL) {
cur->lchild = *pre;
cur->ltag = 1;
}
if (cur->rchild == NULL) {
cur->rtag = 1;
}
if (*pre && (*pre)->rtag == 1) {
(*pre)->rchild = cur;
}
*pre = cur;
}
}
int main(void) {
BTree T,p=NULL;
T = Build_Tree();
Pre_Thread(T, &p);
//In_Thread(T, &p);
//Post_Thread(T, &p);
return 0;
}
|
跑时分别运行前序、中序、后序线索化。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://blog.csdn.net/chendongqaq/article/details/72770468