二叉樹的遍歷遞回非遞回

重點說一下二叉樹后序遍歷的非遞回實作
創建的二叉樹如下：

后序遍歷為：5 3 2 4 1

先序遍歷為：1 2 5 3 4

逆后序遍歷為：1 4 2 3 5

從逆后序遍歷與先序遍歷的關系中我們可以知道逆后序遍歷序列為先序遍歷交換左右子樹的遍歷順序得到的，所以我們得到了逆后序序列之后然后逆序就可以得到后序遍歷的序列了，所以需要兩個堆疊，第一個堆疊用來存盤先序遍歷交換左右子樹的遍歷的中介結果，第二個是存盤后序遍歷的結果（逆序也就是可以理解為先進后出的意思）

下面是模仿元素進堆疊與出堆疊的程序：

① 1節點進堆疊，在回圈中彈出1節點壓入到第二個堆疊中，發現左右節點不為空那么將左右節點壓入堆疊1，這個與先序遍歷中將左右子樹壓入到堆疊頂的順序是相反的

② 彈出4節點壓入到第二個堆疊中，發現左右孩子都為空那么不進行任何的操作

③ 彈出2節點壓入到第二個堆疊中，發現左右節點不為空那么將左右節點壓入到堆疊1中

④ 彈出3節點壓入到第二個堆疊中，發現左右孩子都為空不進行任何操作

⑤ 彈出5節點壓入到第二個堆疊中，發現左右孩子都為空不進行任何操作

最后堆疊為空那么退出回圈結束
代碼：

  1 public class 樹的遍歷 {
  2     //前序 遞回
  3     public static void preOrderTraversal(int[] nums, int i) {
  4         if(i >= nums.length || nums[i] == -1) {
  5             return;
  6         }
  7         System.out.print(nums[i] + " ");
  8         preOrderTraversal(nums, 2 * i + 1);
  9         preOrderTraversal(nums, 2 * i + 2);
 10     }
 11     //前序 非遞回
 12     public static void preOrderTraversal2(int[] nums, int i) {
 13         LinkedList<Integer> list = new LinkedList<>();
 14         //i < nums.length && nums[i] != -1表示nums[i]存在
 15         while(i < nums.length && nums[i] != -1 || !list.isEmpty()) {
 16             while(i < nums.length && nums[i] != -1) {
 17                 System.out.print(nums[i] + " ");
 18                 list.push(i);
 19                 i = 2 * i + 1;//nums[i]左節點
 20             }
 21             i = list.pop() * 2 + 2;//nums[i]右節點
 22         }
 23 
 24     }
 25     //中序 遞回
 26     public static void inOrderTraversal(int[] nums, int i) {
 27         if(i >= nums.length || nums[i] == -1) {
 28             return;
 29         }
 30         inOrderTraversal(nums, 2 * i + 1);
 31         System.out.print(nums[i] + " ");
 32         inOrderTraversal(nums, 2 * i + 2);
 33     }
 34     //中序 非遞回
 35     public static void inOrderTraversal2(int[] nums, int i) {
 36         LinkedList<Integer> list = new LinkedList<>();
 37         while(i < nums.length && nums[i] != -1 || !list.isEmpty()) {
 38             while(i < nums.length && nums[i] != -1) {
 39                 list.push(i);
 40                 i = 2 * i + 1;
 41             }
 42             int k = list.pop();
 43             System.out.print(nums[k] + " ");
 44             i = k * 2 + 2;
 45         }
 46     }
 47 
 48     //后序 遞回
 49     public static void postOrderTraversal(int[] nums, int i) {
 50         if(i >= nums.length || nums[i] == -1) {
 51             return;
 52         }
 53         postOrderTraversal(nums, 2 * i + 1);
 54         System.out.print(nums[i] + " ");
 55         postOrderTraversal(nums, 2 * i + 2);
 56 
 57     }
 58     
 59     //后續 非遞回 雙堆疊
 60     public static void postOrderTraversal2(int[] nums, int i) {
 61         LinkedList<Integer> stack1 = new LinkedList<>();
 62         LinkedList<Integer> stack2 = new LinkedList<>();
 63         stack1.push(i);
 64         while (!stack1.isEmpty()) {
 65             i = stack1.pop();
 66             stack2.push(i);//把stack1堆疊頂的元素壓進list中
 67             i = 2 * i + 1;
 68             if(i < nums.length && nums[i] != -1)
 69                stack1.push(i);
 70             ++i;
 71             if(i < nums.length && nums[i] != -1)
 72                 stack1.push(i);
 73         }
 74         for (int k: stack2) {
 75             System.out.print(nums[k] + " ");
 76         }
 77 
 78     }
 79 
 80     //層序遍歷 佇列實作
 81     public static void levelOrder(int[] nums, int i) {
 82         LinkedList<Integer> que = new LinkedList<>();
 83         que.push(i);
 84         while(!que.isEmpty()) {
 85             i = que.removeFirst();
 86             System.out.print(nums[i] + " ");
 87             i = 2 * i + 1;
 88             if(i < nums.length && nums[i] != -1)
 89                 que.addLast(i);
 90             ++i;
 91             if(i < nums.length && nums[i] != -1)
 92                 que.addLast(i);
 93         }
 94     }
 95 
 96     public static void main(String[] args) {
 97         int[] nums = new int[]{1, 2, 3, -1, 5, 6, -1};
 98         postOrderTraversal2(nums, 0);
 99     }
100 }

標籤：其他

上一篇：計算機基礎資料結構講解第八篇-堆疊

下一篇：冪集問題