package com.yyq;

/**

 * Created by Administrator on 2015/9/15.

 */

public class MirrorOfBinaryTree {

    public static BinaryTreeNode mirrorOfBinaryTree(BinaryTreeNode pNode) {

        if (pNode == null)

            return null;

        if (pNode.getM_pLeft() == null && pNode.getM_pRight() == null)

            return null;

        BinaryTreeNode pTemp = pNode.getM_pLeft();

        pNode.setM_pLeft(pNode.getM_pRight());

        pNode.setM_pRight(pTemp);

        if (pNode.getM_pLeft() != null)

            mirrorOfBinaryTree(pNode.getM_pLeft());

        if (pNode.getM_pRight() != null)

            mirrorOfBinaryTree(pNode.getM_pRight());

        return pNode;

    }

    //先序遍历

    public static void preprintTree(BinaryTreeNode pRoot) {

        if (pRoot == null)

            return;

        System.out.print(pRoot.getM_nValue() + "\t");

        preprintTree(pRoot.getM_pLeft());

        preprintTree(pRoot.getM_pRight());

    }

    //中序遍历

    public static void midprintTree(BinaryTreeNode pRoot) {

        if (pRoot != null) {

            midprintTree(pRoot.getM_pLeft());

            System.out.print(pRoot.getM_nValue() + "\t");

            midprintTree(pRoot.getM_pRight());

        }

    }

    public static void Test(String testName, BinaryTreeNode pRoot){

        if (testName == null)

            return ;

        System.out.println("previous printing tree is:");

        preprintTree(pRoot);

        System.out.println();

        System.out.println("middle printing tree is:");

        midprintTree(pRoot);

        System.out.println("\n====="+testName+": MirrorRecursively=====");

        BinaryTreeNode pNode1 = mirrorOfBinaryTree(pRoot);

        System.out.println("previous printing tree is:");

        preprintTree(pNode1);

        System.out.println();

        System.out.println("middle printing tree is:");

        midprintTree(pNode1);

        System.out.println("\n====="+testName+": MirrorIteratively=====");

        BinaryTreeNode pNode2 = mirrorOfBinaryTree(pRoot);

        System.out.println("previous printing tree is:");

        preprintTree(pNode2);

        System.out.println();

        System.out.println("middle printing tree is:");

        midprintTree(pNode2);

        System.out.println();

    }

    // ====================测试代码====================

// 测试完全二叉树：除了叶子节点，其他节点都有两个子节点

//            8

//        6      10

//       5 7    9  11

    public static void Test1() {

        System.out.println("\n=====Test1 starts:=====");

        BinaryTreeNode pNode8 = new BinaryTreeNode(8);

        BinaryTreeNode pNode6 = new BinaryTreeNode(6);

        BinaryTreeNode pNode10 = new BinaryTreeNode(10);

        BinaryTreeNode pNode5 = new BinaryTreeNode(5);

        BinaryTreeNode pNode7 = new BinaryTreeNode(7);

        BinaryTreeNode pNode9 = new BinaryTreeNode(9);

        BinaryTreeNode pNode11 = new BinaryTreeNode(11);

        pNode8.connectTreeNodes(pNode6, pNode10);

        pNode6.connectTreeNodes(pNode5, pNode7);

        pNode10.connectTreeNodes(pNode9, pNode11);

        Test("Test1",pNode8);

        pNode8 = null;

    }

    // 测试二叉树：出叶子结点之外，左右的结点都有且只有一个左子结点

//            8

//          7

//        6

//      5

//

    public static void Test2() {

        System.out.println("\n=====Test2 starts:=====");

        BinaryTreeNode pNode8 = new BinaryTreeNode(8);

        BinaryTreeNode pNode7 = new BinaryTreeNode(7);

        BinaryTreeNode pNode6 = new BinaryTreeNode(6);

        BinaryTreeNode pNode5 = new BinaryTreeNode(5);

        BinaryTreeNode pNode4 = new BinaryTreeNode(4);

        pNode8.connectTreeNodes(pNode7, null);

        pNode7.connectTreeNodes(pNode6, null);

        pNode6.connectTreeNodes(pNode5, null);

        pNode5.connectTreeNodes(pNode4, null);

        Test("Test2",pNode8);

        pNode8 = null;

    }

    // 测试二叉树：出叶子结点之外，左右的结点都有且只有一个右子结点

//            8

//             7

//              6

//               5

//                4

    public static void Test3() {

        System.out.println("\n=====Test3 starts:=====");

        BinaryTreeNode pNode8 = new BinaryTreeNode(8);

        BinaryTreeNode pNode7 = new BinaryTreeNode(7);

        BinaryTreeNode pNode6 = new BinaryTreeNode(6);

        BinaryTreeNode pNode5 = new BinaryTreeNode(5);

        BinaryTreeNode pNode4 = new BinaryTreeNode(4);

        pNode8.connectTreeNodes(null, pNode7);

        pNode7.connectTreeNodes(null, pNode6);

        pNode6.connectTreeNodes(null, pNode5);

        pNode5.connectTreeNodes(null, pNode4);

        Test("Test3",pNode8);

        pNode8 = null;

    }

    // 测试空二叉树：根结点为空指针

    public static void Test4() {

        System.out.println("\n=====Test4 starts:=====");

        BinaryTreeNode pNode = null;

        Test("Test4",pNode);

    }

    // 测试只有一个结点的二叉树

    public static void Test5() {

        System.out.println("\n=====Test5 starts:=====");

        BinaryTreeNode pNode8 = new BinaryTreeNode(8);

        Test("Test5",pNode8);

        pNode8 = null;

    }

    public static void main(String[] args) {

        Test1();

        Test2();

        Test3();

        Test4();

        Test5();

    }

}