`
java-mans
  • 浏览: 11710397 次
文章分类
社区版块
存档分类
最新评论

【100题】第九题(整数序列是否是二叉查找树后续遍历)

 
阅读更多

判断整数序列是不是二叉查找树的后序遍历结果
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。

例如:输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历(左右根)结果:

8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。

分析:最后一个输出的节点为,根节点。因为7大于根节点,所以前三个节点应该为右子树。而4应该为5左子树所以此序列不是任何一个二叉查找树的后续遍历结果。

求解思路:采用分治思想。

先是整体:最后一个为根节点,然后从前向后遍历序列,直到大于根节点(此时将左子树过滤)

然后验证:过滤掉左子树,除去根节点后,剩余节点为右子树。只要右子树所有节点大于根则正确,否则不是后序遍历序列。

分治验证:对左、右子树,采用同样的方法验证。

源码:

#include"stdio.h"
/*后序遍历,最后输出的节点,一定是根节点
  此题的解法,采用思想:分治
*/
bool Test_Squence_BST(int squence[], int length)
{
      if(squence == NULL || length <= 0)//如果输出序列为空,或者输出长度为0则返回false 
            return false;
      
      int root = squence[length - 1];//
      
      int i = 0;
      for(; i < length - 1; ++ i)//将二叉查找树,左子树过滤掉 
      {
            if(squence[i] > root)  //找到大于根的节点
                  break;
      }
      
      int j = i;//采用j的原因是,让i记录左子树个数 
      for(; j < length - 1; ++ j) //过滤掉左子树后,剩余的除了根节点外,理论上全为右子树 
      {
            if(squence[j] < root)
                  return false;//如果存在不正确的,这里就会返回false .不会继续递归调用子树 
      }
      
      bool left = true;//验证左子树,是否也为后序遍历序列 
      if(i > 0)
            left = Test_Squence_BST(squence, i);
       
      bool right = true;//验证右子树,是否也为后序遍历序列 
      if(i < length - 1)
            right = Test_Squence_BST(squence + i, length - i - 1);
      return (left && right);
}
int main()
{
	//int a[7]={5,7,6,9,11,10,8};
	int a[4]={7,4,6,5};
    if(Test_Squence_BST(a,4))
         printf("YES");
    else
         printf("NO"); 
         
} 


分享到:
评论

相关推荐

    878计算机专业基础综合20111

    在后续的分析题中,涉及了无向图的深度优先和宽度优先遍历、最小代价生成树的构建以及二叉排序树和平衡二叉树(AVL树)的构造,这些都是图论和数据结构的重要概念,具体解答如下: - 1)无向图的深度优先遍历(DFS...

    数据结构试卷

    5. 快速排序法对整数序列进行排序的具体步骤在这里无法详细展开,但基本流程是选取一个基准元素,将序列分为比基准小和大的两部分,然后对这两部分递归进行快速排序。 这些题目涉及到的数据结构知识是计算机科学...

    数据结构(C++)有关练习题

    2、实现1所要求的代码后,运行设计好的代码,将以下的几组整数序列建成搜索二叉树,并记录下它们的前序遍历序列和后序遍历序列: a. 1、3、5、7、9; b. 1、13、35、13、27; c. 50、25、78、13、44、...

    Tencent笔试题收集

    6. 二叉搜索树比较次数:在顺序插入10个数后构建的二叉搜索树中,元素62的比较次数取决于它在输入序列中的位置,通常情况下,如果62是中间值,比较次数最少;如果是最后一个,比较次数最多。 7. Hash链表长度:10个...

    华师网络学院作业答案-数据结构选择题.pdf

    - 对二叉排序树进行中根遍历可以得到递增序列,因为中根遍历的顺序是左子树-根节点-右子树,对于排序树来说,左子树的键值小于根,右子树的键值大于根。 6. **栈和队列**: - 它们都是线性结构,但栈是后进先出...

    2019清华912真题(DS部分)2

    算法利用了树的结构来高效地找到第K个节点,避免了全树遍历。 2. 原理解释:通过比较左子树和右子树的大小,可以快速定位第K大节点,减少了遍历的深度。 3. 时间复杂度证明:算法的时间复杂度与节点深度成正比,...

    山大数据结构真题

    #### 九、AVL树的构建与删除 - **知识点概述**: - AVL树是一种自平衡的二叉搜索树,通过维护节点之间的平衡因子来保持树的高度平衡。 - **题目解析**: - 已给出一个序列,要求写出建立AVL树的过程及删除某一...

    2012计算机专业基础综合联考真题(408)试卷版

    AVL树是一种自平衡二叉查找树,在任何节点处,两子树的高度差最多为1。本题中,所有非叶结点的平衡因子为1,意味着每个非叶结点都有一个孩子结点比另一个孩子结点高1层。根据平衡二叉树的性质,我们可以逐步构建出这...

    北航软件工程硕士2008年试题与答案

    要判断一棵二叉树是否为二叉排序树,可以利用中序遍历的特性。对于二叉排序树而言,其任何节点的左子树中的所有节点值均小于该节点值,而右子树中的所有节点值均大于该节点值。因此,对二叉树进行中序遍历时,节点值...

    唯品会2018校招前端、java、运维、测试、数据库笔试题合集.docx

    4. **内存查找**:一旦树节点被读入内存,后续的查找操作只需在内存中进行,而内存的速度远快于磁盘。 相比于普通的二叉搜索树,B+树能够显著减少磁盘I/O操作的次数,进而提高查询速度。 --- #### 三、选择题解析...

    数据结构(C语言版)(第二版)PPT

    二叉搜索树、平衡树(如AVL树和红黑树)等都是重要的树结构,它们在搜索和排序中有重要作用。 6. **图**:图由节点和边组成,表示对象之间的关系。图可以用来解决复杂的问题,如网络路由、最短路径算法(Dijkstra...

    chapter_3_算法分析.zip

    《Python数据结构第三章:算法分析》 在Python编程中,数据结构与算法的理解和运用是至关重要的。本章节着重探讨了如何分析和利用各种数据结构实现高效的算法,旨在帮助初学者更好地掌握Python中的核心概念。以下是...

    2021-2022计算机二级等级考试试题及答案No.14321.docx

    ### 9. 数据结构中的非线性结构 在给定选项中,**二叉链表**属于非线性结构。非线性结构是指数据元素之间的关系不是简单的线性序列,而是具有分支或多对多的关系。常见的非线性结构还包括树形结构和图形结构等。 ##...

    ACM模版代码(已验证)

    - **描述**:利用二叉查找树的数据结构来查找元素。 - **应用**:在动态数据集合中进行高效查找。 #### 三、排序 **1. 选择排序** - **描述**:每次从未排序部分找到最小(或最大)的元素,放到已排序序列的...

Global site tag (gtag.js) - Google Analytics