锐客网

  1. 首页 > it技术 > >

二叉树例题

1.HDU 1710
题意：已知二叉树的前序遍历和中序遍历，求后序遍历；
思路：把先序序列的第一个数字当作一个根，在中序序列中找到这个数字，则中序序列中根前面的序列为根的左子树，后面的序列为右子树。假如中序历遍中第i个点是根节点，那么划分为两个区域，0~i和i~n-1；

#include #include using namespace std; int a[1005]; int k; void postorder(int *p, int *q, int len){ if(len == 0)//长度为0，返回 return; int t = 0; int s = *p; for(; t < len; t ++){ if(q[t] == *p){//找到当前中序遍历中第一个与当前前序遍历相同的点 break; } } postorder(p+1, q, t); //求左子树 postorder(p+t+1, q+t+1, len-t-1); //求右子树 a[k++] = s; } int main(){ int n, i, j; int p[1005], q[1005]; while(cin>>n){ for(i = 0; i < n; i ++){ cin>>p[i]; } for(j = 0; j < n; j ++){ cin>>q[j]; } k = 0; postorder(p, q, n); for(i = 0; i < k-1; i ++){ cout<' '; } cout<1]<
【二叉树例题】2.拓展：已知中序，后序，求前序；
#include"iostream" using namespace std; int pre[30]; int in[30]; int post[30]; int indexOfRootIn(int start,int stop,int root){ for(int j=start; j<=stop; j++){ if(in[j]==root){ return j; } } return -1; } /*void postOrder(int pre_start,int pre_end,int in_start,int in_end,int length){ if(length==0) return; if(length==1){ cout<>N; for(int i=0; i>post[i]; } for(int i=0; i>in[i]; } preOrder(0,N-1,0,N-1,N); return 0; }


转载于:https://www.cnblogs.com/cccyx/p/11537623.html

    推荐阅读


    上一篇：你们以前不是好朋友，以后也不是

    下一篇：你不知道的“挂画黄金法则”(漫画图解)