添加树的一些算法

byhieg · byhieg · commit 02de7695d154 · 2017-04-16T16:58:48.000+08:00
diff --git a/src/main/java/cn/byhieg/algorithmtutorial/BinaryTree.java b/src/main/java/cn/byhieg/algorithmtutorial/BinaryTree.java
@@ -162,6 +162,11 @@ public static int getNodes(Node root) {
         return getNodes(root.left) + getNodes(root.right) + 1;
     }
 
+    /**
+     * &#24471;&#21040;&#26641;&#30340;&#21494;&#23376;&#33410;&#28857;&#30340;&#25968;&#30446;
+     * @param root
+     * @return
+     */
     public static int getLeafs(Node root) {
         if (root == null) {
             return 0;
@@ -173,6 +178,70 @@ public static int getLeafs(Node root) {
 
     }
 
+
+    /**
+     * &#35745;&#31639;&#26641;&#30340;&#28145;&#24230;
+     * @param root
+     * @return
+     */
+    public static int getHeight(Node root){
+        if (root == null) {
+            return 0;
+        }
+        int leftHeight = getHeight(root.left) + 1;
+        int rightHeight = getHeight(root.right) + 1;
+        return leftHeight > rightHeight ? leftHeight : rightHeight;
+    }
+
+    /**
+     * &#35745;&#31639;&#31532;K&#23618;&#30340;&#33410;&#28857;&#25968;
+     * @param root
+     * @param k
+     * @return
+     */
+    public static int calcKNodes(Node root, int k) {
+        if (root == null || k < 0) {
+            return 0;
+        }
+        if (k == 0){
+            return 1;
+        }
+        return calcKNodes(root.left, k - 1) + calcKNodes(root.right, k - 1);
+
+    }
+
+    /**
+     * &#21028;&#26029;&#20004;&#20010;&#26641;&#30340;&#32467;&#26500;&#26159;&#21542;&#30456;&#21516;
+     * @param root1
+     * @param root2
+     * @return
+     */
+    public static boolean isCommon(Node root1, Node root2) {
+        if (root1 == null && root2 == null) {
+            return true;
+        } else if (root1 == null || root2 == null) {
+            return false;
+        }else{
+            boolean isLeftCommon = isCommon(root1.left, root2.left);
+            boolean isRightCommon = isCommon(root1.right, root2.right);
+            return isLeftCommon && isRightCommon;
+        }
+    }
+
+    /**
+     * &#24471;&#21040;&#26641;&#30340;&#38236;&#20687;&#65292;&#21363;&#23545;&#20110;&#27599;&#19968;&#20010;&#33410;&#28857;&#65292;&#20132;&#25442;&#20182;&#20204;&#30340;&#24038;&#21491;&#23401;&#23376;&#33410;&#28857;&#12290;
+     * @param root
+     */
+    public static void mirror(Node root) {
+        if (root != null) {
+            Node tmp = root.left;
+            root.left = root.right;
+            root.right = tmp;
+            mirror(root.left);
+            mirror(root.right);
+        }
+    }
+
     public static class Node {
         public int data;
         public Node left;
diff --git a/src/test/java/cn/byhieg/algorithmtutorialtest/BinaryTreeTest.java b/src/test/java/cn/byhieg/algorithmtutorialtest/BinaryTreeTest.java
@@ -1,7 +1,6 @@
 package cn.byhieg.algorithmtutorialtest;
 
 import cn.byhieg.algorithmtutorial.BinaryTree;
-import cn.byhieg.iotutorial.bytestreamio.BufferdInputStreamExample;
 import junit.framework.TestCase;
 
 /**
@@ -10,7 +9,6 @@
  */
 public class BinaryTreeTest extends TestCase {
 
-
     BinaryTree.Node root = new BinaryTree.Node(1);
     public void setUp() throws Exception {
         super.setUp();
@@ -69,11 +67,22 @@ public void testLevelOrder() throws Exception {
     }
 
     public void testGetNodes() throws Exception {
-        System.out.println("&#33410;&#28857;&#25968;" + BinaryTree.getNodes(root));
+        System.out.print("&#33410;&#28857;&#25968;" + BinaryTree.getNodes(root));
     }
 
     public void testGetLeafs() throws Exception {
-        System.out.println("&#21494;&#23376;&#25968;" + BinaryTree.getLeafs(root));
+        System.out.print("&#21494;&#23376;&#25968;" + BinaryTree.getLeafs(root));
+    }
+
+    public void testGetHeight() throws Exception {
+        System.out.print("&#26641;&#30340;&#39640;&#24230;" + BinaryTree.getHeight(root));
     }
 
+    public void testCalcKNodes() throws Exception {
+        System.out.print("&#31532;2&#23618;&#30340;&#33410;&#28857;&#25968;" + BinaryTree.calcKNodes(root,2));
+    }
+
+    public void testMirror() throws Exception {
+        BinaryTree.mirror(root);
+    }
 }
