白书8.4&&8.5 树的遍历及重建

树的遍历有三种方式.

1.前序遍历 先访问根节点，左子树，右子树

2.中序遍历 先左再根最后右

3.后续遍历 先左再右最后根.

 实现遍历的三种差别在于输出位置的函数位置不同

1.前序遍历的函数.

prewalk(u)
  if u==nil return ;
print u
prewalk(左子树)
prewalk(右子树）

2.中序

prewalk(u)
  if u==nil return ;
prewalk(左子树)
print u
prewalk(右子树）

3.后序

prewalk(u)
  if u==nil return ;
prewalk(左子树)
prewalk(右子树）
print u

然后如果我们有了一个树的先序和中序遍历，就能重建一个树.

先序 1 2 3 4 5 6 7 8 9 

中序 3 2 5 4 6 1 8 7 9 

先在先序取出一个点作为根 然后用这个根将中序划分成两部分

第一步 取1 把 中序分为 3 2 5 4 6  1  8 7 9

然后继续 再以2为根 又把上面分开的左边(3 2 5 4 6)

分为 (3 2 5 4 6） 以此类推 递归下去 就能重建一颗树.

最后重建树的代码:

#include
#include
#include
#include
using namespace std;
vector pre,post,in;
int pos=0;
void rec(int l,int r){
 if(l>=r) return ; 
 int root=pre[pos++];
 int dis=distance(in.begin(),find(in.begin(),in.end(),root));
 rec(l,dis);
 rec(dis+1,r);
 post.push_back(root);
}
int main(){ int i,j,k,n;cin>>n;
for(i=1;i>k; pre.push_back(k);
}
for(i=1;i>k;in.push_back(k);
}
 rec(0,pre.size());
for(i=0;i