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

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回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() */

赞 (0)

相关推荐

  • 二叉树的非递归后序遍历算法实例详解

    前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中.方法有很多,这里只举一种,先定义栈结点的数据结构 复制代码 代码如下: typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,往左下方走,一直走到头,将路径上

  • C语言数据结构树之后序遍历的实现

    C语言数据结构树之后序遍历的实现

    后续遍历的实现: 数据结构树中的后续遍历,这里提供简单实例,代码中有注释,大家参考下! 看下实现效果: 题目及分析 给定树的先序遍历和中序遍历,求后续遍历 输入 abdec dbeac 输出 debca 三.实现代码: #include <iostream> #include <string> using namespace std; string s1="abdec";//先序遍历 string s2="dbeac";//中序遍历 void

  • 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

    如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data; 

  • C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法

    本文实例讲述了C#使用前序遍历.中序遍历和后序遍历打印二叉树的方法.分享给大家供大家参考.具体实现方法如下: public class BinaryTreeNode { public BinaryTreeNode Left { get; set; } public BinaryTreeNode Right { get; set; } public int Data { get; set; } public BinaryTreeNode(int data) { this.Data = data;

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

    题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果.如果是返回true,否则返回false.例如输入5.7.6.9.11.10.8,由于这一整数序列是如下树的后序遍历结果.    8    / \  6   10 / \    / \ 5  7 9 11因此返回true.如果输入7.4.6.5,没有哪棵树的后序遍历的结果是这个序列,因此返回false.本题网上已经有用递归单纯判断的解法. 个人解法: 先得到序列对应的中序序列, 然后看中序序列是否从小到大有序, 得出判断. 相比

  • C语言实现输入一颗二元查找树并将该树转换为它的镜像

    本文实例讲述了C语言实现输入一颗二元查找树并将该树转换为它的镜像的方法,分享给大家供大家参考.具体实现方法如下: 采用递归方法实现代码如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> #include <iterator> #include <algorithm> using namespace std; struct Node { Node(int

  • JQuery查找子元素find()和遍历集合each的方法总结

    1.HTML代码 <div name="students" school="HK"> <input type="boy" name="ZhangSan" value="206"> <input type="girl" name="Lisi" value="108"> </div>  2.jquery

  • Java语言实现非递归实现树的前中后序遍历总结

    Java语言实现非递归实现树的前中后序遍历总结

    前言 三种遍历的递归写法都很好写,所以总结一下非递归写法. 先贴一张图复习一下三种遍历方式就进入正文啦~ [注:本文所有代码实现中树的结点定义如下: public class Node { int val; Node left; Node right; Node parent; Node() {} Node(int val) { this.val = val; } } 1.前序遍历 实现思路: 前序遍历的顺序是:根结点 -> 左孩子 -> 右孩子 借助一个栈结构先将根结点压入栈,然后循环每次取

  • PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法

    本文实例讲述了PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法.分享给大家供大家参考,具体如下: 先来看看前序遍历.中序遍历与后序遍历原理图: 根据树的前序遍历和中序遍历构造树并输出后序遍历代码如下: <?php class BinaryTreeNode{ public $m_value; public $m_left; public $m_right; } function ConstructCore($preorder,$inorder){ if(count($preorder)!

  • LintCode-排序列表转换为二分查找树分析及实例

    给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树 您在真实的面试中是否遇到过这个题? 分析:就是一个简单的递归,只是需要有些链表的操作而已 代码: /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } * Defin

  • 一波C语言二元查找树算法题目解答实例汇总

    一波C语言二元查找树算法题目解答实例汇总

    按层次遍历二元树 问题描述:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印.  例如输入: 8 / / 6 10 / / / / 5 7 9 11 输出 8 6 10 5 7 9 11 定义二元树(其实是二元搜索树,但并不遍历算法)的结点为: struct BSTreeNode { int value; BSTreeNode *left; BSTreeNode *right; }; 思路:利用队列的先进先出,很容易实现.每次取出队列的首元素,然后将其左右子女放入队列

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • javascript先序遍历DOM树的方法

    DOM树由文档中的所有节点(元素节点.文本节点.注释节点等)所构成的一个树结构,DOM树的解析和构建是浏览器要实现的关键功能.既然DOM树是一个树结构,那么我们就可以使用遍历树结构的相关方法来对DOM树进行遍历,同时DOM2中的"Traversal"模块又提供了两种新的类型,从而可以很方便地实现DOM树的先序遍历. 注:本文中的5种方法都是对DOM的先序遍历方法(深度优先遍历),并且只关注Element类型. 1. 使用DOM1中的基础接口,递归遍历DOM树 DOM1中为基础类型Nod

  • Python实现树的先序、中序、后序排序算法示例

    本文实例讲述了Python实现树的先序.中序.后序排序算法.分享给大家供大家参考,具体如下: #encoding=utf-8 class Tree(): def __init__(self,leftjd=0,rightjd=0,data=0): self.leftjd = leftjd self.rightjd = rightjd self.data = data class Btree(): def __init__(self,base=0): self.base = base #前序遍历 根

随机推荐