Complete Binary Search Tree

PAT-1064

本次因为涉及到完全二叉排序树，所以可以使用数组的形式来存储二叉排序树
对输入序列排序后，得到的是中序遍历二叉排序树的序列。对这颗二叉排序树进行中序遍历，将每个结点的值放入二叉树的存储数组中，最后遍历数组即可求出层次遍历的序列。
此题需要注意层次遍历和数组存储二叉树的关系，利用这个关系可以快速解题。

/**

 * @Author WaleGarrett

 * @Date 2020/9/5 8:20

 */

import java.util.Arrays;

import java.util.Scanner;

/**

 * PAT-1043,1064,1066,1086,1089,1099,1098

 * 7

 * 8 6 5 7 10 8 11

 */

public class PAT_1064 {

    static final int maxn=1003;

    static int[] node;

    static int[] tree;//存储二叉树

    static int N;

    static int position=0;

    static void inOrder(int root){

        if(root>N)

            return;

        inOrder(root<<1);

        tree[root]=node[position++];

        inOrder(root<<1|1);

    }

    public static void main(String[] args) {

        Scanner scanner=new Scanner(System.in);

        int n=scanner.nextInt();

        N=n;

        node=new int[n];

        tree=new int[n+1];

        int i=0;

        while(n!=0){

            node[i]=scanner.nextInt();

            i++;

            n--;

        }

        Arrays.sort(node);

        inOrder(1);

        for(i=1;i<N;i++){

            System.out.print(tree[i]+" ");

        }

        System.out.println(tree[N]);

    }

}

巴特西

PAT-1064（Complete Binary Search Tree）JAVA实现

Complete Binary Search Tree

PAT-1064

最新文章

热门文章