对于二叉树，在之前笔者写过两篇文章了！那么，这篇主要是：递归与非递归实现二叉树的前中后序遍历！！
二叉树相关的列题讲解：https://blog.csdn.net/weixin_64308540/article/details/129071653?spm=1001.2014.3001.5501
对于二叉树，是真正的很难！很难，不是一般的难度！！
笔者学习完二叉树，笔记记录了得有三十多页，但是，还是很不理解（做题不怎么会）
下面进入二叉树的基础部分：
二叉树概念！！
一颗二叉树是节点的一个有限集合：该集合
或者为空
或者是由一个根节点加上两颗别称为左子树和右子树的二叉树组成
经过上述，我们可以得出：
二叉树不存在度大于2的节点（对于度是什么，不理解的读者，可以参考笔者的之前的文章：https://blog.csdn.net/weixin_64308540/article/details/129045341
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树（左右顺序）
经过二叉树的上述内容的讲解，我们可以得出：对于任意类型的二叉树，都是由一下的几种情况复合而成的！
经过上述的内容，我们便可以根据自己的想法，设计任意类型的二叉树了！！
下面我们来进行讲解一下两种特殊的二叉树：
满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
对于这个满二叉树，我们可以根据层数，每层的个数，最后得出节点的个数（考试可能会考）
完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
在这里，我们需要注意的是：满二叉树是一种特殊的完全二叉树
二叉树的性质！！
- 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点
- 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)
- 具有n个结点的完全二叉树的深度k为 上取整
- 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有： 1.若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点 2.若2i+1<n，左孩子序号：2i+1，否则无左孩子 3.若2i+2<n，右孩子序号：2i+2，否则无右孩子
- 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
对于第5点，笔者在后续的代码/选择题/解答题当中，经常使用！所以，我们需要知道它的推理由来！！（笔者由一颗完全二叉树为列，来进行讲解）
根据上述的二叉树的性质，来做几个简单的练习题吧！！
1. . 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ 200） 提示：叶子节点为：度为0的节点（不知道度是什么的，可以参考：https://blog.csdn.net/weixin_64308540/article/details/129045341）
在具有 2n 个结点的完全二叉树中，叶子结点个数为（ n）
提示：2n是个偶数！！
思考一下：当奇数节点的时候，又会是怎么个结果？？思路跟刚才的一样！感兴趣的可以自己思考一下！
2. 一个具有767个节点的完全二叉树，其叶子节点个数为（384） 首先我们需要根据767（奇数），完全二叉树来进行思考！
3. 一棵完全二叉树的节点数为531个，那么这棵树的高度为（ 10）
这个便不再解析了，大家自行解决！答案已经给出
上述文章的引用链接为：原文链接： https://blog.csdn.net/weixin_64308540/article/details/129046267
递归法：
- 前序遍历递归法：
//二叉树的前序遍历（递归） public void preOrder(TreeNode root){ if (root==null){ return; } System.out.print(root.val+" ");//根 preOrder(root.left);//左 preOrder(root.right);//右 }
2.中序遍历递归法：
//二叉树的中序遍历（递归） public void inOrder(TreeNode root){ if (root==null){ return; } preOrder(root.left);//左 System.out.print(root.val+" ");//根 preOrder(root.right);//右 }
3.后序遍历递归法：
//二叉树的后序遍历（递归） public void postOrder(TreeNode root){ if (root==null){ return; } preOrder(root.left);//左 preOrder(root.right);//右 System.out.print(root.val+" ");//根 }
非递归法：
1.前序遍历
//非递归，前序遍历(用栈来做） public void prevOrderNor(TreeNode root){ if (root==null){ return; } TreeNode cur=root; //栈 Deque<TreeNode> stack=new ArrayDeque<>(); while (cur!=null || !stack.isEmpty()){ while (cur!=null){ stack.push(cur);//把cur放到栈中 System.out.print(cur.val+" ");//打印 cur=cur.left;//左树 } TreeNode top=stack.pop();//弹出栈顶的一个元素 cur=top.right;//右树 } System.out.println(); }
2.中序遍历
// 非递归，中序遍历 public void inOrderNor(TreeNode root){ if (root==null){ return; } TreeNode cur=root; Deque<TreeNode> stack =new ArrayDeque<>(); while (cur!=null || !stack.isEmpty()){ while (cur!=null){ stack.push(cur); cur=cur.left; } TreeNode top=stack.pop(); System.out.print(top.val+" "); cur=top.right; } System.out.println(); }
3.后序遍历
//非递归，后序遍历 public void postOrderNor(TreeNode root){ if (root==null){ return; } TreeNode cur=root; TreeNode prev=root; Deque<TreeNode> stack=new ArrayDeque<>(); while (cur!=null || !stack.isEmpty()){ while (cur!=null){ stack.push(cur); cur=cur.left } TreeNode top=stack.peek(); if (top.right==null || top.right==prev){ System.out.print(top.val+" "); stack.pop(); prev=top; }else { cur=top.right; } } System.out.println(); }
对于为什么这样写代码，你可以理解为：所谓的非递归实现，只不过是模拟实现了递归！！
对于这么写的思路，那么，建议你可以参考一下：https://blog.csdn.net/weixin_64308540/article/details/129046267?spm=1001.2014.3001.5501这里面有着详细的解析！
