带你用Java方法轻松实现树的同构

树的同构

举例

带你用Java方法轻松实现树的同构_第1张图片

树的构造

树可以由数组或链表来构造:

举例:上图左上角的树通过数组可表示为

0 1 2 3 4 5 6 7 8 9 10 11 12
A B C D E G - - - F - H -

该方式浪费了部分空间,但适合表示完全二叉树

链表方式则比较直观

除上述两种方式外,还可以采用“类数组”的方式

 public static class Node{
        String data;
        int left;
        int right;
         }

举例:上图左上角的树可表示为

数组索引 data left right
0 A 1 2
1 B 3 4
2 C 6 -
3 D - -
4 E 5 -
5 F - -
6 G 7 -
7 H - -

本文的树结构使用了第三种方式

终端输入:

A,1,2
B,3,-
C,-,-
D,-,-
A,2,1
B,3,-
C,-,-
D,-,-
public class TongGou {
    private Scanner scanner;
    public TongGou(){
        scanner = new Scanner(System.in);
    }
    //树结构
    public static class Node{
        String data;
        int left;
        int right;
    }
    /**
     * 创建树
     * @param nodes
     * @return
     */
    public int createTree(Node[] nodes){
        int N = nodes.length;
        int root = -1;
        int[] check = new int[N];
        Arrays.fill(check,0);  //初始化为0
        for (int i=0;i0) {
                    check[left] = 1;
                }
                if(right>0){
                    check[right] = 1;
                }
            }
        }
        for(int i=0;i 
 

总结

本篇文章的内容就到这了,希望大家可以喜欢,也希望大家可以多多关注脚本之家的其他精彩内容!

你可能感兴趣的