1 #include<stdio.h>
2 #include<stdlib.h>
3 #define OK 1
4 #define NO 0
5 #define TRUE 1
6 #define FALSE 0
7 #define ERROR -1
8
9 #define MAX_TREE_SIZE 100
//树的最大结点数
10
11 typedef
int Status;
12 typedef
char TElemType_C;
13 typedef
struct CTNode
//孩子结点
14 {
15 int child;
16 struct CTNode *
next;
17 }CTNode;
18 typedef CTNode* ChildPtr;
//孩子结点指针
19 typedef
struct
20 {
21 int parent;
//双亲结点的位置
22 TElemType_C data;
23 ChildPtr firstchild;
//孩子链表头指针
24
25 }CTBox;
26 typedef
struct
27 {
28 CTBox nodes[MAX_TREE_SIZE];
29 int r;
//根的位置
30 int n;
//树的结点数
31 }CTree;
32
33 void InitTree_C(CTree *T);
//构造空树
34
35 void FreeChild_C(ChildPtr *p);
//删除孩子列表
36
37 void ClearTree_C(CTree *T);
//清空树T
38
39 void DestroyTree_C(CTree *T);
//销毁树T
40
41 Status TreeEmpty_C(CTree T);
//判断树是否为空
42
43 Status CreateTree_C(CTree *T);
//按层序序列构造树
44
45 int TreeDegree_C(CTree T);
//返回树的度
46
47 int TreeDepth_C_1(CTree T);
//借助双亲标志
48
49 int TreeDepth_C_1(CTree T);
//不借助双亲标志
50
51 int Depth_C(CTree T,
int i);
//求T中第i个结点开始的深度
52
53 TElemType_C Root_C(CTree T);
//返回树的根节点的值
54
55 TElemType_C Value_C(CTree T,
int i);
//返回树中第i个结点值（按层序计数）
56
57 int Order_C(CTree T,TElemType_C e);
//返回结点e的值位置（在数组中的位置），-1代表无此结点
58
59 Status Assign_C(CTree*T,TElemType_C e,TElemType_C value);
//替换结点e的值为value
60
61 TElemType_C ChildValue_C(CTree T,TElemType_C e,
int order);
//返回结点e的第order个孩子的值（从左到右计数）
62
63 TElemType_C Sibling_C_1(CTree T,TElemType_C e,
int mark);
//返回元素e的左右兄弟，mark标记左右
64
65 int Sibling_C_2(CTree T,TElemType_C e,
int mark);
//返回元素e的左右兄弟序号，mark标记左右
66
67 int ChildCount_C(CTree T,TElemType_C p);
//返回结点p的孩子结点（子树）个数，返回负数代表结点p不存在
68
69 int ChildSeat_C(CTree T,TElemType_C p,
int i);
//返回树T中p结点的第i个孩子（层序计数）的位置，i=0定义为最后一个孩子。
70
71 ChildPtr SiblingSeat_C(CTree T,TElemType_C p);
//返回在孩子链表中指向元素p的指针。
72
73 Status InsertChild_C(CTree *T,TElemType_C p,
int i,TElemType_C e);
//将结点e插入为p结点的第i个孩子（层序计数），i=0定义为最后一个孩子
74
75 Status InsertTree_C(CTree *T,TElemType_C p,
int i,CTree e);
//将树t插入为树T中p结点的第i颗子树，i=0定义为最后一棵树
76
77 Status DeleteTree_C(CTree *T,TElemType_C p,
int i);
//删除树T中p结点的第i棵子树
78
79 void LevelOrderTraverse_C(CTree T);
//层序遍历
80
81 void Print_C_1(CTree T);
//依赖双亲结点信息打印树。
82
83 void ShowTree_C(CTree T);
//展示T的存储结构
84
85
86 int main (
int argc,
char**
argv){
87 CTree T,T0;
88 printf(
"1\n函数InitTree_C测试..\n");
89 {
90 printf(
"初始化一棵空树 T..\n");
91 InitTree_C(&
T);
92 printf(
"\n");
93 }
94 printf(
"5\n函数TreeEmpty_C测试..\n");
95 {
96 TreeEmpty_C(T)?printf(
"T 为空！！"):printf(
"T 不为空！！");
97 printf(
"\n");
98 }
99 printf(
"6\n函数CreateTree_C测试..\n");
100 {
101 CreateTree_C(&
T);
102 printf(
"\n");
103 }
104 printf(
"22\n函数LevelOrderTraverse_C测试..\n");
105 {
106 printf(
"层序遍历树 T=");
107 LevelOrderTraverse_C(T);
108 printf(
"\n");
109 }
110
111
112 return 0;
113 }
114 void InitTree_C(CTree *
T){
115 int i;
116
117 printf(
"录入根节点的位置（非负数）：\n");
118 scanf(
"%d",&
i);
119 if(i<
0||i>MAX_TREE_SIZE-
1)
120 {
121 printf(
" i 值错误！\n");
122 exit(ERROR);
123 }
124 T->r=
i;
125 T->n=
0;
126
127 }
128 Status TreeEmpty_C(CTree T){
129 return (T.n?
FALSE:TRUE);
130
131 }
132
133 Status CreateTree_C(CTree *T){
//去掉getchar什么的一起输入不容易出错
134 TElemType_C ch;
135 int i;
//i标记当前结点的父结点的位置
136 int j;
//j标记当前结点的位置
137 int k;
//k标记i结点的第一个孩子的位置
138 ChildPtr p,q;
//q始终指向child的尾指针
139 printf(
"录入树的根节点-->");
140 getchar();
//抵掉回车
141 scanf(
"%c",&
ch);
142 printf(
"\n");
143 if(ch!=
'^')
144 {
145 i=T->
r;
146 T->nodes[i].parent=-
1;
147 T->nodes[i].data=
ch;
148 T->nodes[i].firstchild=
NULL;
149 T->n++
;
150
151 if(i!=
0)
//设置第二个结点的输入位置
152 j=
0;
153 else
154 j=
1;
155 k=
j;
156 }
157 getchar();
158 printf(
"输入结点\n");
159 scanf(
"%c",&
ch);
160 while(ch!=
'#')
161 {
162 p=q=
NULL;
163 while(
1){
164 scanf(
"%c",&
ch);
165 if(ch==
'^')
166 break;
167 else
168 {
169 T->nodes[j].parent=
i;
170 T->nodes[j].data=
ch;
171 T->nodes[j].firstchild=
NULL;
172 T->n++
;
173
174 p=(ChildPtr)malloc(
sizeof(CTNode));
175 if(!
p)
176 exit(ERROR);
177 p->child=
j;
178 p->next=
NULL;
179 if(T->nodes[i].firstchild==
NULL)
180 T->nodes[i].firstchild=
p;
181
182 else
183 q->next=
p;
184 q=
p;
185 }
186 if(j+
1==T->
r)
187 j=j+
2;
188 else
189 j++
;
190 }
191 i=
k;
192 if(j+
1==T->
r)
193 k=k+
2;
194 else
195 k++
;
196 scanf(
"%c",&
ch);
197 }
198 return OK;
199 }
200
201 void LevelOrderTraverse_C(CTree T){
202 int i,count;
203 count=
0;
204 if(T.n)
205 {
206 count++
;
207 printf(
"%c",T.nodes[T.r].data);
208 if(T.r)
209 i=
0;
210 else
211 i=
1;
212 while(count<
T.n)
213 {
214 if(i!=
T.r)
215 {
216 count++
;
217 printf(
"%c",T.nodes[i].data);
218 }
219 i++
;
220
221 }
222 }
223 }
输入示例
参考http://www.cnblogs.com/kangjianwei101/p/5222014.html
转载于:https://www.cnblogs.com/lovecodepql/p/7695972.html
