二叉树的实现与QJ题总结

首先对递归的本质进行一些理解.

递归在逻辑上就是创建很多个一样的子函数，每个函数在遇到返回值或代码走完时结束直到主函数结束，在物理上就是不断的压栈和消栈.

同时我们要知道一个main函数中的代码需会生成一个它自己的代码空间，例如main中的一个函数，它内部的代码会有一份空间，编译器通过这份空间中的代码开栈.如果该函数为递归函数，那么就会通过这份空间的代码不断地开栈而非每遇到一个该函数就给它内部的代码再开一份空间.

总结而言就是编译器在运行过程中遇到一个新函数时，会为它内部的代码创建一份空间，以后在遇到这个函数时就会在调用对应空间的代码而非再创建一份.

下面是二叉树的实现

声明

实现

层序遍历使用了queue,下面的完全二叉树的识别也是.

对于能通过第一个NULL来识别的解释:

只要遇到NULL时，后面一排有非空，就一定能遍历到.
原因：遇到NULL的同排有非空一定能遍历到,此是都不用到下一排了.
故下一排的结点只可能是第一个NULL之前产生的.
总之在遇到第一个NULL之前，下一排的结点一定都出现了.

下面是一些QJ题

1.前序遍历

2.相同的树

3.对称二叉树

4.另一棵树的子树

5.二叉树遍历