一、调试成功程序及说明 1、 题目： 根据二叉树的中序、先序序列创建二叉树，并返回根节点指针； 算法思想： 先根据先序序列找到当前子树的根，然后再在中序序列中寻找这个根，那么左边的就是左分支，右边的就是右分支（当然左不一定是到最左，可能会遇到之前用过的根节点，右边同理）。然后递归构造就行了，毕竟树的定义就是递归的。 运行结果：
结果分析： 结果正确，和老师给的该题二叉树的图像相吻合。 附源程序
BT *createtree(char *in,char *pre,int k) //根据二叉树的中序、先序序列创建二叉树，并返回根节点指针 { BT *T; //子树的根节点 int i; //计算左分支的节点个数 if(k<=0) //没有节点了就说明该分支创建完成 return NULL; else { T = (BT *)malloc(sizeof(BT)); //动态分配空间 T->data = *pre; //子树根节点赋值 for(i=0;in[i]!=*pre;i++); //寻找子树根节点在中序序列的为止，以此来确定左右分支 T->left = createtree(in,pre+1,i); //递归创建左子树 T->right = createtree(in+i+1,pre+i+1,k-i-1); //递归创建右子树 return T; //返回当前的根节点 } }2、 题目： 为每个节点的pa指针赋值（注意根节点的pa指向NULL） 算法思想： 采用后序遍历，因为后序遍历中的栈，满足前一个节点为后一个节点的父亲。这样方便赋值。 运行结果：
结果分析： 运行结果正确。 附源程序
void getpa(BT *T)//为二叉树的每个节点的pa指针赋值（非递归算法） { BT *t[N],*p,*b; //*t[N]为栈，b来帮忙判断右节点是否走过 int top = -1; p = T; do { while(p) { top++; t[top] = p; p = p->left; } b = NULL; while(top>=0) { p = t[top]; if(p->right == b) { top--; p->pa = t[top]; b = p; } else { p = p->right; break; } } }while(top>=0); T->pa = NULL; }3、 题目： 利用递归算法输出根节点到所有叶子节点的路径； 算法思想： 递归寻找到叶子节点（这个判断左右孩子就行了），然后根据父节点向上输出就行了。 存在问题：我用了父节点，因为这里不可以加别的参数或者全局变量，所以我不太会存他的父节点。 运行结果： 结果分析： 运行结果正确，但是由于参数限制，我们不能知道条数 附源程序：
void getpath1(BT *T)//递归算法输出根节点到所有叶子节点的路径 { BT *p; int i; p = T; if(p) { if(!(p->left||p->right)) //判断是不是叶子节点 { printf("Step:"); while((p->pa)!=NULL) //只是为了输出好看，可以除了最后一个，别的都有箭头罢了； { printf("%c<--",p->data); p = p->pa; } printf("%c\n",p->data); } else { getpath1(p->left); //递归选找左分支 getpath1(p->right); //递归选找右分支 } } }4、 题目： 用非递归算法输出根节点到所有叶子节点的路径； 算法思想： 法一：运用后序遍历，因为他的栈里面的元素是满足父子关系的，所以判断栈顶是不是叶子节点，是的话，就把栈里面的元素显示一下； 法二；运用层次遍历，但是需要一个fro[N]来存储它前一个节点的位置。 总上，两种方法都可以找出所有路径，但是层次遍历的路径是从小到大排序的，所以找最长/短路径，还是优先使用层次遍历 运行结果： 结果分析： 结果正确，和3算出来的路径一样 附源程序： 法一：
void getpath2(BT *T)//非递归算法---后序---输出根节点到所有叶子节点的路径 { BT *t[N],*p=T,*b; int step = 0,i; int top = -1; int sum[N]={1},max=1,min=1; do { while(p) { top++; t[top] = p; p = p->left; } b = NULL; while(top>=0) { p = t[top]; if(p->right == b) { if(!(p->left||p->right)) { step++; printf("Step %d: ",step); for(i=0;i<=top-1;i++) { sum[step]++; printf("%c-->",t[i]->data); } printf("%c\n",t[top]->data); } top--; b=p; } else { p = p->right; break; } } }while(top>=0); for(i=1;i<=step;i++) { if(sum[i]<sum[min]) min=i; if(sum[i]>sum[max]) max=i; } printf("最长路径为Step %d,最短路径为Step %d。\n",max,min); }法二：
void getpath3(BT *T)//非递归算法---层次---输出根节点到所有叶子节点的路径 { BT *t[N],*p; int fro[N]; int i,count=0,tmp; int head=0,rear=0; t[rear] = T; fro[rear] = -1; rear++; while(rear> head) { p = t[head]; if(p->left) { fro[rear]=head; t[rear] = p->left; rear++; } if(p->right) { fro[rear]=head; t[rear] = p->right; rear++; } head++; } printf("路线长度从小到大排序为:\n"); for(i=0;i<head;i++) { if(!(t[i]->left||t[i]->right)) { count++; printf("Step %d:%c",count,t[i]->data); tmp = fro[i]; while(tmp>=0) { printf("<--%c",t[tmp]->data); tmp = fro[tmp]; } printf("\n"); } } }5、 题目： 利用递归算法，寻找距离两个指定节点（互相不为对方的祖先）最近的共同祖先，返回该祖先指针； 算法思想： 运用后序遍历，把两个指定节点（互相不为对方的祖先）都存在两个数组里面，然后遍历寻找就行了。 运行结果： 结果分析： 运行正确，显示了他们最近的共同祖先 附源程序：
BT *getcomances(BT *T,char s1,char s2)//寻找距离两个指定节点，即分别包含数据s1和s2的节点（互相不为对 //方的祖先）最近的共同祖先，返回指向该祖先结点的指针 { BT *t[N],*p=T,*b,*num1[N],*num2[N]; int top = -1,i,j,len1=0,len2=0,flag=0; do { while(p) { top++; t[top] = p; p = p->left; } b = NULL; while(top>=0) { p = t[top]; if(p->right == b) { if(p->data == s1) { for(i= top;i>=0;i--) { len1++; num1[top-i] = t[i]; } } if(p->data == s2) { for(i= top;i>=0;i--) { len2++; num2[top-i] = t[i]; } } top--; b=p; } else { p = p->right; break; } } }while(top>=0); for(i=0;i<len1;i++) { for(j=0;j<len2;j++) { if(num1[i]->data == num2[j]->data) { flag = 1; break; } } if(flag==1) break; } return num1[i]; }6、 题目： 按层次逐行输出二叉树的节点数据（每一层单独显示一行），并判断该二叉树是否为完全二叉树 算法思想： 1.设置一个height[N]数组，存储每一个节点的层数，用层数变化判断，是否需要换行。 2.设置了一个权重，左孩子的权重为2，右孩子的权重为1，那么我们可以记录下每一个节点的权重，当权重num[N]中大的在前，小的在后，2的个数不超过1个，1的个数为0个。 运行结果： 本题样例
只有根
树为空
结果分析： 运行结果正确，我用了一些特殊的数来测试 附源程序：
//我设置了一个权重，左孩子的权重为2，右孩子的权重为1，那么我们可以记录下每一个节点的权重，当权重num[N]中大的在前，小的在后，2的个数不超过1个 int layervisit(BT *T)//层次遍历二叉树，逐行输出节点数据（每一层单独一行显示），并判断该二叉树 //是否为完全二叉树，如果是，返回1，否则返回0 { BT *t[N],*p; //队列 int head=0,rear=0,height[N],num[N]={0},flag=1,count=0,i; // height记录节点的层数 if(!T) return 1; t[rear] = T; height[rear] = 1; rear++; while(rear>head) { p = t[head]; printf("%c ",p->data); if(p->left) { t[rear] = p->left; height[rear] = height[head]+1; num[head] = num[head]+2; rear++; } if(p->right) { t[rear] = p->right; height[rear] = height[head]+1; num[head] = num[head]+1; rear++; } if(height[head]!=height[head+1]) printf("\n"); head++; } for(i=1;i<head;i++) { if(num[i-1]<num[i]) //判断前后两个的大小关系 { flag = 0; break; } if(num[i]==1||num[0]==1) //判断有没有点只有右孩子 { flag = 0; break; } if(num[i]==2) //判断只有左孩子点的个数 count++; } if(num[0]==2) //上面从i=1开始循环，所以要额外判断i=0 count++; if(count>1) //如果个数超过1个，那么就不是完全二叉树 flag = 0; return flag; }7、 题目： 销毁以指定节点为根节点的子树 算法思想： 采用层次遍历，用了一个数组fro[N]来存储当前节点的父节点（上一个节点），用数组child[N]来存储他是左孩子还是右孩子，然后在入队出队的过程中，寻找该节点，找到后，让该节点的前一个节点（父节点）相应的孩子节点指向空，然后调用delbt(BT *T)函数将其删除。 运行结果：
结果分析： 结果正确，成功删除该子树。 附源程序：
BT *delsubtree(BT *T,char s)//找到包含数据为s的节点，并删除以该节点为根的子树，最后返回根节点 //（因为这个删除也可能会删除整个树，所以结束后返回当前二叉树的根节点指向） { BT *t[N],*p,*fro[N]; int child[N]; int head=0,rear=0; t[rear] = T; child[rear] = -1; fro[rear] = NULL; rear++; while(rear> head) { p = t[head]; if(p->data == s) break; if(p->left) { fro[rear] = p; child[rear] = 0; //0表示左孩子 t[rear] = p->left; rear++; } if(p->right) { fro[rear] = p; child[rear] = 1; //1表示右孩子 t[rear] = p->right; rear++; } head++; } if(child[head] == 0) fro[head]->left = NULL; else if(child[head] == 1) fro[head]->right = NULL; p = delbt(p); return T; } BT *delbt(BT *T) { if(T) { T->left = delbt(T->left); T->right = delbt(T->right); free(T); } return NULL; }