tree

树的一些知识点

Expression trees, B and B* trees, red-black trees, quad trees, PQ trees

uva,536

为一棵n叉树，k为深度

考虑到所以猫的高度:  Ih(1+n/(n+1)+n*n/(n+1)*(n+1)+.....+n^k/(n+1)^k)

不工作的猫:1+n+n^2+....+n^k-Lc

得到。Lc=n^k    Ih=(n+1)^k

求n  log(Ih)/log(n+1)=log(Lc)/log(n);

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cmath>
 5 #define eps 1e-10
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int Ih,Lc;
11     int left,right;
12     while(~scanf("%d %d",&Ih,&Lc))
13     {
14         if(!Ih && !Lc)
15             break;
16         int n,k=0;
17         if(Lc==1)  //考虑情况为1，因为对等比数列来说，公比不能为一
18 //否则求前n项和就rte，
19         {
20             left=(ceil)(log(Ih)/log(2));  //int取整+0.5或者ceil
21             right=2*Ih-1;
22         }
23         else
24         {
25         for(n=1;n<=Lc;n++)
26         {
27             if(fabs(log(n)*log(Ih)-log(Lc)*log(n+1))<eps)
28                 break;
29         }
30         k=(int)(log(Ih)/log(n+1)+0.5);
31         left=(1-Lc)/(1-n);  
32         right=(n+1)*Ih-n*Lc;
33         }
34         printf("%d %d
",left,right);
35     }
36     return 0;
37 }
View Code
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cmath>
 5 #define eps 1e-10
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int Ih,Lc;
11     int left,right;
12     while(~scanf("%d %d",&Ih,&Lc))
13     {
14         if(!Ih && !Lc)
15             break;
16         int n=1,k=0;
17         if(Lc==1)
18         {
19             left=(ceil)(log(Ih)/log(2));
20             right=2*Ih-1;
21         }
22         else
23         {
24         while(fabs(log(n)*log(Ih)-log(Lc)*log(n+1))>eps)
25             n++;
26         k=(int)(log(Ih)/log(n+1)+0.5);
27         left=(1-Lc)/(1-n);
28         right=(n+1)*Ih-n*Lc;
29         }
30         printf("%d %d
",left,right);
31     }
32     return 0;
33 }
其实不用考虑n的范围，不需要额外的空间

uva,536

前跟：先访问根再访问左再访问右子树

中跟：先访问左再访问根在访问右子树

后跟：先访问左子树再访问右子树再访问根

通过前根的点在中根中位置确定左右子树，然后递归最右再最左，压栈，压栈的顺序和后根遍历的顺序正好相反。

例如：DBACEGF  ABCDEFG

先对D找到在中根的位置，然后访问右边，然后找到E然后G然后F然后B,C,A，

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <stack>
 5 
 6 using namespace std;
 7 
 8 stack<char> st;
 9 char PD[30],ID[30];
