K叉树的运算

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #define K 4   //树的最大分叉数
  4 
  5 struct TreeNode   //表示K叉树节点的结构体类型
  6 {
  7     int data;    //节点数据域
  8     struct TreeNode *Link[K];  //节点指针域,结构体指针数组
  9 };
 10 typedef struct TreeNode TreeNode1;
 11 
 12 struct Path    //遍历K叉树过程中链表栈的节点
 13 {
 14     TreeNode1 *current;  //指向链表节点代表的K叉树节点的指针
 15     int direction;   //指向由链表节点代表的K叉树节点的下一个节点的Link数组元素的下标加一后的值
 16     struct Path *pnext, *pbefore;   //双向链表的左链指针和右链指针
 17 };
 18 typedef struct Path Path1;
 19 
 20 int ComputeLeaf(TreeNode1 *root, int *depth);   //计算K叉树叶子数目和深度的函数
 21 int Search(TreeNode1 *ptr, int d); //寻找ptr指向的K叉树节点上从d开始下一可走方向
 22 int Enable(TreeNode1 *ptr, int m);  //判定在ptr指向的K叉树节点上方向m是否可走
 23 
 24 void main()
 25 {
 26     int i, depth;   //depth为K叉树深度
 27     TreeNode1 *temp1, *temp2;                       //创建4叉树
 28     TreeNode1 *root=(TreeNode1 *) malloc(sizeof(TreeNode1));
 29     root->data=0;
 30     root->Link[0]=NULL;
 31     for(i=1; i<=3; i++)
 32     {
 33         root->Link[i]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 34         root->Link[i]->data=i;
 35     }
 36 
 37     for (i=1; i<=4; i++)
 38         root->Link[1]->Link[i-1]=NULL;
 39 
 40     temp1=root->Link[2];
 41     for (i=1; i<=4; i++)
 42     {
 43         temp1->Link[i-1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 44         temp1->Link[i-1]->data=i+3;
 45     }
 46 
 47     temp2=temp1->Link[0];
 48     temp2->Link[1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 49     temp2->Link[1]->data=10;
 50     for (i=1; i<=4; i++)
 51         temp2->Link[1]->Link[i-1]=NULL;
 52 
 53     temp2->Link[3]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 54     temp2->Link[3]->data=11;
 55     for (i=1; i<=4; i++)
 56         temp2->Link[3]->Link[i-1]=NULL;
 57     temp2->Link[0]=temp2->Link[2]=NULL;
 58 
 59     temp2=temp1->Link[2];
 60     temp2->Link[2]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 61     temp2->Link[2]->data=12;
 62     for (i=1; i<=4; i++)
 63         temp2->Link[2]->Link[i-1]=NULL;
 64     temp2->Link[0]=temp2->Link[1]=temp2->Link[3]=NULL;
 65 
 66     temp2=temp1->Link[1];
 67     for (i=1; i<=4; i++)
 68         temp2->Link[i-1]=NULL;
 69 
 70     temp2=temp1->Link[3];
 71     for (i=1; i<=4; i++)
 72         temp2->Link[i-1]=NULL;
 73 
 74     temp1=root->Link[3];
 75     temp1->Link[1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 76     temp2=temp1->Link[1];
 77     temp2->data=8;
 78     for (i=1; i<=4; i++)
 79         temp2->Link[i-1]=NULL;
 80 
 81     temp1->Link[3]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 82     temp2=temp1->Link[3];
 83     temp2->data=9;
 84     for (i=1; i<=4; i++)
 85         temp2->Link[i-1]=NULL;
 86 
 87     temp1->Link[0]=temp1->Link[2]=NULL;
 88 
 89     printf ("K叉树的叶子结点数目为%d\n", ComputeLeaf(root, &depth));   //计算叶子数目和深度，输出叶子数目
 90     printf ("K叉树的深度为%d\n", depth-1);   //输出深度
 91 }
 92 
 93 int ComputeLeaf(TreeNode1 *root, int *depth)
 94 {
 95     int i;
 96 
 97     for (i=1; i<=K; i++)
 98     {
 99         if (root->Link[i-1]!=NULL)
100             break;
101     }
102 
103     if (i>K)    //K叉树为只有根节点的空树
104     {
105         *depth=0;  
106         return 1;   //深度为0,叶子数为1
107     }
108     else
109     {
110         int d, k, flag;   //d为当前方向,k为K叉树层数
111         int count;   //计数变量，统计叶子数目
112         TreeNode1 *ptr, *interval;   //ptr指向遍历过程中的当前节点
113 
114         ptr=root;  //ptr初始化，指向根节点
115         d=0;  //方向初始化为0
116         count=0;  //计数变量初始化
117         k=1;    //层数初始化
118         flag=0;
119 
120         Path1 *psnewbe, *psnewaf, *head, *current;  
121         head=(Path1 *) malloc(sizeof(Path1));  
122         psnewbe=head;                         //路径链表初始化
123         psnewaf=head;             
124         head->pnext=NULL;  
125         head->pbefore=NULL;
126         while(1)
127         {
128             if (Search(ptr, d)==0)
129             {
130                 if (ptr==root)   //在根节点无下一可走方向，遍历结束，退出循环
131                     break;
132                 else
133                 {
134                     if (d==0)    //找到一个叶子
135                     {
136                         count++;   //计数变量加一
137                         if (flag==0)
138                         {
139                             *depth=k;
140                             flag=1;             //通过比较确定叶子深度最大值，求出K叉树深度
141                         }
142                         else
143                         {
144                             if (*depth<k)
145                                 *depth=k;
146                         }
147                         k--;
148                         ptr=psnewaf->current;    //回溯
149                         d=psnewaf->direction;
150                         continue;
151                     }
152                     else
153                     {
154                         k--;
155                         free(psnewaf);
156                         psnewbe->pnext=NULL;  
157                         psnewaf=psnewbe;                   
158                         psnewbe=psnewbe->pbefore;  //回溯
159                         ptr=psnewaf->current;
160                         d=psnewaf->direction;
161                         continue;
162                     }
163                 }
164             }
165             else
166             {
167                 if (d==0)
168                 {
169                     current=(Path1 *) malloc(sizeof(Path1));  //找到下一个节点，当前节点加入路径链表
170                     current->current=ptr;
171                     current->direction=Search(ptr, d);
172                     interval=ptr->Link[current->direction-1];
173                     current->pnext=NULL;  
174                     psnewaf->pnext=current;  
175                     current->pbefore=psnewaf;              
176                     psnewbe=psnewaf;  
177                     psnewaf=current; 
178                 }
179                 else
180                 {
181                     psnewaf->direction=Search(ptr, d);     //在当前节点找到新方向，更新当前节点方向
182                     interval=ptr->Link[psnewaf->direction-1];
183                 }
184 
185                 ptr=interval;    //递进至下一节点
186                 d=0;
187                 k++;
188                 continue;
189             }
190         }
191         return count;   //返回叶子总数
192     }
193 }
194 
195 int Search(TreeNode1 *ptr, int d)
196 {
197     int m=d;
198     for(m++; m<=K; m++)
199     {
200         if (Enable(ptr, m)==1)
201             return m;
202     }
203     return 0;
204 }
205 
206 int Enable(TreeNode1 *ptr, int m)
207 {
208     if (ptr->Link[m-1]!=NULL)
209         return 1;
210     else
211         return 0;
212 }

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #define K 4
  4 
  5 struct TreeNode
  6 {
  7     int data;
  8     struct TreeNode *Link[K];
  9 };
 10 typedef struct TreeNode TreeNode1;
 11 
 12 struct Path
 13 {
 14     TreeNode1 *current;
 15     int direction;
 16     struct Path *pnext, *pbefore;
 17 };
 18 typedef struct Path Path1;
 19 
 20 int ComputeLeaf(TreeNode1 *root, int m);  //函数，求第m层节点总数
 21 int Search(TreeNode1 *ptr, int d);
 22 int Enable(TreeNode1 *ptr, int m);
 23 
 24 void main()
 25 {
 26     int i, m;   //m指定要搜索结点数目的层数
 27     TreeNode1 *temp1, *temp2;
 28     TreeNode1 *root=(TreeNode1 *) malloc(sizeof(TreeNode1));
 29     root->data=0;
 30     root->Link[0]=NULL;
 31     for(i=1; i<=3; i++)
 32     {
 33         root->Link[i]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 34         root->Link[i]->data=i;
 35     }
 36 
 37     for (i=1; i<=4; i++)
 38         root->Link[1]->Link[i-1]=NULL;
 39 
 40     temp1=root->Link[2];
 41     for (i=1; i<=4; i++)
 42     {
 43         temp1->Link[i-1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 44         temp1->Link[i-1]->data=i+3;
 45     }
 46 
 47     temp2=temp1->Link[0];
 48     temp2->Link[1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 49     temp2->Link[1]->data=10;
 50     for (i=1; i<=4; i++)
 51         temp2->Link[1]->Link[i-1]=NULL;
 52 
 53     temp2->Link[3]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 54     temp2->Link[3]->data=11;
 55     for (i=1; i<=4; i++)
 56         temp2->Link[3]->Link[i-1]=NULL;
 57     temp2->Link[0]=temp2->Link[2]=NULL;
 58 
 59     temp2=temp1->Link[2];
 60     temp2->Link[2]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 61     temp2->Link[2]->data=12;
 62     for (i=1; i<=4; i++)
 63         temp2->Link[2]->Link[i-1]=NULL;
 64     temp2->Link[0]=temp2->Link[1]=temp2->Link[3]=NULL;
 65 
 66     temp2=temp1->Link[1];
 67     for (i=1; i<=4; i++)
 68         temp2->Link[i-1]=NULL;
 69 
 70     temp2=temp1->Link[3];
 71     for (i=1; i<=4; i++)
 72         temp2->Link[i-1]=NULL;
 73 
 74     temp1=root->Link[3];
 75     temp1->Link[1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 76     temp2=temp1->Link[1];
 77     temp2->data=8;
 78     for (i=1; i<=4; i++)
 79         temp2->Link[i-1]=NULL;
 80 
 81     temp1->Link[3]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 82     temp2=temp1->Link[3];
 83     temp2->data=9;
 84     for (i=1; i<=4; i++)
 85         temp2->Link[i-1]=NULL;
 86 
 87     temp1->Link[0]=temp1->Link[2]=NULL;
 88 
 89     printf("请输入想求节点数目的K叉树层数\n");
 90     scanf("%d", &m);      //输入想求结点数目的层数
 91 
 92     if ((i=ComputeLeaf(root, m))==0)     //m层不存在
 93         printf("%d超出K叉树深度,第%d层不存在\n", m, m);
 94 
 95     printf ("K叉树第%d层的结点数目为%d\n", m, i);  //输出m层结点总数
 96 }
 97 
 98 int ComputeLeaf(TreeNode1 *root, int m)
 99 {
100     int i;
101 
102     for (i=1; i<=K; i++)
103     {
104         if (root->Link[i-1]!=NULL)
105             break;
106     }
107 
108     if (i>K)    //空树
109     {
110         if (m==1)
111             return 1;   //第一层一个节点，即根节点
112         else
113             return 0;  //其余各层不存在
114     }
115     else
116     {
117         if (m==1)
118             return 1;  //同上
119         else
120         {
121             int d, k;
122             int count;  //计数变量，统计m层结点数
123             TreeNode1 *ptr, *interval;
124 
125             ptr=root;
126              d=0;
127             count=0;
128             k=1;
129 
130             Path1 *psnewbe, *psnewaf, *head, *current;  
131             head=(Path1 *) malloc(sizeof(Path1));  
132             psnewbe=head;  
133             psnewaf=head;             
134             head->pnext=NULL;  
135             head->pbefore=NULL;
136             while(1)
137             {
138                 if (Search(ptr, d)==0)
139                 {
140                     if (ptr==root)
141                        break;
142                     else
143                     {
144                         if (d==0)
145                         {
146                             k--;
147                             ptr=psnewaf->current;
148                             d=psnewaf->direction;
149                             continue;
150                         }
151                         else
152                         {
153                             k--;
154                             free(psnewaf);
155                             psnewbe->pnext=NULL;  
156                             psnewaf=psnewbe;                   
157                             psnewbe=psnewbe->pbefore;
158                             ptr=psnewaf->current;
159                             d=psnewaf->direction;
160                             continue;
161                         }
162                     }
163                 }
164                 else
165                 {
166                      if (d==0)
167                      {
168                          current=(Path1 *) malloc(sizeof(Path1));
169                          current->current=ptr;
170                          current->direction=Search(ptr, d);
171                          interval=ptr->Link[current->direction-1];
172                          current->pnext=NULL;  
173                          psnewaf->pnext=current;  
174                          current->pbefore=psnewaf;              
175                          psnewbe=psnewaf;  
176                          psnewaf=current; 
177                      }
178                      else
179                      {
180                          psnewaf->direction=Search(ptr, d);
181                          interval=ptr->Link[psnewaf->direction-1];
182                      }
183 
184                      ptr=interval;
185                      d=0;
186                      k++;
187                      if (k==m)   //到达第m层
188                      {
189                          count++;   //计数变量加一
190                          ptr=psnewaf->current;
191                          d=psnewaf->direction;   //回溯
192                          k--;
193                      }
194                      continue;
195                 }
196             }
197             return count;  //返回m层结点总数
198         }
199     }
200 }
201 
202 int Search(TreeNode1 *ptr, int d)
203 {
204     int m=d;
205     for(m++; m<=K; m++)
206     {
207         if (Enable(ptr, m)==1)
208             return m;
209     }
210     return 0;
211 }
212 
213 int Enable(TreeNode1 *ptr, int m)
214 {
215     if (ptr->Link[m-1]!=NULL)
216         return 1;
217     else
218         return 0;
219 }

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #define K 4
  4 
  5 struct TreeNode
  6 {
  7     int data;
  8     struct TreeNode *Link[K];
  9 };
 10 typedef struct TreeNode TreeNode1;
 11 
 12 struct Path
 13 {
 14     TreeNode1 *current;
 15     int direction;
 16     struct Path *pnext, *pbefore;
 17 };
 18 typedef struct Path Path1;
 19 
 20 struct SearchNode    //用于存放搜索到的为给定值m项的结构体类型
 21 {
 22     int plies;     //所在层数
 23     TreeNode1 *goal;   //指向该项的指针
 24     TreeNode1 *before;   //指向该项父结点的指针
 25     struct SearchNode *next;
 26 };
 27 typedef struct SearchNode SearchNode1;
 28 
 29 SearchNode1 *ComputeLeaf(TreeNode1 *root, int m, int *count);   //函数，在K叉树中搜索给定值m，统计K叉树中值为m的结点个数，返回SearchNode1链表头结点
 30 void Order(int i, int m, int *number, SearchNode1 *before, TreeNode1 *root, int plies, SearchNode1 **Location);  //函数，输出以*Location为起点,before为终点的SearchNode1链表段中各结点项位置
 31 int Search(TreeNode1 *ptr, int d);
 32 int Enable(TreeNode1 *ptr, int m);
 33 
 34 void main()
 35 {
 36     int i, m, count=0, number=0;  //m为要搜索的值,count为m项总数
 37     TreeNode1 *temp1, *temp2;
 38     SearchNode1 *head, *before, *after, *Location;
 39 
 40     TreeNode1 *root=(TreeNode1 *) malloc(sizeof(TreeNode1));
 41     root->data=0;
 42     root->Link[0]=NULL;
 43     for(i=1; i<=3; i++)
 44     {
 45         root->Link[i]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 46         root->Link[i]->data=i;
 47     }
 48 
 49     for (i=1; i<=4; i++)
 50         root->Link[1]->Link[i-1]=NULL;
 51 
 52     temp1=root->Link[2];
 53     for (i=1; i<=4; i++)
 54     {
 55         temp1->Link[i-1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 56         temp1->Link[i-1]->data=i+3;
 57     }
 58 
 59     temp2=temp1->Link[0];
 60     temp2->Link[1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 61     temp2->Link[1]->data=10;
 62     for (i=1; i<=4; i++)
 63         temp2->Link[1]->Link[i-1]=NULL;
 64 
 65     temp2->Link[3]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 66     temp2->Link[3]->data=5;
 67     for (i=1; i<=4; i++)
 68         temp2->Link[3]->Link[i-1]=NULL;
 69     temp2->Link[0]=temp2->Link[2]=NULL;
 70 
 71     temp2=temp1->Link[2];
 72     temp2->Link[2]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 73     temp2->Link[2]->data=12;
 74     for (i=1; i<=4; i++)
 75         temp2->Link[2]->Link[i-1]=NULL;
 76     temp2->Link[0]=temp2->Link[1]=temp2->Link[3]=NULL;
 77 
 78     temp2=temp1->Link[1];
 79     for (i=1; i<=4; i++)
 80         temp2->Link[i-1]=NULL;
 81 
 82     temp2=temp1->Link[3];
 83     for (i=1; i<=4; i++)
 84         temp2->Link[i-1]=NULL;
 85 
 86     temp1=root->Link[3];
 87     temp1->Link[1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 88     temp2=temp1->Link[1];
 89     temp2->data=8;
 90     for (i=1; i<=4; i++)
 91         temp2->Link[i-1]=NULL;
 92 
 93     temp1->Link[3]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 94     temp2=temp1->Link[3];
 95     temp2->data=9;
 96     for (i=1; i<=4; i++)
 97         temp2->Link[i-1]=NULL;
 98 
 99     temp1->Link[0]=temp1->Link[2]=NULL;
100 
101     for (i=1; i<=K; i++)
102     {
103         if (root->Link[i-1]!=NULL)
104         {
105             break;
106         }
107     }
108 
109     printf("请输入要在K叉树中搜索的值\n");
110     scanf("%d", &m);   //输入要搜索的值
111 
112     if ((head=ComputeLeaf(root, m, &count))->next==NULL)  //m项不存在
113     {
114         printf("%d在K叉树中不存在\n", m);
115         printf("K叉树中共有%d个%d项\n", count, m);
116     }
117     else
118     {
119         before=head;
120         after=head->next;
121         Location=after;
122         while(after!=NULL)
123         {
124             if (before->plies<after->plies)    //按层数由小到大,每层从左至右的顺序输出所有m项位置
125             {
126                 if (before!=head)                    
127                 {
128                     Order(i, m, &number, before, root, before->plies, &Location);
129                 }
130             }
131             after=after->next;
132             before=before->next;
133         }
134         Order(i, m, &number, before, root, before->plies, &Location);
135         printf("K叉树中共有%d个%d项\n", count, m);  //输出m项总数
136     } 
137 }
138 
139 SearchNode1 *ComputeLeaf(TreeNode1 *root, int m, int *count)
140 {
141     int i;
142     SearchNode1 *head1, *psnew1, *after, *before;
143     head1=(SearchNode1 *) malloc(sizeof(SearchNode1));
144     head1->next=NULL;       //链表初始化
145     head1->plies=0;
146 
147     for (i=1; i<=K; i++)
148     {
149         if (root->Link[i-1]!=NULL)
150             break;
151     }
152 
153     if (i>K)   //空树
154     {
155         if (root->data==m)
156         {
157             psnew1=(SearchNode1 *) malloc(sizeof(SearchNode1));   //只有根节点需要加入SearchNode1链表中
158             psnew1->plies=1;
159             psnew1->goal=root;
160             psnew1->before=NULL;
161             psnew1->next=NULL;
162             head1->next=psnew1;
163             (*count)++;
164         }
165         return head1;
166     }
167     else
168     {
169         if (root->data==m)
170         {
171             psnew1=(SearchNode1 *) malloc(sizeof(SearchNode1));
172             psnew1->plies=1;
173             psnew1->goal=root;
174             psnew1->before=NULL;
175             psnew1->next=NULL;
176             head1->next=psnew1;
177             (*count)++;
178         }
179 
180         int d, k;
181         TreeNode1 *ptr, *interval;
182 
183         ptr=root;
184         d=0;
185         k=1;
186 
187         Path1 *psnewbe, *psnewaf, *head, *current;  
188         head=(Path1 *) malloc(sizeof(Path1));  
189         psnewbe=head;  
190         psnewaf=head;             
191         head->pnext=NULL;  
192         head->pbefore=NULL;
193         while(1)
194         {
195             if (Search(ptr, d)==0)
196             {
197                 if (ptr==root)
198                     break;
199                 else
200                 {
201                     if (d==0)
202                     {
203                         k--;
204                         ptr=psnewaf->current;
205                         d=psnewaf->direction;
206                         continue;
207                     }
208                     else
209                     {
210                         k--;
211                         free(psnewaf);
212                         psnewbe->pnext=NULL;  
213                         psnewaf=psnewbe;                   
214                         psnewbe=psnewbe->pbefore;
215                         ptr=psnewaf->current;
216                         d=psnewaf->direction;
217                         continue;
218                     }
219                 }
220             }
221             else
222             {
223                 if (d==0)
224                 {
225                     current=(Path1 *) malloc(sizeof(Path1));
226                     current->current=ptr;
227                     current->direction=Search(ptr, d);
228                     interval=ptr->Link[current->direction-1];
229                     current->pnext=NULL;  
230                     psnewaf->pnext=current;  
231                     current->pbefore=psnewaf;              
232                     psnewbe=psnewaf;  
233                     psnewaf=current; 
234                 }
235                 else
236                 {
237                      psnewaf->direction=Search(ptr, d);
238                      interval=ptr->Link[psnewaf->direction-1];
239                 }
240 
241                 ptr=interval;
242                 d=0;
243                 k++;
244                 if (ptr->data==m)  //找到一个m项
245                 {
246                     (*count)++;
247                     psnew1=(SearchNode1 *) malloc(sizeof(SearchNode1));  //建立该m项对应的SearchNode1结点
248                     psnew1->plies=k;
249                     psnew1->goal=ptr;
250                     psnew1->before=psnewaf->current;
251 
252                     before=head1;
253                     after=head1->next;
254                     while (after!=NULL)
255                     {
256                         if (before->plies<after->plies)     //将SearchNode1结点插入至SearchNode1链表中，确保插入后链表中相同层数的结点所属的块按层数大小以从小到大顺序从左至右排列，且每个块中各节点排列顺序与他们在树的同一层中出现的顺序一致
257                         {
258                             if (psnew1->plies<after->plies)
259                             {
260                                psnew1->next=before->next;
261                                before->next=psnew1;
262                                break;
263                             }
264                         }
265                         after=after->next;
266                         before=before->next;
267                     }
268                     if(after==NULL)
269                     {
270                         psnew1->next=NULL;
271                         before->next=psnew1;
272                     }
273                 }
274                 continue;
275             }
276         }
277         return head1;
278     }
279 }
280 
281 void Order(int i, int m, int *number, SearchNode1 *before, TreeNode1 *root, int plies, SearchNode1 **Location)
282 {
283     if (i>K)      //空树
284     {
285         (*number)++;
286         printf("第%d个%d结点位于第%d层上从左自由数起第%d个位置\n", *number, m, 1, 1); //SearchNode1链表中只有一个结点需要输出
287         return;
288     }
289     else
290     {
291         if (plies==1)  //要处理链表块只有一个结点,层数1,即为根节点
292         {
293             (*number)++;
294             printf("第%d个%d结点位于第%d层上从左自由数起第%d个位置\n", *number, m, 1, 1);
295             *Location=(*Location)->next;
296             return;
297         }
298         else
299         {
300             int d, k, count;
301             TreeNode1 *ptr, *interval;
302 
303             ptr=root;
304             count=0;
305              d=0;
306             k=1;
307 
308             Path1 *psnewbe, *psnewaf, *head, *current;  
309             head=(Path1 *) malloc(sizeof(Path1));  
310             psnewbe=head;  
311             psnewaf=head;             
312             head->pnext=NULL;  
313             head->pbefore=NULL;
314             while(1)
315             {
316                 if (Search(ptr, d)==0)
317                 {
318                     if (ptr==root)
319                        break;
320                     else
321                     {
322                         if (d==0)
323                         {
324                             k--;
325                             ptr=psnewaf->current;
326                             d=psnewaf->direction;
327                             continue;
328                         }
329                         else
330                         {
331                             k--;
332                             free(psnewaf);
333                             psnewbe->pnext=NULL;  
334                             psnewaf=psnewbe;                   
335                             psnewbe=psnewbe->pbefore;
336                             ptr=psnewaf->current;
337                             d=psnewaf->direction;
338                             continue;
339                         }
340                     }
341                 }
342                 else
343                 {
344                      if (d==0)
345                      {
346                          current=(Path1 *) malloc(sizeof(Path1));
347                          current->current=ptr;
348                          current->direction=Search(ptr, d);
349                          interval=ptr->Link[current->direction-1];
350                          current->pnext=NULL;  
351                          psnewaf->pnext=current;  
352                          current->pbefore=psnewaf;              
353                          psnewbe=psnewaf;  
354                          psnewaf=current; 
355                      }
356                      else
357                      {
358                          psnewaf->direction=Search(ptr, d);
359                          interval=ptr->Link[psnewaf->direction-1];
360                      }
361 
362                      ptr=interval;
363                      d=0;
364                      k++;
365                      if (k==plies)  //抵达第plies层
366                      {
367                          count++;
368                          if (ptr->data==m)   //在plies层找到m项
369                          {
370                              (*number)++;
371                              printf("第%d个%d结点位于第%d层上从左自由数起第%d个位置\n", *number, m, plies, count);  //输出找到的m项位置
372                              if (*Location==before)  //到达链表块尾部，链表块中结点位置输出完毕
373                              {
374                                  *Location=(*Location)->next;  //*Location指向下一链表块第一个结点
375                                  return;
376                              }
377                              *Location=(*Location)->next;   //递进至本链表块下一结点
378                          }
379                          ptr=psnewaf->current;
380                          d=psnewaf->direction;
381                          k--;
382                      }
383                      continue;
384                 }
385             }
386         }
387     }
388 }
389 
390 int Search(TreeNode1 *ptr, int d)
391 {
392     int m=d;
393     for(m++; m<=K; m++)
394     {
395         if (Enable(ptr, m)==1)
396             return m;
397     }
398     return 0;
399 }
400 
401 int Enable(TreeNode1 *ptr, int m)
402 {
403     if (ptr->Link[m-1]!=NULL)
404         return 1;
405     else
406         return 0;
407 }

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #define K 4
  4 
  5 struct TreeNode
  6 {
  7     int data;
  8     struct TreeNode *Link[K];
  9 };
 10 typedef struct TreeNode TreeNode1;
 11 
 12 struct Path
 13 {
 14     TreeNode1 *current;
 15     int direction;
 16     struct Path *pnext, *pbefore;
 17 };
 18 typedef struct Path Path1;
 19 
 20 struct SearchNode
 21 {
 22     int value;
 23     int plies;
 24     TreeNode1 *goal;
 25     TreeNode1 *before;
 26     struct SearchNode *next;
 27 };
 28 typedef struct SearchNode SearchNode1;
 29 
 30 SearchNode1 *ComputeLeaf(TreeNode1 *root, int *count);    //函数用于求节点总数，返回SearchNode1链表头结点
 31 int Search(TreeNode1 *ptr, int d);
 32 int Enable(TreeNode1 *ptr, int m);
 33 
 34 void main()
 35 {
 36     int i, count; //count记录结点总数
 37     SearchNode1 *head, *before, *after;
 38     TreeNode1 *temp1, *temp2;
 39     TreeNode1 *root=(TreeNode1 *) malloc(sizeof(TreeNode1));
 40     root->data=0;
 41     root->Link[0]=NULL;
 42     for(i=1; i<=3; i++)
 43     {
 44         root->Link[i]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 45         root->Link[i]->data=i;
 46     }
 47 
 48     for (i=1; i<=4; i++)
 49         root->Link[1]->Link[i-1]=NULL;
 50 
 51     temp1=root->Link[2];
 52     for (i=1; i<=4; i++)
 53     {
 54         temp1->Link[i-1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 55         temp1->Link[i-1]->data=i+3;
 56     }
 57 
 58     temp2=temp1->Link[0];
 59     temp2->Link[1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 60     temp2->Link[1]->data=10;
 61     for (i=1; i<=4; i++)
 62         temp2->Link[1]->Link[i-1]=NULL;
 63 
 64     temp2->Link[3]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 65     temp2->Link[3]->data=11;
 66     for (i=1; i<=4; i++)
 67         temp2->Link[3]->Link[i-1]=NULL;
 68     temp2->Link[0]=temp2->Link[2]=NULL;
 69 
 70     temp2=temp1->Link[2];
 71     temp2->Link[2]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 72     temp2->Link[2]->data=12;
 73     for (i=1; i<=4; i++)
 74         temp2->Link[2]->Link[i-1]=NULL;
 75     temp2->Link[0]=temp2->Link[1]=temp2->Link[3]=NULL;
 76 
 77     temp2=temp1->Link[1];
 78     for (i=1; i<=4; i++)
 79         temp2->Link[i-1]=NULL;
 80 
 81     temp2=temp1->Link[3];
 82     for (i=1; i<=4; i++)
 83         temp2->Link[i-1]=NULL;
 84 
 85     temp1=root->Link[3];
 86     temp1->Link[1]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 87     temp2=temp1->Link[1];
 88     temp2->data=8;
 89     for (i=1; i<=4; i++)
 90         temp2->Link[i-1]=NULL;
 91 
 92     temp1->Link[3]=(TreeNode1 *) malloc(sizeof(TreeNode1));
 93     temp2=temp1->Link[3];
 94     temp2->data=9;
 95     for (i=1; i<=4; i++)
 96         temp2->Link[i-1]=NULL;
 97 
 98     temp1->Link[0]=temp1->Link[2]=NULL;
 99 
100     head=ComputeLeaf(root, &count);
101     before=head;
102     after=head->next;
103 
104     i=0;
105     while (after!=NULL)
106     {
107         if (before->plies<after->plies)     //按层数有小到大每层从左至右顺序输出所有结点值
108         {
109             if (before!=head)
110             {
111                 printf("\n");
112             }
113             i++;
114             printf("K叉树的第%d行从左至右为:", i);
115             printf(" %d", after->value);
116         }
117         else
118         {
119             printf(" %d", after->value);
120         }
121         after=after->next;
122         before=before->next;
123     }
124     printf("\n");
125 
126     printf("K叉树中共有%d个节点\n", count);   //输出结点总数
127 }
128 
129 SearchNode1 *ComputeLeaf(TreeNode1 *root, int *count)
130 {
131     int i;
132     SearchNode1 *head1, *psnew1, *after, *before;
133     head1=(SearchNode1 *) malloc(sizeof(SearchNode1));
134     head1->next=NULL;
135     head1->plies=0;
136 
137     for (i=1; i<=K; i++)
138     {
139         if (root->Link[i-1]!=NULL)
140             break;
141     }
142 
143     psnew1=(SearchNode1 *) malloc(sizeof(SearchNode1));
144     psnew1->value=root->data;
145     psnew1->plies=1;
146     psnew1->goal=root;          //将根节点插入SearchNode1链表
147     psnew1->before=NULL;
148     psnew1->next=NULL;
149     head1->next=psnew1;
150 
151     if (i>K)   //空树
152     {
153          (*count)=1;   //节点总数为1
154          return head1;
155     }
156     else
157     {
158          int d, k;
159          TreeNode1 *ptr, *interval;
160 
161          ptr=root;
162          d=0;
163          *count=1;
164          k=1;
165 
166          Path1 *psnewbe, *psnewaf, *head, *current;  
167          head=(Path1 *) malloc(sizeof(Path1));  
168          psnewbe=head;  
169          psnewaf=head;             
170          head->pnext=NULL;  
171          head->pbefore=NULL;
172          while(1)
173         {
174             if (Search(ptr, d)==0)
175             {
176                 if (ptr==root)
177                     break;
178                 else
179                 {
180                     if (d==0)
181                     {
182                         k--;
183                         ptr=psnewaf->current;
184                         d=psnewaf->direction;
185                         continue;
186                     }
187                     else
188                     {
189                         k--;
190                         free(psnewaf);
191                         psnewbe->pnext=NULL;  
192                         psnewaf=psnewbe;                   
193                         psnewbe=psnewbe->pbefore;
194                         ptr=psnewaf->current;
195                         d=psnewaf->direction;
196                         continue;
197                     }
198                 }
199             }
200             else
201             {
202                 if (d==0)
203                 {
204                     current=(Path1 *) malloc(sizeof(Path1));
205                     current->current=ptr;
206                     current->direction=Search(ptr, d);
207                     interval=ptr->Link[current->direction-1];
208                     current->pnext=NULL;  
209                     psnewaf->pnext=current;  
210                     current->pbefore=psnewaf;              
211                     psnewbe=psnewaf;  
212                     psnewaf=current; 
213                 }
214                 else
215                 {
216                     psnewaf->direction=Search(ptr, d);
217                     interval=ptr->Link[psnewaf->direction-1];
218                 }
219 
220                 ptr=interval;            //找到K叉树中新节点
221                 d=0;
222                 k++;
223 
224                 (*count)++;   //计数变量加一
225                 psnew1=(SearchNode1 *) malloc(sizeof(SearchNode1));
226                 psnew1->value=ptr->data;         //建立与新节点对应的SearchNode1结点
227                 psnew1->plies=k;
228                 psnew1->goal=ptr;
229                 psnew1->before=psnewaf->current;
230 
231                 before=head1;
232                 after=head1->next;
233                 while (after!=NULL)
234                 {
235                     if (before->plies<after->plies)
236                     {
237                         if (psnew1->plies<after->plies)
238                         {
239                             psnew1->next=before->next;      //将SearchNode1结点插入至SearchNode1链表中，确保插入后链表中相同层数的结点所属的块按层数大小以从小到大顺序从左至右排列，且每个块中各节点排列顺序与他们在树的同一层中出现的顺序一致
240                             before->next=psnew1;
241                             break;
242                         }
243                     }
244                     after=after->next;
245                     before=before->next;
246                 }
247                 if(after==NULL)
248                 {
249                     psnew1->next=NULL;
250                     before->next=psnew1;
251                 }
252                 continue;
253             }
254         }
255         return head1;
256     }
257 }
258 
259 int Search(TreeNode1 *ptr, int d)
260 {
261     int m=d;
262     for(m++; m<=K; m++)
263     {
264         if (Enable(ptr, m)==1)
265             return m;
266     }
267     return 0;
268 }
269 
270 int Enable(TreeNode1 *ptr, int m)
271 {
272     if (ptr->Link[m-1]!=NULL)
273         return 1;
274     else
275         return 0;
276 }