我们知道具有n个结点的不同的二叉树的数量是个(这是一个卡塔兰数),那么如何确定这些二叉树是什么样子的呢?下面是博主的思路:
我们还知道一个入栈序列的不同出栈序列的数量也是个,于是博主就想:这不是巧了么,既然他们的数量是一样的,而且均不相同,那么是不是可以构建一个映射,使得不同的出栈序列和不同的二叉树进行一一对应呢。
于是,在博主的做了深入的观察和思考后,发现对于其中一个出栈序列,其实和某个二叉树的中序遍历结果是相对应的,而经过进一步探索,发现入栈序列是所有二叉树的前序遍历结果。
众所周知,一个二叉树的前序和中序遍历结果是可以唯一确定一棵二叉树的。
然而在写代码的过程中博主又遇到了一个难题:就是如何输出一个入栈序列的全部出栈序列呢?为了解决这个问题,博主上某搜索网站参考了各位大神的代码,发现他们基本都是用回溯法解决的。于是在一番研究之下。我成功地写出了输出一个入栈序列的全部出栈序列的函数。
这样一来,所有问题都解决了。然后经过了20分钟的编码。博主成功地写出了求解具有n个结点的不同的二叉树的所有前序增强序列的C++代码:
另外如果大家有什么疑问或者见解可以在评论下方讨论,如果发现确实有什么错误的话,还请指正。
如下所示:
#include <iostream>
using namespace std;
static const int M = 100;
//依次代表的意思是结点数、栈、出栈序列、栈指针、出栈序列大小、输入顺序、二叉树中序序列,二叉树中序序列索引
static int n,stk[M],seq[M],stk_top=-1,seq_size=0,input[M],in[M],idx;
//根据二叉树的前序和中序遍历获取增强前序序列
static void getEnhencedPreorder(int root, int begin, int end) {
if (begin > end) {
cout << "#" << " ";
return;
}
int i = begin;
while (input[root] != in[i]) {
i++;
}
cout << input[root] << " ";
getEnhencedPreorder(root + 1, begin, i - 1);
getEnhencedPreorder(root + (i - begin) + 1, i + 1, end);
}
//获取所有出栈序列
static void getSequence(int i) {
if (i == n) {
//收集结果
idx = 0;
for (int i = 0; i < seq_size; i++) {
in[idx++]=seq[i];
}
for (int i = stk_top; i >= 0; i--) {
in[idx++] = stk[i];
}
//根据前序和中序遍历获取其增强前序遍历序列
getEnhencedPreorder(0,0,n-1);
cout << endl;
} else {
//对于一个入栈的元素,可以入栈,也可以不入栈
//但是每种情况都要检验
//一、首先是元素入栈了
stk[++stk_top]= input[i];
getSequence(i + 1);
stk_top--;
//二、然后元素没有入栈,并且栈顶元素出栈了
if (stk_top!=-1) {
int top= stk[stk_top--];
seq[seq_size++]=top;
getSequence(i);
seq_size--;
stk[++stk_top] = top;
}
}
}
//相当于main函数
void stack_pop_sequence_re2_main() {
cin >> n;
for (int i = 0; i < n;i++) {
input[i] = i + 1;
}
getSequence(0);
}
下面是一个示例(当n取3时):
其入栈序列为1 2 3,输出结果为所有组成的二叉树的前序增强序列('#'号标识空)。