首先約定：先序：根，左，右 中序：左，根，右 后序：左，右，根
遞回實作
遞回實作中，總是會經過一個節點三次，所以先序中序和后序的唯一區別就是列印的時機不同
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://www.uj5u.com/houduan/234876.html
標籤：java
上一篇：原型模式