ツリーの再構築(Java実装)

32994 ワード

剣指オフ

問題の説明
本題では,二叉木の前順遍歴シーケンスと中順遍歴シーケンスに基づいて二叉木を再構築する必要があり,Javaで二つの実装を書きましたが,個人的には第一の実装がより簡潔だと思います.
実現する


public class BinaryTreeConstruction1 {
    //                     

    private static class BinaryTreeNode{
        //     
        int value;
        BinaryTreeNode leftNode;
        BinaryTreeNode rightNode;
    }

    public static BinaryTreeNode binaryTreeConstruct(int[] preorder, int[] inorder, int length){
        //       
        if (preorder == null || inorder == null || length <= 0 || preorder.length != inorder.length){
            throw new IllegalArgumentException("Invalid Input");
        }
        return construct(preorder, inorder,
                0, preorder.length - 1, 0, inorder.length - 1);
    }

    private static BinaryTreeNode construct(int[] preorder, int[] inorder, int startPre, int endPre,
                                     int startIn, int endIn){
        //                 
        BinaryTreeNode rootNode = new BinaryTreeNode();
        rootNode.value = preorder[startPre];
        rootNode.leftNode = null;
        rootNode.rightNode = null;

        //      
        if (startPre == endPre){
            if (startIn == endIn && preorder[startPre] == inorder[startIn])
                return rootNode;
            else
                throw new IllegalArgumentException("Invalid Input");
        }

        //              
        int rootInIndex = startIn;
        while(rootInIndex <= endIn && inorder[rootInIndex] != preorder[startPre])
            rootInIndex++;
        //      ，      
        if (rootInIndex == -1)
            throw new IllegalArgumentException("Invalid Input");
	
	//              ，         
        if (rootInIndex > startIn)
            rootNode.leftNode = construct(preorder, inorder,
                    startPre + 1, rootInIndex - startIn + startPre, startIn, rootInIndex - 1);
        if (rootInIndex < endIn)
            rootNode.rightNode = construct(preorder, inorder,
                    rootInIndex - startIn + startPre + 1, endPre, rootInIndex + 1, endIn);

        //  
        return rootNode;
    }

    private static void printPreorder(BinaryTreeNode rootNode){
        //              
        if (rootNode == null)
            return;
        System.out.printf("%d\t", rootNode.value);
        printPreorder(rootNode.leftNode);
        printPreorder(rootNode.rightNode);
    }

    private static void printInorder(BinaryTreeNode rootNode){
        //              
        if (rootNode == null)
            return;
        printInorder(rootNode.leftNode);
        System.out.printf("%d\t", rootNode.value);
        printInorder(rootNode.rightNode);
    }

    //    
    public static void main(String[] args){
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        BinaryTreeConstruction1 construction = new BinaryTreeConstruction1();
        printPreorder(BinaryTreeConstruction1.binaryTreeConstruct(pre, in, 8));
        System.out.println();
        printInorder(BinaryTreeConstruction1.binaryTreeConstruct(pre, in, 8));
    }
}

実現二


import java.util.Arrays;

public class BinaryTreeConstruction2 {
    //                     

    private static class BinaryTreeNode{
        int value;
        BinaryTreeNode leftNode;
        BinaryTreeNode rightNode;
    }

    public static BinaryTreeNode binaryTreeConstruct(int[] preorder, int[] inorder, int length){
        if (preorder == null || inorder == null || length <= 0)
            return null;
        if (preorder.length != inorder.length)
            throw new IllegalArgumentException("Invalid Input");

        return constructCore(preorder, inorder);
    }

    private static BinaryTreeNode constructCore(int[] preorder, int[] inorder){
        //               ，      ，             
        BinaryTreeNode rootNode = new BinaryTreeNode();
        rootNode.value = preorder[0];
        int length = preorder.length;

        //      
        if (length == 1) {
            if (preorder[0] == inorder[0])
                return rootNode;
            else
                throw new IllegalArgumentException("Invalid Input");
        }

        //              
        int rootIndex = -1;
        for (int i = 0; i < length; i++){
            if (preorder[0] == inorder[i])
                rootIndex = i;
        }
        //        
        if (rootIndex == -1)
            throw new IllegalArgumentException("Invalid Input");


        //           
        if (rootIndex > 0){
            //              
            int[] leftInorder = Arrays.copyOfRange(inorder,0, rootIndex);
            int[] leftPreorder = Arrays.copyOfRange(preorder, 1, rootIndex + 1);
            rootNode.leftNode = constructCore(leftPreorder, leftInorder);
        }
        if (length - rootIndex - 1 > 0){
            //              (          )
            int[] rightInorder = Arrays.copyOfRange(inorder, rootIndex + 1, length);
            int[] rightPreorder = Arrays.copyOfRange(preorder, rootIndex + 1, length);
            rootNode.rightNode = constructCore(rightPreorder, rightInorder);
        }
        return rootNode;
    }

    private static void printPreorder(BinaryTreeNode rootNode){
        if (rootNode == null)
            return;
        System.out.printf("%d\t", rootNode.value);
        printPreorder(rootNode.leftNode);
        printPreorder(rootNode.rightNode);
    }

    //    
    public static void main(String[] args){
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};

        printPreorder(BinaryTreeConstruction2.binaryTreeConstruct(pre, in, 8));
    }
}

JAvaトラップ3最後の笑い声

JAva awt印刷柱状図、線図