二叉树遍历


title: 二叉树遍历
date: 2017-04-04 22:05:21
categories: C/C++

tags: 二叉树

春天来了,草长莺飞,正是准备找工作的好时机,也是时候把丢掉的东西在熟悉一下了。

所谓遍历

前序遍历:即先根序遍历
中序遍历:即中根序遍历
后序遍历:即后根序遍历
整体来讲先左子树,后右子树的顺序不会变,变的只是根的位置,这样根分别在不同的位置就对应着上面的三种遍历方式。

具体使用

关于二叉树的题目最常见的也就是两点:
1.根据前中根序遍历->后根序遍历的结果
2.根据中后根序遍历->前根序遍历的结果

其实这个问题最最重要的便是构建出整个树,至于求什么遍历,具体方法就在上面的概念里面了,一波递归就好了。所以下面主要还是求如何根据遍历结果逆推构建二叉树。

前中根序遍历构建二叉树

tree.png
上面的图例已经很清楚的说明了如何通过遍历来构建整个二叉树的思路,为了易于程序实现,我们给出一个最简单的接口:
1.二叉树的根节点
2.二叉树的前根序遍历的数组,包括开始和结尾元素的下标
3.二叉树的中根序遍历的数组,包括开始和结尾元素的下标
二叉树节点的结构体描述:

typedef struct node {
  int  data;
  struct node *lchild;
  struct node *rchild;
}Node;
/* 
    PreS       先根序序列的第一个元素下标 
    PreE       先根序序列的最后一个元素下标 
    InS        中根序序列的第一个元素下标  
    InE        先根序序列的最后一个元素下标   
    PreArray   先根序序列数组 
    InArray    中根序序列数组 
*/  
PreInCreateTree(Node *&T,int PreS ,int PreE ,int InS ,int InE)
{  

    int RootIndex;  
    //先根序第一个字符  
    T = (Node*)malloc(sizeof(Node));  
    T->data = PreArray[PreS];  

    //寻找该结点在中序序列中的位置  
    for(int i = InS;i <= InE;i++){  
        if(T->data == InArray[i]){  
            RootIndex = i;  
            break;  
        }  
    }  
    int leftLen = RootIndex - InS - 1;
    int rightLen = RootIndex;
    //根结点的左子树不为空  
    if(RootIndex != InS){  
        //以根节点的左结点为根建树  !!!特别注意传递的数组的开始和结尾的下标,别问我为什么提示(我哭一会先)
        PreInCreateTree(T->lchild,PreS+1,(RootIndex-InS)+PreS-1,InS,RootIndex-1);  
    }  
    else{  
        T->lchild = NULL;  
    }  
    //根结点的右子树不为空  
    if(RootIndex != InE){  
        //以根节点的右结点为根建树  !!!特别注意传递的数组的开始和结尾的下标
        PreInCreateTree(T->rchild,PreS+1+(RootIndex-InS),PreE,RootIndex+1,InE);  
    }  
    else{  
        T->rchild = NULL;  
    }  
} 

中后根序遍历构建二叉树

/* 
    MidS        中根序序列的第一个元素下标 
    MidE        中根序序列的最后一个元素下标 
    AftS        后根序序列的第一个元素下标  
    AftE        后根序序列的最后一个元素下标   
    MidArray    中根序序列数组 
    AftArray    后根序序列数组 
*/  
MidAfterCreateTree(Node *&T,int MidS ,int MidE ,int AftS ,int AftE)
{ 
    int RootIndex = 0;
    T = (Node*)malloc(sizeof(Node));
    T->data = AftArray[AftE];
    for(int i = MidS ; i <= MidE; i++)
    {
        if(T->data == MidArray[i])
        {
            RootIndex = i;
            break;
        }
    }
    
    if(RootIndex != MidS)
    {
        MidAfterCreateTree(T->lchild,MidS,(RootIndex -1),AftS,(RootIndex - 1-MidS + AftS));
    } 
    else
    {
        T->lchild = NULL;
    }
        
        
    if(RootIndex != MidE)
    {
        MidAfterCreateTree(T->rchild,(RootIndex + 1),MidE,(AftE -MidE + RootIndex),(AftE - 1));
    }
    else
    {
        T->rchild = NULL;
    }
        
}

参考链接:
1

文章版权:My-World - 勿于浮沙筑高台

本文链接:http://doachieveit.cn/index.php/archives/41.html

版权声明:本文为作者原创,转载请注明文章原始出处 !

添加新评论