树的遍历，在构造树的过程中，多个孩子用vector来表示，有的时候孩子需要排序
PAT A1053
dfs有权树然后输出路径权值和目标相同的，必须走到叶子节点。另外要求输出按照非降序输出（这个非降序，仅考虑A>B 在min(lena,lenb)中，第一个不等的是A[i]>B[I]），不考虑长度不同。
解题思路
这个就是正常dfs，存储当前节点和遍历情况，注意在dfs中，保存遍历的判定条件需要在dfs结束当前轮的时候修改，但是保存结果的不用修改，自动顶掉了。
还有cmp数组，这个序号是已知的，只需要对里面的孩子节点进行一下排序，并且只需要考虑大小，因为认为3 2 3 和3 2 3 4也算非降序。
#include<stdio.h> #include<iostream> #include<vector> #include<algorithm> #define maxn 100 using namespace std; int n,nonleafnum,target; int ansroute[105]; using namespace std; struct node{ int w; vector<int>child; }Node[maxn]; bool cmp(int a,int b) { return Node[a].w>Node[b].w; } void dfs(int nodenum,int sum,int num)//当前节点编号，目前总价，这是第几个节点 { if(target==sum+Node[nodenum].w && Node[nodenum].child.size()==0) { ansroute[num]=nodenum; for(int i=0;i<=num-1;i++) { printf("%d ",Node[ansroute[i]].w); } printf("%d ",Node[ansroute[num]].w); return ; } if(Node[nodenum].child.size()==0||(sum+Node[nodenum].w>=target)) return ; ansroute[num]=nodenum; sum=sum+Node[nodenum].w; for(int i=0;i<Node[nodenum].child.size();i++) { dfs(Node[nodenum].child[i],sum,num+1); } } int main() { scanf("%d %d %d",&n,&nonleafnum,&target); for(int i=0;i<=n-1;i++) { int tempw; scanf("%d",&tempw); Node[i].child.clear(); Node[i].w=tempw; } for(int i=1;i<=nonleafnum;i++) { int temp,tempnum,tempchild; scanf("%d%d",&temp,&tempnum); for(int j=1;j<=tempnum;j++) { scanf("%d",&tempchild); Node[temp].child.push_back(tempchild); } sort(Node[temp].child.begin(),Node[temp].child.end(),cmp); } dfs(0,0,0);//当前坐标，当前已有w数值， return 0; }
借着这个输入格式实现了一下先根遍历和层次遍历。这个因为存在vector.size()，就不用NULL了，原理都差不多。
（先根遍历，是先走根节点，本质跟dfs一样，层次是bfs）
#include<stdio.h> #include<iostream> #include<vector> #include<algorithm> #define maxn 100 #include<queue> using namespace std; int n,nonleafnum,target; int ansroute[105]; using namespace std; struct node{ int w; vector<int>child; }Node[maxn]; bool cmp(int a,int b) { return Node[a].w>Node[b].w; } void preOrder(int root) { printf("%d ",Node[root].w); for(int i=0;i<Node[root].child.size();i++) preOrder(Node[root].child[i]); } void layerOrder(int root) { queue<int>q; q.push(root); while(!q.empty()) { int temp=q.front(); q.pop(); printf("%d ",Node[temp].w); for(int i=0;i<Node[temp].child.size();i++) { q.push(Node[temp].child[i]); } } } int main() { scanf("%d %d %d",&n,&nonleafnum,&target); for(int i=0;i<=n-1;i++) { int tempw; scanf("%d",&tempw); Node[i].child.clear(); Node[i].w=tempw; } for(int i=1;i<=nonleafnum;i++) { int temp,tempnum,tempchild; scanf("%d%d",&temp,&tempnum); for(int j=1;j<=tempnum;j++) { scanf("%d",&tempchild); Node[temp].child.push_back(tempchild); } } preOrder(0); printf(" "); layerOrder(0); return 0; }
二叉搜索树
这个就是左子树里面的点都小于右子树里面的点。唯一需要注意的就是删除的时候不能直接让root等于其他的节点，因为还有别的指针关系，在root不是NULL的时候修改root的值，根据左右子树是否为空的情况选中前驱或者后驱。选前后驱时候里面的参数是左右子节点的指针哦。然后删除对应前后驱的时候记得用delete，因为他们可能还有子节点，直接释放是不可以的。部分代码如下（这里面的insert有重复的数就不插入了，实际题目一般不是这种，审题）
这里面有一部分常见操作：findMax是前驱，找左子树里面最大的。这里面insert和delete是引用node*&root
#include<stdio.h> #include<iostream> #include<queue> using namespace std; struct node { int data; node*lchild; node*rchild; }; node*newNode(int x) { node*temp=new node; temp->data=x; temp->lchild=NULL; temp->rchild=NULL; } void search(node*root,int x) { if(root==NULL) { printf("search failed "); return ; } if(x==root->data) { printf("%d ",root->data); } else if(x<root->data) { search(root->lchild,x); } else search(root->rchild,x); } void insert(node*&root,int x) { if(root==NULL) { root=newNode(x); return ; } if(root->data==x) return; else if(x<root->data) { insert(root->lchild,x); } else insert(root-<rchild,x); } node*Create(int data[],int n) { node*root=NULL; for(int i=0;i<n;i++) { insert(root,data[i]); } return root; } node*findMax(node*root) { while(root->rchild!=NULL) root=root->rchild; return root; } node*findMin(node*root) { while(root->lchild!=NULL) root=root->lchild; return root; } void deleteNode(node*&root,int x) { if(root==NULL) return; if(root->data==x) { if(root->lchlid==NULL && root->rchild==NULL) root=NULL; else if(root->lchild!=NULL) { node*temp=findMax(root->lchild); root->data=temp->data; delete(root->lchild,temp->data); } else { node*temp=findMin(root->rchild); root->data=temp->data; delete(root->rchild,temp->data); } } else if(root->data>x) deleteNode(root->lchild,x); else deleteNode(root->rchild,x); }
PAT A1043
这个是给一组数构造二叉搜索树，判断构造出来的前序是否和这个相同，如果相同输出后序。如果跟镜像相同，输出镜像树的后序，他们不是直接倒着输出数组的关系哦，最好还是自己写函数，简单调整一下递归顺序就行。
另外需要注意的点：最后一个不能有空格，那么就必须存储结果之后统一输出。
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; struct node{ int data; node*lchild; node*rchild; }; int n; int a[1000]; int ans[1000]; int ans2[1000]; int count=0; int count2=0; node*newNode(int x) { node*temp=new node; temp->data=x; temp->lchild=NULL; temp->rchild=NULL; return temp; } void insert(node*&root,int x) { if(root==NULL) { root=newNode(x); return; } if(x<root->data) insert(root->lchild,x); else insert(root->rchild,x); } void preOrder(node*root) { if(root==NULL) return; //printf("%d",root->data); ans[count++]=root->data; preOrder(root->lchild); preOrder(root->rchild); } void mirrorOrder(node*root) { if(root==NULL) return ; ans2[count2++]=root->data; mirrorOrder(root->rchild); mirrorOrder(root->lchild); } void postOrder(node*root) { if(root==NULL) return ; postOrder(root->lchild); postOrder(root->rchild); //printf("%d ",root->data); ans[count++]=root->data; } void mirrorPost(node*root) { if(root==NULL) return; mirrorPost(root->rchild); mirrorPost(root->lchild); //printf("%d ",root->data); ans2[count2++]=root->data; } int main() { node*root=new node; root=NULL; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); insert(root,a[i]); } preOrder(root); mirrorOrder(root); bool pd1=true; bool pd2=true; for(int i=0;i<n;i++) { //printf("%d",ans[i]); if(ans[i]!=a[i]) pd1=false; if(ans2[i]!=a[i]) pd2=false; } if(pd1) { count=0; printf("YES "); postOrder(root); for(int i=0;i<=n-2;i++) printf("%d ",ans[i]); printf("%d",ans[n-1]); } else if(pd2) { count2=0; printf("YES "); mirrorPost(root); for(int i=0;i<=n-2;i++) printf("%d ",ans2[i]); printf("%d",ans2[n-1]); } else printf("NO "); return 0; }