程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 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() */
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved