共计 1951 个字符,预计需要花费 5 分钟才能阅读完成。
首先约定:先序:根,左,右 中序:左,根,右 后序:左,右,根
递归实现
递归实现中,总是会通过一个节点三次,所以先序中序和后序的惟一区别就是打印的机会不同
public class Node {// 这是 Node 的构造
public int value;
public Node left;
public Node right;
public Node(int data) {this.value = data;}
}
public void preOdferRecur(Node head) {if (head == null) {return;}
System.out.print(head.value + " ");// 先序遍历,打印放在第一行
preOdferRecur(head.left);
preOdferRecur(head.right);
}
public void inOdferRecur(Node head) {if (head == null) {return;}
inOdferRecur(head.left);
System.out.print(head.value + " ");// 中序遍历,打印放在第二行
inOdferRecur(head.right);
}
public void posOdferRecur(Node head) {if (head == null) {return;}
posOdferRecur(head.left);
posOdferRecur(head.right);
System.out.print(head.value + " ");// 后序遍历,打印放在第三行
}
非递归实现
非递归先序遍历
思路:申请一个栈,压入头结点,而后弹出栈节点,打印进去,再将弹出节点的右孩子压入,左孩子压入,一直反复这个过程,直到栈为空
public void preOrderUnRecur(Node head){if (head!=null){Stack<Node> stack=new Stack<Node>();
stack.add(head);
while(!stack.isEmpty()){head=stack.pop();
System.out.printf(head.value+" ");
if (head.right!=null){stack.push(head.right);
}
if (head.left!=null){stack.push(head.left);
}
}
}
}
非递归中序遍历
思路:中序是左,根,右,因而思考将左边界都压入栈,直到节点为空,则从栈中拿出一个打印,以后节点右移,若以后节点不为空,则压入栈,以后节点为左
- 申请一个栈,记为 stack。初始时,令变量 cur=head。
- 先把 cur 节点压入栈,对以 cur 节点为头结点的子树来说,顺次把左边界压入栈中,即不停地令 cur=cur.left,而后反复步骤 2
- 直到 cur 为空,此时从 stack 中弹出一个节点,记为 node。打印 node,并让 cur=node.right,而后继续反复步骤 2
- 当 stack 为空且 cur 为空,这个过程进行
`public void inOrderUnRecur(Node head){if(head!=null){Stack<Node> stack=new Stack<Node>();
while (!stack.isEmpty()||head!=null){if (head!=null){stack.push(head);
head=head.left;
}
else {head=stack.pop();
System.out.println(head.value+" ");
head =head.right;
}
}
}
}
非递归后序遍历
思路:后序遍历是左,右,中,先序是中,左,右,将中左右变成中右左,在建设个栈将中右左压入,弹出即是后序遍历的秩序
public void posOrderUnRecur(Node head){if (head!=null){Stack<Node> stack1=new Stack<Node>();
Stack<Node> stack2=new Stack<Node>();
stack1.add(head);
while(!stack1.isEmpty()){head=stack1.pop();
stack2.push(head);
if (head.left!=null){stack1.push(head.left);
}
if (head.right!=null){stack1.push(head.right);
}
}
while(!stack2.isEmpty()){System.out.printf(stack2.pop().value+" ");
}
}
}
连贯地址:https://blog.csdn.net/weixin_…
正文完