版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43126117/article/details/98937218
前中后序遍历在平时用的不多,实际上用到更多是深度优先和广度优先算法,那为什么要遍历二叉树呢!好像也就仅仅输出数据而已,但是对于二叉搜索树,中序遍历,就可以输出一个有序的结果了。
注意根节点的位置,根节点在前那就是前序遍历,根节点在后,那就是后序遍历!
下面给出遍历的代码,需要注意的是,树的结构代码(不含父节点引用)
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x;}
}
public void preorder(TreeNode node) {
System.out.print(node.val);
if (node.left != null) preorder(node.left);
if (node.right !=null) preorder(node.right);
}
思路:因为当前节点并未保存父亲节点的引用,迭代的时候,只能改变一个只进行迭代,那么另外一个(左右)节点就丢失了,那么我们需要借助另外的数据结构存储一下。
public void preorder2(TreeNode node) {
Stack<TreeNode> stack = new Stack<>();
if (node != null) {
stack.push(node);
}
while (!stack.isEmpty()) { //先出左节点,再出相邻右节点
TreeNode pop = stack.pop();
System.out.print(pop.val);
if (pop.right != null) stack.push(pop.right); //每次都把左右节点存进去
if (pop.left != null) stack.push(pop.left);
}
}
public void inorder(TreeNode node) {
if (node.left != null) inorder(node.left);
System.out.print(node.val);
if (node.right !=null) inorder(node.right);
}
public void inorder2(TreeNode node) {
Stack<TreeNode> stack = new Stack<>();
while (node != null||!stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left; //先把左边全部存入
}
node = stack.pop(); //取得最左边
System.out.print(node.val);
node = node.right; //检查最左边的右节点
}
}
public void postorder(TreeNode node) {
if (node.left != null) postorder(node.left);
if (node.right !=null) postorder(node.right);
System.out.print(node.val);
}
思路:这个比较有技巧,前序遍历是 “根》左》右” ,把前序遍历的左右调换 “根》 右 》左” ,再把这个结果反转“左》右》根”
public void postorder3(TreeNode node) {
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> reverse = new Stack<>(); ////建立多个栈,作为反转,先入后出
if (node != null) {
stack.push(node);
}
while (!stack.isEmpty()) {
TreeNode pop = stack.pop();
reverse.add(pop.val); //建立多个栈,作为反转
if (pop.left != null) stack.push(pop.left); //先存入左边, 那么就先出右边 根》 右 》左
if (pop.right != null) stack.push(pop.right);
}
while (!reverse.isEmpty()) { //直接输出就可以了
System.out.print(reverse.pop());
}
}
思路:这个借鉴了中序遍历“左根右”,先获取所有左节点, 再次证明当前节点是左节点就行。
即:当前节点存在右节点,则证明是根节点。
假如是根节点,则把根节点的右节点再次重复(先获取所有左节点,再次证明当前节点是左节点)
这里需要保存上一个节点,防止一直重复右节点。(例如:获取栈->存在右节点->右节点重复->再获取栈->存在右节点,其实就是一直未出栈,导致重复了。获取栈->上一节点->存在右节点)
public void postorder2(TreeNode node) {
Stack<TreeNode> stack = new Stack<>();
TreeNode last = null;
while (node != null || !stack.isEmpty()) {
while (node != null) { //获取全部左节点
stack.push(node);
node = node.left;
}
node = stack.peek(); //没有出栈,只是赋值, 这个节点可能根节点 或者左节点
if (node.right == null || node.right == last) { //证明是左节点,last的作用 防止多次重复。
System.out.print(node.val);
stack.pop(); //出栈
last = node;
node = null;
} else { //否则就是根节点,再次重复上面过程。
node = node.right;
}
}
}