数据结构与算法-树

package *;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: data-structure
 * @description: 树
 * @author: ChenWenLong
 * @create: 2019-09-10 10:29
 **/
public class MyTree<T> {

    //树的节点
    private static class TreeNode<T>{
        T value;
        TreeNode<T> leftChild;
        TreeNode<T> rightChild;

        TreeNode(T value) {
            this.value = value;
        }

        /**
         * 功能描述:
         * 〈往树的左边添加子节点〉
         *
         * @params : [value]
         * @return : void
         * @author : cwl
         * @date : 2019/9/10 10:36
         */
        public void addLeft(T value){
            TreeNode<T> leftChild = new TreeNode<T>(value);
            this.leftChild = leftChild;
        }

        /**
         * 功能描述:
         * 〈往树的右边添加子节点〉
         *
         * @params : [value]
         * @return : void
         * @author : cwl
         * @date : 2019/9/10 10:37
         */
        public void addRight(T value){
            TreeNode<T> rightChild = new TreeNode<T>(value);
            this.rightChild = rightChild;
        }

        /**
         * 功能描述:
         * 〈重载节点中是否相等〉
         *
         * @params : [obj]
         * @return : boolean
         * @author : cwl
         * @date : 2019/9/10 10:37
         */
        @Override
        public boolean equals(Object obj) {
            if(!(obj instanceof TreeNode)){
                return false;
            }
            return this.value.equals(((TreeNode<?>)obj).value);
        }

        @Override
        public int hashCode() {
            return this.value.hashCode();
        }

        @Override
        public String toString(){
            return this.value==null?"":this.value.toString();
        }
    }

    /**
     * 功能描述:
     * 〈判断树当中节点的个数〉
     *
     * @params : [root]
     * @return : int
     * @author : cwl
     * @date : 2019/9/10 10:40
     */
    public static <T> int getTreeNum(TreeNode<T> root) {
        if (root == null) {
            return 0;
        }
        return getTreeNum(root.leftChild) + getTreeNum(root.rightChild) + 1;
    }

    /**
     * 功能描述:
     * 〈判断树的深度〉
     *
     * @params : [root]
     * @return : int
     * @author : cwl
     * @date : 2019/9/10 10:43
     */
    public static <T> int getTreeDepth(TreeNode<T> root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = getTreeDepth(root.leftChild) + 1;
        int rightDepth = getTreeDepth(root.rightChild) + 1;
        return Math.max(leftDepth, rightDepth);
    }

    /**
     * 功能描述:
     * 〈前序遍历〉
     *
     * @params : [root]
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 10:44
     */
    public static <T> void preOrderTravel(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        visitNode(root);
        preOrderTravel(root.leftChild);
        preOrderTravel(root.rightChild);
    }

    /**
     * 功能描述:
     * 〈中序遍历〉
     *
     * @params : [root]
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 10:45
     */
    public static <T> void midOrderTravel(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        midOrderTravel(root.leftChild);
        visitNode(root);
        midOrderTravel(root.rightChild);
    }

    /**
     * 功能描述:
     * 〈后序遍历〉
     *
     * @params : [root]
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 10:45
     */
    public static <T> void backOrderTravel(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        backOrderTravel(root.leftChild);
        backOrderTravel(root.rightChild);
        visitNode(root);
    }

    /**
     * 功能描述:
     * 〈打印每个节点〉
     *
     * @params : [node]
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 10:46
     */
    private static <T> void visitNode(TreeNode<T> node) {
        System.out.print(node.value + "\t");
    }

