深入分析由前序和中序重构二叉树问题-白红宇

深入分析由前序和中序重构二叉树问题

阅读量：6294 次

发布时间：2019-06-22

本文共 2280 字，大约阅读时间需要 7 分钟。

由以下的这棵树来分析

前序遍历：

ACFKDBUMWS

中序遍历：

KFDCAUBWMS

实际前序遍历的组成是

根节点+左边+右边

实际中序遍历的组成是

左边+根节点+右边

step1

前序遍历的第一个为根结点，所以A为根节点，

step2

在中序中找到A，分为两组

KFDC 根节点左边

UBWMS 根节点右边

而前序遍历中也能够分开了（仅仅是顺序不一样，个数一样）

CFKD 是左边

BUMWS是右边

step 3

在左边CFKD又一次作为一颗整树。反复步骤一和步骤二，根节点为C，

在中序中找到C，在分为左右边，

理论是能够实现又一次构建一棵树。怎样用编程语言实现？

採用一种递归方法

前序遍历

根+左+右

中序遍历

左+根+右

伪代码

struct node

{

char data;

struct node* left;

struct node* right;

}

struct node* creat(前序遍历字符串f，中序遍历字符串m)

{

struct node n;

n.data=从f中获取根；

fl=前序遍历根的左边；

fr=前序遍历根的右边。

ml=中序遍历根的左边；

mr=中序遍历根的右边。

n.left=creat(fl.ml);

n.right=creat(fr,mr);

return  n;

}

另一个问题，递归的结束问题，什么时候结束。

以一个简单例子说明

前序遍历

ABC

中序遍历

BAC

根A+左B+右C

左B+根A+右C

进入creat函数后

f=“ABC”; m=“BAC”

fl=‘B’ ；fr=’C’

ml=’B’ ; mr=’C’

然后fl和ml进入递归

f=‘B’；m=‘B’

此时，就不再出现左子树和右子树了，非常明显这个时候能够全身而退了。

左子树个数=0。

右子树个数=0;

说明左右子树都没有了这是就退

伪代码

struct node{    char data;    struct node* left;    struct node* right;}struct node* creat(前序遍历字符串f。中序遍历字符串m){    struct node n;    n.data=从f中获取根；    fl=前序遍历根的左边；    fr=前序遍历根的右边。    ml=中序遍历根的左边；    mr=中序遍历根的右边。    if(左子树长度==0)    {         n.left=NULL;    }    else         n.left=creat(fl.ml);   if(右子树长度==0)    {        n.right=NULL;    }    else    {        n.right=creat(fr,mr);    }    return  n;}

c代码实现

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef struct node{ char data; struct node* left; struct node* right;}NODE;//qian creatNODE* creat_node(string &f,string &m){ char c; string fl,fr; string ml,mr; int local; c=f[0]; if(c>'Z' || c<'A') {  cout<<"error data"<
          
           data  = c; if(local == 0)  node->left = NULL; else  node->left  = creat_node(fl,ml); if((m.size()-1-local)==0)  node->right = NULL; else  node->right = creat_node(fr,mr); return node;}void front_search(NODE* root){ if(root == NULL)  return; NODE node=*root; cout<