菜鸟笔记这三也是经典的二叉树的三种方法
二叉树的前序遍历
递归实现
public class Main4 {
static ArrayList<TreeNode> list = new ArrayList<TreeNode>();
int QianXu(TreeNode t) {
//根，判定第一个节点(根)是否存在
if(t==null) {
return 0;
}
list.add(t);
//左
if(t.left!=null) {
HouXu(t.left);
}
//右
if(t.right!=null) {
HouXu(t.right);
}
return 0;
}
public static void main(String[] args) {
TreeNode tn1= new TreeNode(1);
TreeNode tn2= new TreeNode(2);
TreeNode tn3= new TreeNode(3);
TreeNode tn4= new TreeNode(4);
TreeNode tn5= new TreeNode(5);
TreeNode tn6= new TreeNode(6);
TreeNode tn7= new TreeNode(7);
tn1.left=tn2;
tn1.right=tn3;
tn2.left=tn4;
tn2.right=tn5;
tn3.left=tn6;
tn3.right=tn7;
new Main4().QianXu(tn1);
for(int i =0;i<list.size();i++) {
System.out.print(list.get(i).val);
}
}
}
这个没什么难理解的，顺序就是根，左，右节点，如果有左右节点就遍历，没有就不往左节点或右节点遍历了
非递归实现
前序遍历的非递归实现就不写了，很简单，和深度优先一样，我不知道别人有用什么奇怪方法的，但是我用栈来实现深度优先，可以参考二叉树广度优先搜索和深度优先搜索
二叉树的中序遍历
1、使用递归的方式实现
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Main3 {
static ArrayList<TreeNode> list = new ArrayList<TreeNode>();
int ZhongXuBianLi(TreeNode tn) {
if(t==null) { //判定第一个节点(根)是否存在
return 0;
}
//左
if(tn.left!=null) {
ZhongXuBianLi(tn.left);
}
//根
list.add(tn);
//右
if(tn.right!=null) {
ZhongXuBianLi(tn.right);
}
return 0;
}
public static void main(String[] args) {
TreeNode tn1= new TreeNode(1);
TreeNode tn2= new TreeNode(2);
TreeNode tn3= new TreeNode(3);
TreeNode tn4= new TreeNode(4);
TreeNode tn5= new TreeNode(5);
TreeNode tn6= new TreeNode(6);
TreeNode tn7= new TreeNode(7);
tn1.left=tn2;
tn1.right=tn3;
tn2.left=tn4;
tn2.right=tn5;
tn3.left=tn6;
tn3.right=tn7;
new Main3().ZhongXuBianLi(tn1);
for(int i =0;i<list.size();i++) {
System.out.print(list.get(i).val);
}
}
}
结果：
使用的例子示例图
分析这个可能有点眼花缭乱，那就先看小的部分
这个怎么能成中序遍历呢？
肯定是213吧，那是不是先把2节点放进去，再把1节点放进去，再把三节点放进去呢！肯定的
那给的节点肯定是1节点了，那访问的顺序肯定就是先从1到2，再经过1到3。
而这个顺序正好有一个中序遍历的顺序，那就是213，所以就从2节点开始放，那怎么知道到2了呢？
那就找左子树是null的节点就行，添加完2肯定就是返回，返回到根节点添加1，再通过右子树为null找到3，添加进去，就完成了。
再经过递归就可以成大的了、
2、使用非递归的方式实现(使用栈)
TreeNode是二叉树的节点，上个程序有，这就不添加上了
//非递归
int ZhongXuBianLi1(TreeNode tn) {
//根不存在
if(tn==null) {
return 0;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.add(tn);
//isEmpty只有当size==0时才返回true
while(stack.isEmpty()==false) { //第一步
if(tn!=null) { //第二步
stack.add(tn);
tn = tn.left;
}else { //第三步
tn = stack.pop();
list.add(tn);
if(stack.isEmpty()==false) { //第四步
tn = stack.pop();
list.add(tn);
}
tn = tn.right;
}
}
return 0;
}
public static void main(String[] args) {
TreeNode tn1= new TreeNode(1);
TreeNode tn2= new TreeNode(2);
TreeNode tn3= new TreeNode(3);
TreeNode tn4= new TreeNode(4);
TreeNode tn5= new TreeNode(5);
TreeNode tn6= new TreeNode(6);
TreeNode tn7= new TreeNode(7);
tn1.left=tn2;
tn1.right=tn3;
tn2.left=tn4;
tn2.right=tn5;
tn3.left=tn6;
tn3.right=tn7;
new Main3().ZhongXuBianLi1(tn1);
for(int i =0;i<list.size();i++) {
System.out.print(list.get(i).val);
}
}
这个的例子也是用的
因为不是用递归实现，所以就需要用while或者for来代替递归了，说实话递归的确好理解
一步一步的来分析分析怎么用栈来解决的，用栈怎么实现的。
首先看一张图
不知道你能不能看懂，一开始我也看不懂，经过自己写这个过程就会了，
这些不同颜色的实线箭头 就是进栈的顺序(这些箭头是不可以打断的，比如1，2，4必须进栈是1、2、4，不能在4之前插入一个)
当然出栈的没写，根据入栈的顺序，和中序遍历的顺序结合，其实就能写出 出栈的顺序。
按这个思路，首先你需要while循环一下把1、2、4都添加进去吧，之后出4，2，再把5进栈
之后5，1出栈，3、6进栈，再3、6出栈，7入栈，再7出栈，就构成了中序遍历
上面的思路好理解，但是实现有点困难，看程序，
1、首先解决的是while的判定条件，因为这个过程中栈空代表着么有没有节点了，所以结束了，
2、之后是怎么一口气把像1、2、4这样的节点入栈
3、什么情况下开始出栈，出栈几个(要考虑到有可能连着的父节点，祖父节点等没有右节点)，
4、考虑到出栈到根节点的情况
上面的4个正好对应程序中关键的四步
二叉树的后序遍历
递归实现
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Main4 {
static ArrayList<TreeNode> list = new ArrayList<TreeNode>();
int HouXu(TreeNode t) {
if(t==null) { //判定第一个节点(根)是否存在
return 0;
}
//左
if(t.left!=null) {
HouXu(t.left);
}
//右
if(t.right!=null) {
HouXu(t.right);
}
list.add(t);
return 0;
}
public static void main(String[] args) {
TreeNode tn1= new TreeNode(1);
TreeNode tn2= new TreeNode(2);
TreeNode tn3= new TreeNode(3);
TreeNode tn4= new TreeNode(4);
TreeNode tn5= new TreeNode(5);
TreeNode tn6= new TreeNode(6);
TreeNode tn7= new TreeNode(7);
tn1.left=tn2;
tn1.right=tn3;
tn2.left=tn4;
tn2.right=tn5;
tn3.left=tn6;
tn3.right=tn7;
new Main4().HouXu(tn1);
for(int i =0;i<list.size();i++) {
System.out.print(list.get(i).val);
}
}
}
非递归实现
用两个栈来实现，当压入第一个栈是1，取出来把它左右都压进栈，再把1压入另一个栈，这样循环下去，第二个栈的出栈顺序就是后续遍历
int HouXu1(TreeNode t) {
if(t==null) {
return 0;
}
Stack<TreeNode> stack1=new Stack<TreeNode>();
Stack<TreeNode> stack2=new Stack<TreeNode>();
stack1.add(t);
while(!stack1.isEmpty()) {
t =stack1.pop();
if(t.left!=null) {
stack1.add(t.left);
}
if(t.right!=null) {
stack1.add(t.right);
}
stack2.add(t);
}
while(!stack2.isEmpty()) {
list.add(stack2.pop());
}
return 0;
}
public static void main(String[] args) {
TreeNode tn1= new TreeNode(1);
TreeNode tn2= new TreeNode(2);
TreeNode tn3= new TreeNode(3);
TreeNode tn4= new TreeNode(4);
TreeNode tn5= new TreeNode(5);
TreeNode tn6= new TreeNode(6);
TreeNode tn7= new TreeNode(7);
tn1.left=tn2;
tn1.right=tn3;
tn2.left=tn4;
tn2.right=tn5;
tn3.left=tn6;
tn3.right=tn7;
new Main4().HouXu1(tn1);
for(int i =0;i<list.size();i++) {
System.out.print(list.get(i).val);
}
}
分析分析这三种遍历中递归的区别(非递归联系不是很大)
自己整理完这三种遍历的算法，感觉也就那样，尤其是递归的，更没什么
if(t==null) { //这个必须排第一个
return 0;
}
list.add(t); //第一部分
//左
if(t.left!=null) { //第二部分
HouXu(t.left);
}
//右
if(t.right!=null) { //第三部分
HouXu(t.right);
}
return 0;
前序遍历、中序遍历、后序遍历也就是上面三部分根据前面序列的规则排序而已。
举个例子：
前序要求根节点，左节点，右节点。那上面排序的规则就是第一部分(根)、第二部分(左)、第三部分(右)
很简单。看别人千万遍不如自己写一遍，总结一遍啊。