10 
11 void find(int p1,int p2,int q1,int q2)
12 {
13     if(p1>p2) return;
14     st.push(PD[p1]);
15     int root=q1;
16     for(;ID[root]!=PD[p1];++root);
17     find(root+1-q1+p1,p2,root+1,q2);
18     find(p1+1,root-q1+p1,q1,root-1);
19 }
20 
21 int main()
22 {
23     while(cin>>PD>>ID)
24     {
25         int L=strlen(PD)-1;
26         find(0,L,0,L);
27         while(!st.empty())
28         {
29             char c=st.top();
30             st.pop();
31             printf("%c",c);
32         }
33         printf("
");
34     }
35     return 0;
36 }
dfs压栈的思维

通过先根和中根建树然后根据后根去遍历输出 （重写）

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 char PD[30],ID[30];
 8 
 9 struct Node
10 {
11     Node *left;
12     Node *right;
13     char c;
14     Node(char c)
15     {
16         this->c=c;
17         this->left=left;
18         this->right=right;
19     }
20 };
21 
22 Node *root;
23 
24 Node *Create_Tree(char *pre,char *min,int len)
25 {
26     if(!len)
27         return NULL;
28     int p=0;
29     while(min[p]!=pre[0])
30         p++;
31     Node *root=new Node(pre[0]);
32     root->left=Create_Tree(pre+1,min,p);
33     root->right=Create_Tree(pre+p+1,min+p+1,len-p-1);
34     return root;
35 }
36 
37 void print_Post(Node *r)
38 {
39     if(r!=NULL)
40     {
41         print_Post(r->left);
42         print_Post(r->right);
43         printf("%c",r->c);
44     }
45 }
46 
47 int main()
48 {
49     while(cin>>PD>>ID)
50     {
51         int L=strlen(PD);
52         root=Create_Tree(PD,ID,L);
53         print_Post(root);
54         puts("");
55     }
56     return 0;
57 }
建树输出

直接dfs递归求解，自己抽象出栈。

 1 #include <iostream>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 char PD[30],ID[30];
 6 
 7 void dfs(int p1,int p2,int q1,int q2,int root)
 8 {
 9     if(p1>p2)
10         return;
11     for(root=q1;ID[root]!=PD[p1];++root);
12     dfs(p1+1,root-q1+p1,q1,root-1,0);
13     dfs(root+1-q1+p1,p2,root+1,q2,0);
14     cout<<ID[root];
15 }
16 
17 int main()
18 {
19     while(cin>>PD>>ID)
20     {
21         int L=strlen(PD)-1;
22         dfs(0,L,0,L,0);
23         cout<<endl;
24     }
25     return 0;
26 }
dfs重写

 uva,122

 1 #include <iostream>
 2 #include <string>
 3 #include <sstream>
 4 #include <list>
 5 
 6 using namespace std;
 7 //建树
 8 struct NODE
 9 {
10     int nVal;
11     NODE *pL;
12     NODE *pR;
13 }
14 //初始化空节点
15 const NullNode={0,0,0};
16 //删除树，避免泄漏内存
17 void DeleteTree(NODE *pPar)
18 {
19     if(pPar!=NULL)
20     {
21         DeleteTree(pPar->pL);
22         DeleteTree(pPar->pR);
23     }
24     delete pPar;
25 }
26 //生成二叉树
27 NODE* AddChild(NODE* pPar,int nVal,const char *pPath)
28 {//如果pPar为0，则初始化
29     if(pPar==0)
30         pPar=new NODE(NullNode);
31     switch(*pPath)
32     {
33         case ')':pPar->nVal=(pPar->nVal==0 && nVal!=0)?nVal:-1;break;
34 //左子孙
35         case 'L':pPar->pL=AddChild(pPar->pL,nVal,pPath+1);break;
36 //右子孙  
37       case 'R':pPar->pR=AddChild(pPar->pR,nVal,pPath+1);break;
38     }
39     return pPar;
40 }
41 
42 int main()
43 {
44     NODE* pRoot=0;
45     
46     for(string strToken;cin>>strToken;)
47     {
48         const char *pStr=strToken.c_str(); //超赞的方法
49         int nVal=0;
50         
51         if(pStr[1]!=')')
52         {
53             for(;isdigit(*++pStr);nVal=nVal*10+*pStr-'0');
54             if(*pStr!=',') while(true);  //报错，如果不是','则lld输入不正确
55             pRoot=AddChild(pRoot,nVal,++pStr);
56             continue;
57         }
58         //层次遍历用链表存储树，如果遍历到尾部，继续返回首部遍历
59        //并在原地插入子孙节点
60         list<NODE*> Level(1,pRoot);
61         stringstream ss;
62         for(list<NODE*>::iterator it=Level.begin();!Level.empty();
63             it=(it==Level.end()?Level.begin():it))
64         {
65             NODE* pTemp=*it;
66             it=Level.erase(it);
67             
68             if(pTemp==0)
69                 continue;
70             if(pTemp->nVal<=0)
71             {
72                 Level.clear();
73                 ss.str("");
74                 break;
75             }
76                 ss<<pTemp->nVal<<' ';
77                 it=Level.insert(it,pTemp->pL),++it;
78                 it=Level.insert(it,pTemp->pR),++it;
79             
80         }
81         DeleteTree(pRoot);
82         pRoot=0;
83         strToken=ss.str();
84         if(strToken.empty())
85         {
86             strToken="not complete";
87         }
88         else
89         {
90             strToken.erase(strToken.end()-1);
91         }
92 
93         cout<<strToken<<endl;
94     }
95     return 0;
96 }
View Code
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 #include <algorithm>
 5 #include <sstream>
 6 #include <vector>
 7 #include <map>
 8 
 9 using namespace std;
10 
11 
12 struct Node
13 {
14     int id;
15     string routine;
16     Node(int x,string str):id(x),routine(str){}
17     bool operator<(const Node& n)const
18     {
19         if(routine.size()<n.routine.size()) return true;
20         else if(routine.size()==n.routine.size()) return routine<n.routine;
21         else return false;
22     }
23 };
24 
25 
26 string str;
27 map<string,int> mp;
28 vector<Node> vt;
29 
30 bool Input()
31 {
32     mp.clear();
33     vt.clear();
34     bool input=false;
35     while(cin>>str and str!="()")
36     {
37         input=true;
38         stringstream ss(str);
39         char ch;int x;string tmp;
40         ss>>ch>>x>>ch>>tmp;
41         tmp.erase(tmp.size()-1);
42         vt.push_back(Node(x,tmp));
43     }
44     return input;
45 }
46 
47 inline string Parent(string &str)
48 {
49     return str.substr(0,str.size()-1);
50 }
51 
52 int main()
53 {
54     while(Input())
55     {
56         sort(vt.begin(),vt.end());
57         bool NO=vt[0].routine!="";
58         mp[""]=1;
59         for(int i=1;i<vt.size() and !NO;i++)
60         {
61             string par=Parent(vt[i].routine);
62             if(mp.count(par)==0 or mp.count(vt[i].routine)!=0)
63             {
64                 NO=true;
65                 break;
66             }
67             mp[vt[i].routine]++;
68         }
69         
70         if(NO)
71             cout<<"not complete"<<endl;
72         else
73         {
74             for(int i=0;i<vt.size()-1;i++)
75                 cout<<vt[i].id<<" ";
76             cout<<vt.back().id<<endl;
77         }
78     }
79     return 0;
80 }
用stl重写了，不需要太多用到树
活在现实，做在梦里。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/do-it-best/p/5395980.html