二叉树的各种操作(递归和非递归遍历,树深度,结点个数等等)

二叉树建立

先给出结点结构:
1 2 3 4 5 6 7 8 9 static class Node { public int val; public Node left; public Node right; public Node(int val) { this.val = val; } }

两种建立方式:

  • 可以根据二叉树根节点和左右子结点的下标关系递归建立二叉树，层次输入二叉树结点；
  • 也可以使用输入流前序建立二叉树(注意空树要输入-1)；

1、根据下标关系
1 2 3 4 5 6 7 8 9 ``` // given a arr to build static Node createTree(int arr[], int i) { if (i >= arr.length

大致过程如下:
这里写图片描述

2、前序输入(cin)建立
1 2 3 4 5 6 7 8 9 10 11 // 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、递归前序
1 2 3 4 5 6 7 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为空，循环结束。

代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` static void iterativePre(Node root) { Stack s = new Stack<>(); Node p = root; while (!s.empty()

也可以将上面的一直访问到左子树为空写成一个while循环:
1 2 3 4 5 6 7 8 9 10 11 12 13 ``` static void iterativePre2(Node root) { Stack s = new Stack<>(); Node p = root; while (!s.empty()

还有另外一种写法是:

  • 先把根节点入栈，然后每次出栈一个元素，先访问这个元素，然后如果它的右子树存在，就入栈，如果它的左子树存在也入栈；
  • 为什么要先入右子树呢，因为，前序遍历是中->左->右，而栈可以逆序，所以先右再左；

这个方法在后续遍历的双栈法中有体现，那个只是这个稍微的修改。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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、递归中序
1 2 3 4 5 6 7 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ``` /** * 1)、当前节点不空(!=null)，压入栈中(和前序遍历不同的是，不需要打印)，当前节点向左； * 2)、当前节点为空(==null)，从栈中拿出一个并且打印(在这里打印) ，当前节点向右； */ static void iterativeIn(Node root) { if (root == null) return; Stack s = new Stack<>(); Node p = root; while (!s.empty()

同理，那个一直访问左孩子那里也可以改成whlie:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ``` static void iterativeIn2(Node root) { if (root == null) return; Stack s = new Stack<>(); Node p = root; while (!s.empty()

后序遍历

1、递归后序
1 2 3 4 5 6 7 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 /** * 非递归后续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存在左孩子或者右孩子，但是左孩子和右孩子都已经被访问过了，则也可以直接访问该结点；
  • 若非上述两种情况，则将右孩子和左孩子依次入栈。这样可以保证每次取栈顶元素时，左孩子在右孩子前面被访问，根结点在左孩子和右孩子访问之后被访问；

代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ``` /*** 非递归后续2(设置pre结点) */ static void iterativePos2(Node root) { Node cur, pre = null; Stack s = new Stack<>(); s.push(root); while (!s.empty()) { cur = s.peek(); // 两种可以访问的情况 if ((cur.left == null && cur.right == null)

层次遍历

很简单。利用队列BFS即可，每次访问完p，若左右孩子存在，则入队，直至队空；
1 2 3 4 5 6 7 8 9 10 11 12 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的结点

递归条件有两个，一个是为空代表没找到，找到了的话直接返回，否则递归查找左右子树。
1 2 3 4 5 6 7 8 9 10 11 12 13 //查找某个值为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) + 左子树结点个数 + 右子树的个数，递归求解即可。
1 2 3 4 5 6 7 //统计结点个数 static int count(Node T) { if (T == null) return 0; else return count(T.left) + count(T.right) + 1; }

计算树的高度

也是递归求解，左右子树的高度中的比较高的加上根节点就是树的高度。
1 2 3 4 5 6 //计算二叉树的深度 static int depth(Node T) { if (T == null) return 0; return Math.max(depth(T.left), depth(T.right)) + 1; }

判断两棵树是不是相等

也是递归求解，两棵树相等，既要根节点的值相等，而且左右子树也要相等。
1 2 3 4 5 6 7 8 9 //判断两棵树是不是相等 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); } }

完整测试代码

完整的测试代码，这里输入的样例树(就是建树的时候那个例子)如下:

这里写图片描述

代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 ``` import java.io.BufferedInputStream; import java.util.*; public class BinaryTree { static class Node { public int val; public Node left; public Node right; public Node(int val) { this.val = val; } } // given a arr to build static Node createTree(int arr[], int i) { if (i >= arr.length

运行效果如下图: