package week6.jsjf;

import week4.jsjf.ArrayUnorderedList;
import week4.jsjf.UnorderedListADT;

public class BTCreation {
    public static void main(String[] args) {
        String[]a={"H","D","I","B","E","M","J","N","A","F","C","K","G","L"};
        String[]b={"A","B","D","H","I","E","J","M","N","C","F","G","K","L"};
        BTCreation ab=new BTCreation(a,b);
        ab.ab=ab.Creation(b, a, 0, b.length-1, 0, a.length-1);
        System.out.println( ab.toString());

    }
    String [] preorder;String[]inorder;
    BinaryTreeNode ab;

    public BTCreation(String[] preorder,String[]inorder){

        this.preorder=preorder;
        this.inorder=inorder;
    }
    public  BinaryTreeNode Creation(String[] preorder, String[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
        BinaryTreeNode tree = new BinaryTreeNode(preorder[preStart]);
        tree.left = null;
        tree.right = null;
        if (preStart == preEnd && inStart == inEnd) {
            return tree;
        }
        int root = 0;
        for(root= inStart; root < inEnd; root++){
            if (preorder[preStart] == inorder[root]) {
                break;
            }
        }
        int leifLength = root - inStart;
        int rightLength = inEnd - root;
        if (leifLength > 0) {
            tree.left = Creation(preorder, inorder, preStart+1, preStart+leifLength, inStart, root-1);
        }
        if (rightLength > 0) {
            tree.right = Creation(preorder, inorder, preStart+1+leifLength, preEnd, root+1, inEnd);
        }
        return tree;
    }

    @Override
    public String toString()
    {
        UnorderedListADT<BinaryTreeNode> nodes = new ArrayUnorderedList<BinaryTreeNode>();
        UnorderedListADT<Integer> levelList = new ArrayUnorderedList<Integer>();
        BinaryTreeNode current;
        String result = "";
        int printDepth = this.height(this.ab);
        int possibleNodes = (int)Math.pow(2, printDepth + 1);
        int countNodes = 0;

        nodes.addToRear(this.ab);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.addToRear(currentLevel);

        while (countNodes < possibleNodes)
        {
            countNodes = countNodes + 1;
            current = nodes.removeFirst();
            currentLevel = levelList.removeFirst();
            if (currentLevel > previousLevel)
            {
                result = result + "\n\n";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                    result = result + " ";
            }
            else
            {
                for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++)
                {
                    result = result + " ";
                }
            }
            if (current != null)
            {
                result = result + (current.getElement()).toString();
                nodes.addToRear(current.getLeft());
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(current.getRight());
                levelList.addToRear(currentLevel + 1);
            }
            else {
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                result = result + " ";
            }
        }
        return result;
    }

    public  int height(BinaryTreeNode node)
    {
        if (node==null)
            return 0;

        int leftlength=height(node.getLeft());
        int rightlength=height(node.getRight());

        return  leftlength> rightlength ? leftlength + 1 : rightlength + 1;

    }


}