循環(huán)遍歷(只有層次遍歷用到了隊，其他都是棧)
- 前序遍歷
1.使用一個棧來存儲元素枉氮，剛開始的時候將棧頂元素壓入棧
2.當棧不為空的時候做如下操作：彈出棧頂元素并遍歷志衍，依次將出棧結點的右孩子和左孩子入棧
//非遞歸前序遍歷二叉樹
public static void printTree1(Node root){
SequenceStack<Node> stack=new SequenceStack<Node>();
List<Node> list=new ArrayList<Node>();
//首先先把根節(jié)點壓棧
stack.push(root);
//當棧不為空的時候循環(huán)遍歷
while(!stack.isEmpty()){
//彈出棧頂元素
Node node=stack.pop();
//遍歷棧頂元素
list.add(node);
//如果棧頂元素的右孩子不為空暖庄，則進棧
if(node.right!=null){
stack.push(node.right);
}
//如果棧頂元素的左孩子不為空，則進棧
if(node.left!=null){
stack.push(node.left);
}
}
System.out.println(list);
}
- 中序遍歷
1.剛開始先把根節(jié)點壓入棧楼肪，往后每次判斷節(jié)點不為空則入棧
2.彈出棧頂元素并遍歷培廓，判斷棧頂元素是否存在右孩子結點，根據(jù)結果進行相應的操作~
有：繼續(xù)將右孩子結點壓棧
無：繼續(xù)出棧
//采用非遞歸中序遍歷二叉樹
public static void printTree(Node root){
SequenceStack<Node> stack=new SequenceStack<Node>();
List<Node> list=new ArrayList<Node>();
Node node=root;
//剛開始先把根節(jié)點壓入棧春叫，往后每次判斷節(jié)點不為空則壓棧
do {
while(node!=null){
stack.push(node);
node=node.left;
}
node=stack.pop();
list.add(node);
//如果出棧的結點存在右節(jié)點医舆，則指向該節(jié)點
if(node.right!=null){
node=node.right;
}else{//否則設置為空，下次循環(huán)繼續(xù)出棧
node=null;
}//當棧不為空象缀，或者當前節(jié)點引用不為空時循環(huán)
} while (!stack.isEmpty()||node!=null);
System.out.println(list);
}
- 后序遍歷
1.將根節(jié)點以及左結點依次入棧
2.獲取棧頂元素，對棧頂元素進行右孩子判斷爷速，諾為空央星，則遍歷棧頂元素并彈出棧，否則指向右孩子結點
3.重復1-2兩步
重點：這里需要注意pre變量在遍歷過程中的作用（下方代碼有詳細注釋該變量的作用）
//非遞歸實現(xiàn)后序遍歷
public static void printTree2(Node root){
SequenceStack<Node> stack=new SequenceStack<Node>();
List<Node> list=new ArrayList<Node>();
//定義兩個節(jié)點變量node和pre（這里需要注意pre節(jié)點的作用惫东，下方的注釋有詳細地介紹）
Node node=root;
Node pre=null;
do {
//將左結點一次壓入棧
while(node!=null){
stack.push(node);
node=node.left;
}
//獲取棧頂節(jié)點
node = stack.get();
//如果棧頂節(jié)點的右孩子不為空莉给，說明還得把右子樹壓入棧中，這里需要注意
//node.right!=pre這個條件廉沮，因為我們在遍歷的過程中颓遏，對于（子樹）根節(jié)點的判斷會存在兩次
//第一次是彈出左孩子節(jié)點后，對根節(jié)點進行是否有右孩子的判斷滞时，如果有叁幢，則將右孩子壓棧
//第二次是彈出右孩子節(jié)點后，這時候因為循環(huán)的原因（代碼的原因）坪稽，我們再次對根節(jié)點進行了右孩子判斷曼玩，
//所以這里就必須得判斷該右孩子節(jié)點是否在之前的循環(huán)中已經(jīng)判斷過了，如果判斷過了窒百，則彈出根節(jié)點黍判，否則壓入右孩子節(jié)點。
//總的來說篙梢，pre節(jié)點的作用是用來防止重復遍歷右孩子節(jié)點的顷帖。
if(node.right!=null&&node.right!=pre){
//node指向右孩子節(jié)點
node=node.right;
}else{//只要有一個條件不滿足則執(zhí)行
//彈出棧頂元素
node=stack.pop();
//遍歷棧頂元素
list.add(node);
//將pre指向當前彈出的元素，用來做下次對根節(jié)點的再次判斷時渤滞，右孩子不重復遍歷的一個條件
pre=node;
//將node設置為null贬墩，防止根節(jié)點重復壓入左孩子節(jié)點。
node=null;
}
} while (node!=null||!stack.isEmpty());
System.out.println(list);
}
- 層次遍歷
先將根節(jié)點入隊蔼水，當前節(jié)點是隊頭節(jié)點腥例，將其出隊并訪問，如果當前節(jié)點的左節(jié)點不為空將左節(jié)點入隊溉仑，如果當前節(jié)點的右節(jié)點不為空將其入隊。所以出隊順序也是從左到右依次出隊论咏。
public class PrintFromTopToBottom {
public static class TreeNode{
int val;
TreeNode left=null;
TreeNode right=null;
public TreeNode(int val) {
this.val = val;
}
}
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list=new ArrayList<Integer>(); //存放結果
Queue<TreeNode> queue= new LinkedList<TreeNode>(); //輔助隊列
if (root!=null){
//根節(jié)點入隊
queue.offer(root);
}
//隊列不為空，執(zhí)行循環(huán)
while (!queue.isEmpty()){
TreeNode node=queue.poll();
list.add(node.val); //將隊列元素輸出
//如果有左節(jié)點颁井，就把左節(jié)點加入
if (node.left!=null){
queue.offer(node.left);
}
//如果有右節(jié)點厅贪，就把右節(jié)點加入
if(node.right!=null){
queue.offer(node.right);
}
}
return list;
}
}
遞歸遍歷
public class TreeNode {
public char value;
public TreeNode left;
public TreeNode right;
TreeNode(char value) {
this.value = value;
}
TreeNode(char value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
}
public class Order {
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = init();
System.out.println("先序");
ProOrder(root);
System.out.println("中序");
InOrder(root);
System.out.println("后序");
PostOrder(root);
}
/** 構造樹 */
public static TreeNode init() {
TreeNode a = new TreeNode('A');
TreeNode b = new TreeNode('B', null, a);
TreeNode c = new TreeNode('C');
TreeNode d = new TreeNode('D', b, c);
TreeNode e = new TreeNode('E');
TreeNode f = new TreeNode('F', e, null);
TreeNode g = new TreeNode('G', null, f);
TreeNode h = new TreeNode('H', d, g);
return h;// root
}
/**
* 遞歸前序遍歷
*
* @param tree
*/
public static void ProOrder(TreeNode tree) {
System.out.println(tree.value);
if (tree.left != null) {
ProOrder(tree.left);
}
if (tree.right != null) {
ProOrder(tree.right);
}
}
/**
* 遞歸中序遍歷
*
* @param tree
*/
public static void InOrder(TreeNode tree) {
if (tree.left != null) {
InOrder(tree.left);
}
System.out.println(tree.value);
if (tree.right != null) {
InOrder(tree.right);
}
}
/**
* 遞歸后順遍歷
*
* @param tree
*/
public static void PostOrder(TreeNode tree) {
if (tree.left != null) {
PostOrder(tree.left);
}
if (tree.right != null) {
PostOrder(tree.right);
}
System.out.println(tree.value);
}
}
最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
