二叉樹建立

先給出結點結構:

static class Node { public int val; public Node left; public Node right; public Node(int val) { this.val = val; } }

兩種建立方式:

• 可以根據二叉樹根節點和左右子結點的下标關系遞歸建立二叉樹，層次輸入二叉樹結點；
• 也可以使用輸入流前序建立二叉樹(注意空樹要輸入-1)；

1、根據下标關系

// given a arr to build static Node createTree(int arr[], int i) { if (i >= arr.length || arr[i] == -1) return null; Node root = new Node(arr[i]); root.left = createTree(arr, 2 * i 1); root.right = createTree(arr, 2 * i 2); return root; }

大緻過程如下:

2、前序輸入(cin)建立

// cin method static Node buildTree(Scanner cin) { Node root = null; int data = cin.nextInt(); if (data != -1) { root = new Node(data); root.left = buildTree(cin); root.right = buildTree(cin); } return root; }

過程如下:

前序遍曆

1、遞歸前序

static void preOrder(Node T) { if (T == null) return; System.out.print(T.val " "); preOrder(T.left); preOrder(T.right); }

2、非遞歸前序

前序遍曆順序為: 根結點->左子樹->右子樹，所以對于正在訪問的根結點，可以直接訪問，訪問完之後，按照相同的方式訪問左子樹，再訪問右子樹，過程如下 :

• 如果當前節點p不為空，訪問結點p，并将結點p入棧，并繼續訪問左子樹(直到左子樹為空)；
• 否則将棧頂元素出棧，并訪問棧頂的元素的右子樹；
• 直到棧為空且p為空，循環結束。

代碼:

