输入：ABC##DE#F#G####
输出：3
不难看出，
以二叉树方式存储的树，二叉树结点a的左孩子就是树结点a的左孩子，而二叉树a的右孩子是树节点的a的兄弟，既a父节点f_a的某个孩子（非长子）
那么，可以通过遍历树的每个结点，编写算法，计算出每个结点的度（既树的孩子数目），找出其中最大的度，作为该树的度输出。
第一版代码
#include <stdio.h> #include <stdlib.h> int Max_degree = 0; typedef struct node{ char data; int degree; struct node *lchild,*rchild; }BinTree; /*---创建二叉树---*/ BinTree *CreateBinTree() {/*先序建立一个二叉树链表*/ BinTree *bt = NULL; char ch; ch = getchar(); if(ch!='#') { bt = (BinTree *)malloc(sizeof(BinTree)); bt->data = ch; bt->lchild = CreateBinTree(); bt->rchild = CreateBinTree(); } return bt; } int getpiontDegree(BinTree *bin) { /*遍历找到一个不为空的节点，先判断它是否有左孩子（树的结点是否有孩子），然后计算左孩子的右孩子数目（树结点长子的兄弟数）*/ if(bin!=NULL) { if(bin->lchild != NULL) { BinTree *p = bin->lchild; int n = 1; while(p->rchild !=NULL) { p= p->rchild; n++; } bin->degree = n; } getpiontDegree(bin->lchild); getpiontDegree(bin->rchild); } } void firstprintfBinTreeDegree(BinTree *bt) { int a; /*遍历找到一个非空结点，将该结点与已经存储的Max_degree比较大小，找出最大度的结点*/ if(bt != NULL) { if(bt->lchild) { if(Max_degree<bt->degree) { Max_degree = bt->degree; } } firstprintfBinTreeDegree(bt->lchild); firstprintfBinTreeDegree(bt->rchild); } } int main() { BinTree *bin; bin = CreateBinTree(); getpiontDegree(bin); firstprintfBinTreeDegree(bin); printf("%d",Max_degree); }
第二版代码
在getpiontDegree（）函数中遍历每个结点，计算出每个结点的度，然后又在firstprintfBinTreeDegree（）函数中遍历每个结点，找出其中度最大的结点，其中每个结点被重复遍历了两次，浪费了时间。我们完全可以利用firstprintfBinTreeDegree（）中的遍历进行同时进行这两个操作，getpiontDegree（）函数在firstprintfBinTreeDegree（）函数中被调用，用来计算该循环下的每一个结点的度
给出代码
#include <stdio.h> #include <stdlib.h> typedef char dataType; int Max_degree = 0; typedef struct node{ dataType data; int degree; struct node *lchild,*rchild; }BinTree; /*---创建二叉树---*/ BinTree *CreateBinTree() {/*先序建立一个二叉树链表*/ BinTree *bt = NULL; char ch; ch = getchar(); if(ch!='#') { bt = (BinTree *)malloc(sizeof(BinTree)); bt->data = ch; bt->lchild = CreateBinTree(); bt->rchild = CreateBinTree(); } return bt; } int getpointDegree(BinTree *bin) { if(bin->lchild!=NULL) { int degree = 1; BinTree *p = bin->lchild; while(p->rchild!=NULL) { degree++; p = p->rchild; } return degree; } return 0; } void firstprintfBinTreeDegree(BinTree *bt) { if(bt != NULL) {/*---先序二叉树遍历---*/ bt->degree = getpointDegree(bt); //printf("%c:%d ",bt->data,bt->degree); if(bt->degree > Max_degree) { Max_degree = bt->degree; } firstprintfBinTreeDegree(bt->lchild); firstprintfBinTreeDegree(bt->rchild); } } int main() { BinTree *bin; bin = CreateBinTree(); firstprintfBinTreeDegree(bin); printf("%d",Max_degree); return 0; }
ps：第一次做这个题，思路快就有了，但是代码总是打不出来。第一次尝试用的迭代，想不出来怎么把每次的度和迭代的跳出结合起来，代码乱套了。最后做出了来，oj还是不给ac，没弄明白，回来又把代码写了一遍，这次居然过了，真神奇
