求证：具有 n 个结点的完全二叉树的深度为⌈log₂(n+1)⌉或⌊log₂n⌋+1
证明：设完全二叉树的深度为h，则依据“深度为h的二叉树至多有2^h-1个结点（h≥1）”的性质，
可得：2^h-1-1＜n ≤ 2^h-1
其等价于 2^h-1＜n+1 ≤ 2^h，也即 2^h-1≤ n＜2^h

● 对式子 2^h-1＜n+1 ≤ 2^h 求对数，可得 h-1＜log₂(n+1) ≤ h

显然，此时完全二叉树的深度h=⌈log₂(n+1)⌉

● 对式子 2^h-1≤ n＜2^h 求对数，可得 h-1 ≤log₂n＜h

显然，此时完全二叉树的深度h=⌊log₂n⌋+1

​

        我们知道具有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，输出结果为所有组成的二叉树的前序增强序列('#'号标识空)。

记n个节点的二叉树形态个数为A[n]

1）0个节点的二叉树只有1种形态，A[0]=0；1个节点的二叉树只有1种形态，A[1]=1

2）n个节点（n>=2）的二叉树有，求和的每一项，分别表示根的左子树为m个节点、右子树为 n-1-m个节点的情况。（总共n个节点，左子树m个节点，根节点有1个，那么右子树的节点数为n-1-m个）

刚好就是catalan数，直接用catalan数的公式：h(n)==