static void iterativePre(Node root) { Stack<Node> s = new Stack<>(); Node p = root; while (!s.empty() || p != null) { if (p != null) {//也可以寫一個while循環，直到左子樹為空 s.push(p); System.out.print(p.val " "); p = p.left; } else { p = s.pop(); p = p.right; } } }

也可以将上面的一直訪問到左子樹為空寫成一個while循環:

static void iterativePre2(Node root) { Stack<Node> s = new Stack<>(); Node p = root; while (!s.empty() || p != null) { while (p != null) { // while循環，直到左子樹為空 s.push(p); System.out.print(p.val " "); p = p.left; } p = s.pop(); p = p.right; } }

還有另外一種寫法是:

• 先把根節點入棧，然後每次出棧一個元素，先訪問這個元素，然後如果它的右子樹存在，就入棧，如果它的左子樹存在也入棧；
• 為什麼要先入右子樹呢，因為，前序遍曆是中->左->右，而棧可以逆序，所以先右再左；

這個方法在後續遍曆的雙棧法中有體現，那個隻是這個稍微的修改。

static void iterativePre3(Node root) { if (root == null) return; Node p = root; Stack<Node> stack = new Stack<>(); stack.add(p); while (!stack.isEmpty()) { p = stack.pop(); System.out.print(p.val " "); if (p.right != null)// 先右再左即可 stack.push(p.right); if (p.left != null) stack.push(p.left); } }

---

中序遍曆

1、遞歸中序

static void inOrder(Node T) { if (T == null) return; inOrder(T.left); System.out.print(T.val " "); inOrder(T.right); }

2、非遞歸中序

中序遍曆 : 左子樹->根->右子樹，過程如下：

• 當前節點不空!= null，壓入棧中(和前序遍曆不同的是，不需要打印)，當前節點向左；
• 當前節點為空== null，從棧中拿出一個并且打印(在這裡打印) ，當前節點向右；

直到棧為空且p為空，循環結束。

/** * 1)、當前節點不空(!=null)，壓入棧中(和前序遍曆不同的是，不需要打印)，當前節點向左； * 2)、當前節點為空(==null)，從棧中拿出一個并且打印(在這裡打印) ，當前節點向右； */ static void iterativeIn(Node root) { if (root == null) return; Stack<Node> s = new Stack<>(); Node p = root; while (!s.empty() || p != null) { if (p != null) { s.push(p); p = p.left; } else { p = s.pop(); System.out.print(p.val " "); //在這裡打印 p = p.right; } } }

同理，那個一直訪問左孩子那裡也可以改成whlie:

static void iterativeIn2(Node root) { if (root == null) return; Stack<Node> s = new Stack<>(); Node p = root; while (!s.empty() || p != null) { while (p != null) { //這裡改成while s.push(p); p = p.left; } p = s.pop(); System.out.print(p.val " "); //在這裡打印 p = p.right; } }

---

後序遍曆

1、遞歸後序

static void postOrder(Node T) { if (T == null) return; postOrder(T.left); postOrder(T.right); System.out.print(T.val " "); }

2、非遞歸後序

1)、雙棧法

這個其實就是非遞歸前序(iterativePre3)的稍微一點改進。

• 首先，前序遍曆入棧(iterativePre3)的順序是先 右　再左；
• 這時，我們可以做到反過來先　左　再右，這樣遍曆的順序可以做到 "中右左"，而後續遍曆是 "左右中"，正好是前面那個的相反，所以我們再使用一個棧反轉保存即可；

代碼:

/** * 非遞歸後續1(雙棧法解決非遞歸後續) * 後續遍曆是要實現　　　左->右->中 * 這個方法和前序遍曆的第二種方法　隻是多了一個棧而已 * 因為　前序遍曆是 中->左->右　　壓棧順序是 右->左 * 這樣，我們就很容易實現　中->右->左遍曆　　壓棧順序是　左->右 * 而後續遍曆是要實現 左->右->中， * 我們把上面的　　中右左　壓入到另一個棧中　就實現了　左右中 */ static void iterativePos(Node root) { Stack<Node> s = new Stack<>(), s2 = new Stack<>(); Node p; s.push(root); while (!s.empty()) { p = s.pop(); s2.push(p); if (p.left != null) s.push(p.left); //這裡是先左再右 (非遞歸前序是先右再左) if (p.right != null) s.push(p.right); } while (!s2.empty()) System.out.print(s2.pop().val " "); }

2)、設置pre結點

過程如下:

• 對于任一結點p，先将其入棧；
• 可以訪問的情況: ①若p不存在左孩子和右孩子，則可以直接訪問它。②或者p存在左孩子或者右孩子，但是左孩子和右孩子都已經被訪問過了，則也可以直接訪問該結點；
• 若非上述兩種情況，則将右孩子和左孩子依次入棧。這樣可以保證每次取棧頂元素時，左孩子在右孩子前面被訪問，根結點在左孩子和右孩子訪問之後被訪問；

代碼:

/*** 非遞歸後續2(設置pre結點) */ static void iterativePos2(Node root) { Node cur, pre = null; Stack<Node> s = new Stack<>(); s.push(root); while (!s.empty()) { cur = s.peek(); // 兩種可以訪問的情況 if ((cur.left == null && cur.right == null) || ((pre != null) && (pre == cur.left || pre == cur.right))) { System.out.print(cur.val " "); s.pop(); pre = cur; } else { if (cur.right != null) s.push(cur.right); if (cur.left != null) s.push(cur.left); } } }

---

層次遍曆

很簡單。利用隊列BFS即可，每次訪問完p，若左右孩子存在，則入隊，直至隊空；

static void levelOrder(Node root) { if (root == null) return; Queue<Node> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { Node now = queue.poll(); System.out.print(now.val " "); if (now.left != null) queue.add(now.left); if (now.right != null) queue.add(now.right); } }

尋找樹中有沒有值為x的結點

遞歸條件有兩個，一個是為空代表沒找到，找到了的話直接返回，否則遞歸查找左右子樹。

//查找某個值為x的結點 static Node search(Node T, int x) { if (T == null) return null; if (T.val == x) return T; else { if (search(T.left, x) == null) return search(T.right, x); else return search(T.left, x); } }

統計樹中結點的個數

樹中結點的個數等于根節點(1) 左子樹結點個數 右子樹的個數，遞歸求解即可。

//統計結點個數 static int count(Node T) { if (T == null) return 0; else return count(T.left) count(T.right) 1; }

計算樹的高度

也是遞歸求解，左右子樹的高度中的比較高的加上根節點就是樹的高度。

//計算二叉樹的深度 static int depth(Node T) { if (T == null) return 0; return Math.max(depth(T.left), depth(T.right)) 1; }

判斷兩棵樹是不是相等

也是遞歸求解，兩棵樹相等，既要根節點的值相等，而且左右子樹也要相等。

//判斷兩棵樹是不是相等 static boolean is_SameTree(Node T1, Node T2) { if (T1 == null && T2 == null) return true; else { return T1 != null && T2 != null && T1.val == T2.val && is_SameTree(T1.left, T2.left) && is_SameTree(T1.right, T2.right); } }

,