树的众多操作(2014华为校园招聘 机试 第三题 )

这次的题目是在http://blog.csdn.net/wang603603/article/details/11394915看到的，但是我觉得他完成的不是很好，容错性或则健壮性感觉欠佳，便自己写了一个，因为是华为的机试题，所以每次写起来都特别有激情。希望能进呀...

问题描述：

输入一个二叉树 格式为“单个字符+节点所在层次”
比如根节点所在层次是1，它的两个子树都是2. 节点排列从左到右，然后再输入其中的某个（些）节点，
求得其深度。
第三题还有条件：层次不超过9层
输入：a1b2c2d3e3f3 ab
输出：3 2

ps：因为是在一个文档里写了很多代码，头文件和命名空间就不引了，还有关于哪个层次不超过9的条件我就自动忽略啦...树的操作真的很重要...一定要掌握，递归和非递归，链式存储和线性存储...

typedef struct Tree{char data;struct Tree *lchild;struct Tree *rchild;}Tree;//创建树Tree *BuildTree(char a[]){assert(a != NULL);assert(strlen(a) >= 2);Tree *head;list<Tree *> lstTree;list<Tree *>::iterator p;int i = 0;while(i < strlen(a)){if(i == 0){head = (Tree*)malloc(sizeof(Tree));head->data = a[i];head->lchild = NULL;head->rchild = NULL;lstTree.push_back(head);p = lstTree.begin();i+=2;continue;}char record = a[i+1];if(a[i+1] != a[i-1]+1)//格式有错误return NULL;list<Tree *>::iterator start;//表示此层的第一个元素int time = 1;//记录当前层次添加节点的次数while(record == a[i+1])//record记录层次，如果层次有变化则跳出循环{//这一段代码逻辑比较复杂Tree *temp;temp = (Tree*)malloc(sizeof(Tree));temp->data = a[i];temp->lchild = NULL;temp->rchild = NULL;lstTree.push_back(temp);if((*p)->lchild == NULL){(*p)->lchild = temp;}else if((*p)->rchild == NULL){(*p)->rchild = temp;}else{++p;(*p)->lchild = temp;}i+=2;if(time == 1){//为了保证每一次P指针都指向下一层的第一个节点start = lstTree.end();start--;time++;}if(p == start)//超过这一层最多节点数，输入字符串违法return NULL;}p = start;}return head;}//删除该树void DeleteTree(Tree* t){assert(t != NULL);if(t->lchild != NULL)DeleteTree(t->lchild);if(t->rchild != NULL)DeleteTree(t->rchild);free(t);}//得到某个节点的高度int GetHigh(Tree *t){assert(t != NULL);if(t->lchild == NULL && t->rchild == NULL)return 1;int high1 = 1,high2 = 1;if(t->lchild != NULL)high1 += GetHigh(t->lchild);if(t->rchild != NULL)high2 += GetHigh(t->rchild);return high1>high2?high1:high2;}//题目要求功能函数void SelectNodeHigh(Tree* t,char data,vector<Tree *> &vet){//这样保证可能存在同名节点都可以全部找出来assert(t != NULL);if(t->data == data)vet.push_back(t);if(t->lchild == NULL && t->rchild == NULL)return ;if(t->lchild != NULL)SelectNodeHigh(t->lchild,data,vet);if(t->rchild != NULL)SelectNodeHigh(t->rchild,data,vet);}int main(int argc, char* argv[]){Tree *head = BuildTree("a1a2c2d3e3a4"); //创建树cout<<GetHigh(head)<<endl;vector<Tree *> vet;SelectNodeHigh(head,'a',vet);for(vector<Tree *>::iterator p = vet.begin();p != vet.end();++p)cout<<GetHigh(*p)<<endl;DeleteTree(head);//销毁树return 0;}