判断一个数组是不是二叉树后序遍历的结果

川长思鸟来 2022-05-22 02:06 99阅读 0赞

输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。 例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：  
      8  
    /  \\  
  6  10  
 /  \\ /  \\  
5  7 9  11  
因此返回true。  
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。  
分析：这是一道trilogy的笔试题，主要考查对二元查找树的理解。  
在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于跟结点开始到跟结点前面的一个元素为止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。

#include <stdio.h>
    #include <stdlib.h>
    
    int check_walk(int A[], int length)
    {
      int i = 0;
      int j;
      int left = 1;
      int right = 1;
      
      int x = A[length-1];
      
      while(A[i]<x)
         i++;
      
      for(j = i; j<length-1; j++)
       {
         if(A[j]<x)
         return 0;
        } 
    
    if(i>0) 
      left = check_walk( A, i);
    if(i<length-1)
      right = check_walk( A+i, length-i-1);
      
    return (left && right); 
    }
    
    int main(int argc, char *argv[])
    {
      int A[] = {5,7,6,9,11,12,8}; 
      printf("%d\n",check_walk(A, 7));
      
      system("PAUSE");    
      return 0;
    }

判断一个数组序列是否符合二叉树的输出顺序

#include <stdlib.h>
    #include <stdio.h>
    
    typedef int ElementType;
    
    //后序输出
    bool VerifySequenceOfBSTBehind( ElementType A[], int N )
    {
        if ( A == NULL || N <= 0 )
        {
            return false;
        }
        ElementType root = A[N - 1];
        int i, j;
        for ( i = 0; i < N - 1; i++ )
        {
            if ( A[i] > root )
            {
                break;
            }
        }
    	
        for ( j = i; j < N - 1; j++ )
        {
            if ( A[j] < root )
            {
                return false;
            }
        }
    	
    	
        bool left = true, right = true;
    	
        if ( i > 0 )
        {
            left = VerifySequenceOfBSTBehind( A, i );
        }
    	
        if ( i < N - 1 )
        {
            right = VerifySequenceOfBSTBehind( A + i, N - i - 1 );
        }
    	
        return left&&right;
    	
    }
    
    //前序输出
    bool VerifySequenceOfBSTFore( ElementType A[], int N )
    {
        if ( A == NULL || N <= 0 )
        {
            return false;
        }
        ElementType root = A[0];
        int i, j;
        for ( i = 1; i < N; i++ )
        {
            if ( A[i] > root )
            {
                break;
            }
        }
    	
        for ( j = i; j < N; j++ )
        {
            if ( A[j] < root )
            {
                return false;
            }
        }
    	
    	
        bool left = true, right = true;
    	
        if ( i > 1 )
        {
            left = VerifySequenceOfBSTFore( A + 1, i - 1 );
        }
    	
        if ( i < N )
        {
            right = VerifySequenceOfBSTFore( A + i, N - i);
        }
    	
        return left&&right;
    	
    }
    
    int main()
    {
        ElementType A[] = {12,25,71,68,33,34};
        int N = sizeof(A)/sizeof(A[0]);	
        printf("%d\n", VerifySequenceOfBSTFore( A, N ));
    }