java通过先序遍历和中序遍历获取树结构

本文主要是介绍java通过先序遍历和中序遍历获取树结构，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

     1、首先通过先序遍历找到根节点
     2、在中序遍历中通过该根节点划分左右子树
     3、再根据先序遍历找出左右子树（中序遍历子树）的根节点
     4、重复上述过程，直到无数值

（方法实现有点繁琐，因为拼接字符串，有待改进）

    public static void main(String[] args) {
	// write your code here
        //适用于无相同数字的情况
        List<Integer> hTreeList = new ArrayList<>();
        List<Integer> mTreeList = new ArrayList<>();
        List<Integer> lTreeList = new ArrayList<>();
        List<Integer> rTreeList = new ArrayList<>();
        //先序遍历,根左右
        int [] hTree = {1,2,4,7,3,5,6,8};
        //中序遍历,左根右
        int [] mTree = {4,2,7,1,5,3,8,6};
        for(int j = 0;j<hTree.length;j++){
            hTreeList.add(hTree[j]);
        }
        for(int j = 0;j<mTree.length;j++){
            mTreeList.add(mTree[j]);
        }
        //(1(2(4,7),3(5,6(8,null))))
        StringBuilder tree = new StringBuilder();
        int root = hTreeList.get(0);
        getLeftAndRightTree(hTreeList,mTreeList,root,lTreeList,rTreeList,tree);
        getString(tree);
        System.out.println(tree);
    }

    /**
     * 1、首先通过先序遍历找到根节点
     * 2、在中序遍历中通过该根节点划分左右子树
     * 3、再根据先序遍历找出左右子树（中序遍历子树）的根节点
     * 4、重复上述过程，直到无数值
     */


    /**
     * 处理先序遍历
     * @param hTree
     * @param mTree
     * @param root
     * @param lTree
     * @param rTree
     * @param tree
     */
    public static void getRoot(List<Integer> hTree, List<Integer> mTree, int root, List<Integer> lTree, List<Integer> rTree, StringBuilder tree){
        boolean result = false;
        if(mTree.size() > 1){
            for (Integer ht : hTree) {
                for (Integer mt : mTree) {
                    if(ht.equals(mt)){
                        root = ht;
                        result = true;
                        break;
                    }
                }
                if(result){
                    break;
                }
            }
        }
        getLeftAndRightTree(hTree,mTree,root,lTree,rTree,tree);
    }

    /**
     * 处理中序遍历
     * @param hTree
     * @param mTree
     * @param root
     * @param lTree
     * @param rTree
     * @param tree
     */
    public static void getLeftAndRightTree(List<Integer> hTree, List<Integer> mTree, int root, List<Integer> lTree, List<Integer> rTree, StringBuilder tree){
        lTree.clear();
        rTree.clear();
        boolean result = false;
        for (Integer mt : mTree) {
            //找到根节点
            if(mt.equals(root)){
                if(tree.length()>0){
                    if(tree.substring(tree.length()-1,tree.length()).equals(")")){
                        tree.append(","+mt);
                    }else{
                        if(mTree.size() == 2){
                            tree.append(","+mt);
                        }else{
                            tree.append("("+mt);
                        }

                    }
                }else{
                    tree.append("("+mt);
                }
                result=true;
                continue;
            }
            if(!result){
                //存储左子树
                lTree.add(mt);
            }else {
                //存储右子树
                rTree.add(mt);
            }
        }
        if(lTree.size()==1){
            if(tree.substring(tree.length()-1,tree.length()).equals(")")){
                tree.append(",("+lTree.get(0));
            }else{
                tree.append("("+lTree.get(0));
            }

        }
        if(rTree.size()==1){
            tree.append(","+rTree.get(0)+")");
        }
        List<Integer> baseTree = new ArrayList<>();
        baseTree.addAll(rTree);
        if(lTree.size()>1){
            mTree.clear();
            mTree.addAll(lTree);
            getRoot(hTree,mTree,root,lTree,rTree,tree);
        }
        if(baseTree.size()>1){
            mTree.clear();
            mTree.addAll(baseTree);
            getRoot(hTree,mTree,root,lTree,rTree,tree);
        }
    }

    /**
     * 补全字符串
     * @param tree
     */
    public static void getString(StringBuilder tree){
        String str = tree.toString();
        int j = str.split("\\(").length-str.split("\\)").length;
        for(int i = 0;i<j;i++){
            tree.append(")");
        }
    }

这篇关于java通过先序遍历和中序遍历获取树结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！