首页 > 代码库 > 最基础的算法练习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 }
最基础的算法练习2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。