首页 > 代码库 > 最基础的算法练习2

最基础的算法练习2

恢复二叉树

 1 #include <fstream> 2 #include <iostream> 3  4 using namespace std; 5  6 struct node 7 { 8     char c; 9     struct node *lch,*rch;10 };11 12 int count_leaf(node* tree);//统计叶子结点13 int count_deep(node* tree);//统计树的深度14 void create_tree(char* l,char* r,int i,int j,int e,int f,node** tree);//由先序遍历序列和中序遍历序列恢复二叉树15 16 int main()17 {18     //freopen("D:\\input.in","r",stdin);19     //freopen("D:\\output.out","w",stdout);20     node *tree;cout<<int(tree)<<endl<<int(&tree)<<endl;21     char pre[]="ABDGCEF";22     char in[]="DGBAECF";23     create_tree(pre,in,0,6,0,6,&tree);24     cout<<count_leaf(tree)<<endl;25     cout<<count_deep(tree)<<endl;26     return 0;27 }28 int count_leaf(node* tree)29 {30     if(tree==NULL)  return 0;31     if(tree->lch==NULL&&tree->rch==NULL)    return 1;32     return count_leaf(tree->lch)+count_leaf(tree->rch);33 }34 int count_deep(node* tree)35 {36     if(tree==NULL)  return 0;37     return 1+max(count_deep(tree->lch),count_deep(tree->rch));38 }39 void create_tree(char* l,char* r,int i,int j,int e,int f,node** tree)40 {41     int m;42     (*tree)=new node;43     (*tree)->c=l[i];44     m=e;45     while(r[m]!=l[i])    m++;46     if(m==e)    (*tree)->lch=NULL;47     else    create_tree(l,r,i+1,i+m-e,e,m-1,&(*tree)->lch);48     if(m==f)    (*tree)->rch=NULL;49     else    create_tree(l,r,i+m-e+1,j,m+1,f,&(*tree)->rch);50 }
View Code

 

最基础的算法练习2