一、调试成功程序及说明 1、 题目： 1、利用递归算法输出根节点到所有叶子节点的路径； 算法思想： 用一个数组path[N]来存储他的祖先，即根节点到该节点的路径，然后调用allpath（）函数，判断该节点是不是叶子节点，是的话就输出，否则继续向下（孩子）走。 运行结果： 结果分析： 运行正确。 附源程序
void allpath(TR *T,char *path,int m) { TR *p; int i; if(T) { if(!(T->fir)) //该节点为叶子，那么就输出当前的路径，因为path里面存的都是他的祖先 { path[m] = T->data; printf("Step :"); for(i=0;i<m;i++) printf("%c-->",path[i]); printf("%c\n",path[m]); //为了输出好看，所以把最后一个拿出来了 } else //开始寻找以T为根节点的子树的所有路径 { path[m]=T->data; m++; p = T->fir; //先找第一个孩子 while(p) { allpath(p,path,m); p = p->sib; //然后寻找他的所有兄弟 } } } } void getpath1(TR *T)//递归算法输出根节点到所有叶子节点的路径 { int m=0; char path[N]; allpath(T,path,m); }2、 题目： 2、利用非递归算法输出根节点到所有叶子节点的路径； 算法思想： 法一： 运用后序遍历（即孩子—兄弟树的中序遍历），判断当前栈顶元素是否为叶子，是的话，就输出栈的所有元素（不是弹栈，只弹栈顶） 法二： 运用层次遍历，加上一个front[N]来记录父亲节点，然后对队列遍历一次即可，判断里面的元素是不是叶子节点，是的话，就按照front[N]来输出路径，这样做的好处在于，可以很方便的找出最长/最短的路径。（输出的路径的长度也是从小到大的） 运行结果： 结果分析： 运行正确。 附源程序： 法一：
void getpath2(TR *T)//非递归算法---后序---输出根节点到所有叶子节点的路径 { TR *t[N],*p; int top = -1,count=0,i; p = T; while(top>=0||p) { while(p) { top++; t[top] = p; p = p->fir; } p = t[top]; top--; if(p->fir==NULL) { count++; printf("Step %d:",count); for(i=0;i<=top;i++) printf("%c-->",t[i]->data); printf("%c\n",p->data); } p = p->sib; } }法二：
void getpath3(TR *T)//非递归算法---层次---输出根节点到所有叶子节点的路径 { TR *t[N],*p; int front[N],count=0,i,tmp; int head=0,rear=0; t[rear] = T; front[rear] = -1; rear++; while(rear>head) { p = t[head]; p = p->fir; while(p) { t[rear] = p; front[rear] = head; rear++; p = p->sib; } head++; } printf("路线长度从小到大排序为:\n"); for(i=0;i<rear;i++) { if(!(t[i]->fir)) { count++; printf("Step %d:%c",count,t[i]->data); tmp = front[i]; while(tmp>=0) { printf("<--%c",t[tmp]->data); tmp = front[tmp]; } printf("\n"); } } }3、 题目： 3、利用递归算法统计数中叶子节点的数量； 算法思想： 判断当前节点是不是叶子节点，是的话就返回1，否则继续选找以该节点为根节点的子树（可以递归了），找出他所有的叶子节点的个数，并且用m来存储。 运行结果： 结果分析： 运行正确 附源程序：
int leaftree(TR *T)//递归计算并返回树的叶子节点的数量 { TR *p; int m=0; if(T) //T为真进入 { if(!(T->fir)) //找到叶子 return 1; //返回1，让最终的m加1 else //否则找完以T为根节点的分支 { p = T->fir; //p赋值为T的第一个孩子，开始寻找T的第一个孩子为根节点的叶子数量 while(p) { m = m+leaftree(p); p = p->sib; //寻找T的其他孩子（即T的第一个孩子的兄弟）为根节点的叶子数量 } //结束，说明以T为根节点的子树已经找完。 } } return m; //返回最后该（子）树的所有叶子。 }4、 题目： 计算树的宽度（包含节点数最多的那一层节点数量）； 算法思想： 我们用一个数组height记录高度，即当前节点的所在高度，width记录每一层的节点个数，然后因为height是单调有界的，只需要一次遍历，对相应的width进行++操作就行了（width[height[i]]++），这个灵感来自于原来的一道题;数字范围为1-100000的正数。这样可以有效的降低时间复杂度。 运行结果： 结果分析： 运行正确 附源程序
int weidth(TR *T)//输出树的宽度（包含节点数量最多的那一层的节点数量即为树的宽度） { TR *t[N],*p; int head=0,rear=0,i,max; //max记录点数量最多的那一层的节点数量 int height[N],width[N]={0}; //height记录高度，即当前节点的所在高度，width记录每一层的节点个数 height[rear] = 1; t[rear] = T; rear++; //入队 while(rear>head) //层次遍历 { p = t[head]; p = p->fir; while(p) { height[rear] = height[head]+1; //记录该节点的高度 t[rear] = p; rear++; p = p->sib; } head++; } for(i=0;i<rear;i++) //记录每一层的节点个数 width[height[i]]++; max = width[1]; //寻找最大的 for(i = 2;i<height[rear-1];i++) //注意到height里面的元素的单调性，就可以轻松判断count的元素个数 if(width[i]>max) max = width[i]; return max; }5、 题目： 在指定位置插入一个节点（选做）； 算法思想： 首先先运用后序遍历找到插入点的位置（这里运用层次也可以，那么和上面的选找路径一样，再加一个front[N]来存储父节点的位置），然后对i分类讨论，0或者>0，i=0的话，就插入在p的fir，和p->fir->sip之间，否则就插在p1和p1->sip之间，这里的p1只需要一次简单的遍历就可以找到了。但是要记住，最后插入节点S后，S->fir要赋值为NULL。 运行结果： 结果分析： 运行正确 附源程序
void insdata(TR *T,char subroot,int i,char data) { TR *t[N],*p=T,*p1,*p2,*S; //p为插入的位置的父节点subroot，p1为插入的位置的上一个兄弟，p2为插入的位置的下一个兄弟，S为插入的节点 int top = -1; int flag = 0; //判断插入位置是否存在 if(T) { while(top>=0||p) //后序遍历，选找插入的位置 { while(p) { top++; t[top] = p; p = p->fir; } p = t[top]; top--; if(p->data==subroot) { flag = 1; break; } p = p->sib; } if(flag==1) //说明插入位置存在 { S = (TR *)malloc(sizeof(TR)); //动态分配空间 S->data = data; p1=p; p2=p1->fir; if(i==0) //分情况，是第一孩子，还是兄弟，这里的代码不一样的，一个是fir,一个是sip，无法代码合并 { p->fir = S; S->sib = p2; } else { while(i>0) //找是插在第几个分支的后面 { i--; p1 = p2; p2 = p2->sib; if(p2==NULL) //如果i大于该结点的分支总数，则就在该结点的最后一个分支的后边做插入 break; } p1->sib = S; S->sib = p2; } S->fir = NULL; //这个不能丢，要给S的第一个孩子赋值为NULL } } }6、 题目： 销毁以指定节点为根节点的子树（选做）；算法思想： 运行结果： 结果分析： 运行正确 附源程序
TR *delsubtree(TR *T,char s)//销毁以包含数据s为根节点的子树，并返回删除后树的根节点指向 { TR *t[N],*p,*p1,*p2; int top = -1; p = T; while(top>=0||p) { while(p) { top++; t[top] = p; p = p->fir; } p = t[top]; top--; if(p->data==s) break; p = p->sib; } p1 = t[top]; p2 = p1->fir; if(p2==p) t[top]->fir=p->sib; else { while(p2) { if(p2==p) break; p1 = p2; p2 = p2->sib; } p1->sib = p->sib; } deltree(p); return T; }二、小结 大概1个多小时写完了，因为之前练习了老师上课的代码tree.c很多次，除了第五个忘了写S->fir=NULL外，别的都是一遍过（写完直接编译，运行正确），感觉这次题目很简单，但是我不会掉以轻心，后面还会继续练习（因为今天练习迷宫的时候，我发现我只记得用栈和队列来写了，对于递归的有点忘了）。 很多操作都用到了后序/层次遍历，感觉这两种遍历方式很常用。以及感觉有一个模板，就是，递归的，都有这个样子的代码：
p = T->fir; //有时更改为p->fir->sib While(p) { 递归函数（p，...); P = p->sib; }感觉有点像套路。
