前序遍历
1) 首先将根节点放到栈中
2) 遍历栈,如果不为空, 弹出栈顶元素, 定义为变量cur
3) 如果cur的右节点不为空, 则入栈
4) 如果cur的左节点不为空,则入栈
5) 重复2~4的步骤, 直到栈为空退出
后序遍历
如果把上面[前序遍历]的步骤3和4顺序调换一下, 输出的节点顺序应该是“根-右-左”, 如果把“根-右-左”整个逆序, 则输出结果未“左-右-根”, 即为[后续遍历]
1) 首先将根节点放到栈stack1中
2) 遍历栈,如果stack1不为空, 弹出栈顶元素, 定义为变量cur, 同时把cur放到另外一个栈stack2中存储
3) 如果cur的左节点不为空, 放到stack1中
4) 如果cur的右节点不为空,放到stack1中
5) 重复2~4的步骤, 直到stack1为空退出
6) 遍历stack2
中序遍历
1) 依次把左边界所有节点压栈
2)遍历栈,如果栈不为空, 则弹出栈顶元素cur
3) 如果cur的右节点不为空,则重复1~2的步骤
层序遍历
1) 首先把根节点放入队列
2) 遍历队列,取出头节点, 定义为遍历cur
3) 如果cur的左节点不为空, 放入队列
4) 如果cur的右节点不为空, 放入队列 //每一层遍历完之后, 队列中都放入了下一层的所有元素,因此可以算出最大宽度
5) 重复2~4的步骤
相关代码如下
import java.util.Stack;
public class Test0311 {
static class Node{
int val;
Node left;
Node right;
public Node(int val){
this.val=val;
}
/**
* 二叉树-前序遍历:根左右
* 非递归方式
* 1) 将根节点放到栈中
* 2) 遍历栈,如果非空,弹出栈,定义为变量cur
* 3) 如果cur的右节点不为空,入栈
* 4) 如果cur的左节点不为空,入栈
* 5) 重复2~4的步骤,直到栈为空退出
* @param root
*/
public void preOrder(Node root){
if(root==null){
return;
}
Stack<Node> stack = new Stack();
stack.push(root);
while(!stack.isEmpty()){
Node cur = stack.pop();
System.out.print(cur.val+" ");
if(cur.right!=null){
stack.push(cur.right);
}
if(cur.left!=null){
stack.push(cur.left);
}
}
System.out.println();
}
/**
* 后序遍历:左右根
* 非递归方式遍历
* 1) 将根节点放到stack1
* 2) 遍历stack1, 如果不为空,则弹出栈顶元素, 定义为变量cur, 同时存到stack2
* 3) 如果cur的左节点不为空, 入栈stack1
* 4) 如果cur的右节点不为空, 入栈stack1
* 5) 重复2~4步骤,直到stack1为空退出
* 6) 遍历stack2
* @param root
*/
public void postOrder(Node root){
if(root==null){
return;
}
Stack<Node> stack1 = new Stack();
Stack<Node> stack2 = new Stack();
stack1.push(root);
while(!stack1.isEmpty()){
Node cur = stack1.pop();
stack2.push(cur);
if(cur.left!=null){
stack1.push(cur.left);
}
if(cur.right!=null){
stack1.push(cur.right);
}
}
while(!stack2.isEmpty()){
Node cur = stack2.pop();
System.out.print(cur.val+" ");
}
System.out.println();
}
/**
* 中序遍历: 左根右
* 非递归方式遍历
* 1) 依次把所有的左边界节点压栈(包扩根)
* 2) 遍历栈,如果不为空,弹出栈顶元素,定义为变量cur
* 3) 如果cur的右节点不为空,重复步骤2
*/
public void midOrder(Node root){
//1) 左边界压栈
Node temp = root;
Stack<Node>stack = new Stack();
while(temp!=null){
stack.push(temp);
temp = temp.left;
}
//2) 遍历栈
while(!stack.isEmpty()){
Node cur = stack.pop();
System.out.print(cur.val+" ");
//3) 重复1操作
if(cur.right!=null){
temp = cur.right;
while(temp!=null){
stack.push(temp);
temp = temp.left;
}
}
}
System.out.println();
}
/**代码合并优化如下 */
/**
* 中序遍历: 左根右
* 非递归方式
* 1) 依次把左边界节点放入栈中,直到为空
* 2) 遍历栈,弹出栈顶元素,定义为cur
* 3) 如果cur的右节点不为空,则重复1~2
* @param root
*/
public void midOrder2(Node root){
Node cur = root;
Stack<Node> stack = new Stack();
while(cur!=null || !stack.empty()){
if(cur!=null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
System.out.print(cur.val+" ");
cur = cur.right;
}
}
System.out.println();
}
/**
* 层序遍历
* 1) 首先把根节点放到队列
* 2) 遍历队列,取出头节点,定义为变量cur
* 3) 如果cur的左节点不为空,放到队列
* 4) 如果cur的右节点不为空,放到队列
* 5) 重复2~4的步骤,直到队列空
* @param root
* @return 最大宽度
*/
public int levelOrder(Node root){
if(root==null){
return 0;
}
int wide =1 ;
Queue<Node> queue = new LinkedList();
queue.add(root);
while(!queue.isEmpty()){
Node cur = queue.poll();
System.out.print(cur.val+" ");
if(cur.left!=null){
queue.add(cur.left);
}
if(cur.right!=null){
queue.add(cur.right);
}
wide = Math.max(wide, queue.size());
}
System.out.println();
return wide;
}
/**
* 最大深度
* @param root
* @return
*/
public int maxHeight(Node root){
if(root==null){
return 0;
}
int leftHeight = maxHeight(root.left);
int rightHeight = maxHeight(root.right);
return Math.max(leftHeight,rightHeight)+1;
}
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
node1.left = node2;node2.left=node4;node2.right=node5;
node1.right= node3;node3.left=node6;node3.right=node7;
node1.preOrder(node1);
node1.postOrder(node1);
node1.midOrder(node1);
node1.midOrder2(node1);
node1.levelOrder(node1);
System.out.println("maxWide="+maxWide);
System.out.println("maxHeight="+node1.maxHeight(node1));
}
}
}
