本帖最后由 大灰狼 于 2014-8-1 09:01 编辑
题目
解决代码及点评
- [size=+0]<pre code_snippet_id="110188" snippet_file_name="blog_20131213_1_7234345" class="cpp" name="code"><pre code_snippet_id="110188" snippet_file_name="blog_20131213_1_7234345" class="cpp" name="code"><pre code_snippet_id="110188" snippet_file_name="blog_20131213_1_7234345" class="cpp" name="code"><pre code_snippet_id="110188" snippet_file_name="blog_20131213_1_7234345" name="code" class="cpp"><pre code_snippet_id="110188" snippet_file_name="blog_20131213_1_7234345" name="code" class="cpp">/*
[size=+0] 给出一个数组,判断该数组是否为二叉搜索树的后序遍历 [size=+0] 后序遍历是先遍历左子树,再遍历右子树,最后访问根节点 [size=+0][size=+0] 所以,后序遍历的特点是,最后一个元素是根节点 [size=+0] 在数组剩下的部分里,某连续的部分P1小于根节点,而某连续的部分P2全部大于根节点 [size=+0][size=+0] 对P1和P2来说,分别是两个子树的后序遍历,因此使用递归即可 [size=+0]*/ [size=+0]#include <iostream> [size=+0]using namespace std; [size=+0] [size=+0]/* 判断是否后序遍历序列 */ [size=+0]static bool VerifyArrayOfBST(int* a, int len) [size=+0]{ [size=+0] int root = a[len - 1]; // 最后一个节点是根节点 [size=+0] int i, j; [size=+0] bool result; [size=+0] [size=+0] // 对于只有小于两个节点的树来说,我们认为其是后序遍历序列 [size=+0] if (len <= 2) return true; [size=+0] [size=+0] // 循环找到第一个大于根节点的下标 [size=+0] for (i = 0; i < len-1; ++i) [size=+0] { [size=+0] if (a > root) [size=+0] break; [size=+0] } [size=+0] [size=+0] // 在这个大于根节点的下标后面的所有数据,应该都大于root [size=+0] // 否则它不是后序遍历序列 [size=+0] for (j = i; j < len - 1; ++j) [size=+0] { [size=+0] if (a[j] < root) [size=+0] return false; [size=+0] } [size=+0] [size=+0] // 递归的检测左子树 [size=+0] result = VerifyArrayOfBST(a, i); [size=+0] [size=+0] // 如果左子树成功,则检测右子树,并返回 [size=+0] if (result) [size=+0] return VerifyArrayOfBST(a + i, len - i - 1); [size=+0] [size=+0] // 左子树都不成功,则返回false [size=+0] return false; [size=+0] [size=+0]} [size=+0] [size=+0]// 测试的main函数 [size=+0]int main() [size=+0]{ [size=+0] int a[]={1,6,4,3,5}; [size=+0] int a1[]={7,6,4,3,5}; [size=+0] [size=+0] if (VerifyArrayOfBST(a,5)==true) [size=+0] { [size=+0] cout<<"a是搜索树"<<endl; [size=+0] } [size=+0] else{ [size=+0] cout<<"a不是搜索树"<<endl; [size=+0] } [size=+0] if (VerifyArrayOfBST(a1,5)==true) [size=+0] { [size=+0] cout<<"a1是搜索树"<<endl; [size=+0] } [size=+0] else{ [size=+0] cout<<"a1不是搜索树"<<endl; [size=+0] } [size=+0] system("pause"); [size=+0] return 0; [size=+0]} [size=+0] [size=+0]</pre><br></pre><br></pre></pre></pre>
代码下载及其运行 代码下载地址:http://download.csdn.net/detail/yincheng01/6704519
解压密码:c.itcast.cn
下载代码并解压后,用VC2013打开interview.sln,并设置对应的启动项目后,点击运行即可,具体步骤如下: 1)设置启动项目:右键点击解决方案,在弹出菜单中选择“设置启动项目”
2)在下拉框中选择相应项目,项目名和博客编号一致
3)点击“本地Windows调试器”运行
程序运行结果
|