    /**
     * 功能描述:
     * 〈分层遍历〉
     *
     * @params : [root]
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 10:46
     */
    public static <T> void levelTravel(TreeNode<T> root) {
        Queue<TreeNode<T>> q = new LinkedList<TreeNode<T>>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode<T> temp = q.poll();
            visitNode(temp);
            if (temp.leftChild != null) {
                q.offer(temp.leftChild);
            }
            if (temp.rightChild != null) {
                q.offer(temp.rightChild);
            }
        }
    }

    /**
     * 功能描述:
     * 〈求第K层的节点个数〉
     *
     * @params : [root, k]
     * @return : int
     * @author : cwl
     * @date : 2019/9/10 10:48
     */
    public static <T> int getNumForKlevel(TreeNode<T> root, int k) {
        if (root == null || k < 1) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int leftNum = getNumForKlevel(root.leftChild, k - 1);
        int rightNum = getNumForKlevel(root.rightChild, k - 1);
        return leftNum + rightNum;
    }

    /**
     * 功能描述:
     * 〈获取该节点的叶子节点的个数〉
     *
     * @params : [root]
     * @return : int
     * @author : cwl
     * @date : 2019/9/10 10:49
     */
    public static <T> int getLeafNum(TreeNode<T> root) {
        if (root == null) {
            return 0;
        }
        if (root.leftChild == null && root.rightChild == null) {
            return 1;
        }
        int leftNum = getLeafNum(root.leftChild);
        int rightNum = getLeafNum(root.rightChild);
        return leftNum + rightNum;
    }

    /**
     * 功能描述:
     * 〈交换根节点的左右子树〉
     *
     * @params : [root]
     * @return : com.cwl.data.tree.MyTree.TreeNode<T>
     * @author : cwl
     * @date : 2019/9/10 10:49
     */
    public static <T> TreeNode<T> exchange(TreeNode<T> root) {
        if (root == null) {
            return null;
        }
        TreeNode<T> left = exchange(root.leftChild);
        TreeNode<T> right = exchange(root.rightChild);
        root.leftChild = right;
        root.rightChild = left;
        return root;
    }

    /**
     * 功能描述:
     * 〈查看node是否是root的子节点 〉
     *
     * @params : [root, node]
     * @return : boolean
     * @author : cwl
     * @date : 2019/9/10 10:51
     */
    public static <T> boolean nodeIsChild(TreeNode<T> root, TreeNode<T> node) {
        if (root == null || node == null) {
            return false;
        }
        if (root == node) {
            return true;
        }
        boolean isFind = nodeIsChild(root.leftChild, node);
        if (!isFind) {
            isFind = nodeIsChild(root.rightChild, node);
        }
        return isFind;
    }

    /**
     * 功能描述:
     * 〈返回两个节点lnode和rnode的以root为根节点的公共父节点〉
     *
     * @params : [root, lNode, rNode]
     * @return : com.cwl.data.tree.MyTree.TreeNode<T>
     * @author : cwl
     * @date : 2019/9/10 10:51
     */
    public static <T> TreeNode<T> findAllFatherNode(TreeNode<T> root,
                                                    TreeNode<T> lNode, TreeNode<T> rNode) {
        if (lNode == root || rNode == root) {
            return root;
        }
        if (root == null || lNode == null || rNode == null) {
            return null;
        }
        // 如果lNode是左子树的节点
        if (nodeIsChild(root.leftChild, lNode)) {
            if (nodeIsChild(root.rightChild, rNode)) {
                return root;
            } else {
                return findAllFatherNode(root.leftChild, lNode, rNode);
            }
        } else {
            if (nodeIsChild(root.leftChild, rNode)) {
                return root;
            } else {
                return findAllFatherNode(root.rightChild, lNode, rNode);
            }
        }
    }

    /**
     * 功能描述:
     * 〈根据前序和中序构建二叉树 〉
     *
     * @params : [pre, mid]
     * @return : com.cwl.data.tree.MyTree.TreeNode<T>
     * @author : cwl
     * @date : 2019/9/10 10:54
     */
    public static <T> TreeNode<T> getTreeFromPreAndMid(List<T> pre, List<T> mid) {
        if (pre == null || mid == null || pre.size() == 0 || mid.size() == 0) {
            return null;
        }
        if (pre.size() == 1) {
            return new TreeNode<T>(pre.get(0));
        }
        TreeNode<T> root = new TreeNode<T>(pre.get(0));
        // 找出根节点在中序中的位置
        int index = 0;
        while (!mid.get(index++).equals(pre.get(0))) {
        }
        // 构建左子树的前序
        List<T> preLeft = new ArrayList<T>(index);
        // 左子树的中序
        List<T> midLeft = new ArrayList<T>(index);
        for (int i = 1; i < index; i++) {
            preLeft.add(pre.get(i));
        }
        for (int i = 0; i < index - 1; i++) {
            midLeft.add(mid.get(i));
        }

        // 重建左子树
        root.leftChild = getTreeFromPreAndMid(preLeft, midLeft);
        // 右子树的前序
        List<T> preRight = new ArrayList<T>(pre.size() - index - 1);
        // 右子树的中序
        List<T> midRight = new ArrayList<T>(pre.size() - index - 1);
        for (int i = 0; i <= pre.size() - index - 1; i++) {
            preRight.add(pre.get(index + i));
        }
        for (int i = 0; i <= pre.size() - index - 1; i++) {
            midRight.add(mid.get(index + i));
        }
        // 重建→子树
        root.rightChild = getTreeFromPreAndMid(preRight, midRight);
        return root;
    }

    /**
     * 功能描述:
     * 〈查看node1和node2两棵树是否相等(两棵树所有节点都相等)〉
     *
     * @params : [node1, node2]
     * @return : boolean
     * @author : cwl
     * @date : 2019/9/10 10:55
     */
    public static <T> boolean equals(TreeNode<T> node1, TreeNode<T> node2) {
        if (node1 == null && node2 == null) {
            return true;
        } else if (node1 == null || node2 == null) {
            return false;
        }
        boolean isEqual = node1.value.equals(node2.value);
        boolean isLeftEqual = equals(node1.leftChild, node2.leftChild);
        boolean isRightEqual = equals(node1.rightChild, node2.rightChild);
        return isEqual && isLeftEqual && isRightEqual;
    }
}