服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - 判断整数序列是否为二元查找树的后序遍历结果的解决方法

判断整数序列是否为二元查找树的后序遍历结果的解决方法

2020-12-11 15:39C语言教程网 C/C++

本篇文章是对判断整数序列是否为二元查找树的后序遍历结果的解决方法进行了详细的分析介绍,需要的朋友参考下

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果.
      8
     / \
   6   10
  / \    / \
  5  7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
本题网上已经有用递归单纯判断的解法.
个人解法: 先得到序列对应的中序序列, 然后看中序序列是否从小到大有序, 得出判断.
相比:时间复杂度相同, 增加N的空间, 但可求得对应的中序序列.
以下为代码:

复制代码 代码如下:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 100
int seq[LEN + 1] = {0};
int *mid = NULL;
int pos = 1;
void getmid(int start, int end);
int check(int num);
int main()
{
 int val;
 int num;
 int ret;
 int i;
 printf("input the sequence, end it with '-9999': ");

 num = 1;
 scanf("%d", &val);
 while(val != -9999)
 {
  seq[num] = val;
  num ++;
  scanf("%d", &val);
 }
 num--;
 mid = (int *)malloc((num + 1) * sizeof(int));
 if(mid == NULL)
 {
  printf("malloc failed.\n");
  exit(1);
 }
 memset(mid, 0, num + 1);
 getmid(1, num);

 printf("mid: ");
 for(i = 1; i< num +1; i++)
 {
  printf("%d ", mid[i]);
 }
 printf("\n");
 ret = check(num);
 if(ret == -1)
 {
  printf("no.\n");
 }
 else
 {
  printf("yes\n");
 }
 return 0;
}/* main() */
void getmid(int start, int end)
{
 int flag;
 if(start > end)
 {
  return;
 }
 if(start == end)
 {
  mid[pos] = seq[end];
  pos ++;
  return;
 }
 int par;
 par = start;
 flag = 0;
 while(par < end)
 {
  if(seq[par] > seq[end])
  {
   flag = 1;
   getmid(start, par - 1);
   mid[pos] = seq[end];
   pos ++;   
   getmid(par, end - 1);
   break;
  }
  par ++;
 }
 if(!flag)
 {
  getmid(start, end-1);
  mid[pos] = seq[end];
  pos ++;
 }
}/* getmid */
int check(int num)
{
 int i;

 for(i = 1; i < num; i++)
 {
  if(mid[i] > mid[i+1])
  {
   return -1;
  }
 }
 return 0;
}/* check() */

延伸 · 阅读

精彩推荐