Java怎么生成树形结构数据

101次阅读

共计 1904 个字符，预计需要花费 5 分钟才能阅读完成。

Java 中生成树形结构数据可以使用多种方法，下面列举了两种常用的方法：

方法一：使用递归实现

class TreeNode {int val;
    List<TreeNode> children;

    public TreeNode(int val) {this.val = val;
        this.children = new ArrayList<>();}
}

public class TreeGenerator {public static TreeNode generateTree(int[] nums, int rootIndex) {if (rootIndex >= nums.length) {return null;
        }
        
        TreeNode root = new TreeNode(nums[rootIndex]);
        
        int leftChildIndex = 2 * rootIndex + 1;
        int rightChildIndex = 2 * rootIndex + 2;
        
        root.children.add(generateTree(nums, leftChildIndex));
        root.children.add(generateTree(nums, rightChildIndex));
        
        return root;
    }
    
    public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5, 6, 7};
        
        TreeNode root = generateTree(nums, 0);
        
        // 打印树的结构 
        printTree(root, 0);
    }
    
    public static void printTree(TreeNode root, int level) {if (root == null) {return;
        }
        
        for (int i = 0; i < level; i++) {System.out.print("\t");
        }
        
        System.out.println(root.val);
        
        for (TreeNode child : root.children) {printTree(child, level + 1);
        }
    }
}

方法二：使用队列实现

class TreeNode {int val;
    List<TreeNode> children;

    public TreeNode(int val) {this.val = val;
        this.children = new ArrayList<>();}
}

public class TreeGenerator {public static TreeNode generateTree(int[] nums) {if (nums.length == 0) {return null;
        }
        
        TreeNode root = new TreeNode(nums[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        int index = 1;
        while (!queue.isEmpty() && index < nums.length) {TreeNode currNode = queue.poll();
            
            // 左孩子 
            if (index < nums.length) {TreeNode leftChild = new TreeNode(nums[index++]);
                currNode.children.add(leftChild);
                queue.offer(leftChild);
            }
            
            // 右孩子 
            if (index < nums.length) {TreeNode rightChild = new TreeNode(nums[index++]);
                currNode.children.add(rightChild);
                queue.offer(rightChild);
            }
        }
        
        return root;
    }
    
    public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5, 6, 7};
        
        TreeNode root = generateTree(nums);
        
        // 打印树的结构 
        printTree(root, 0);
    }
    
    public static void printTree(TreeNode root, int level) {if (root == null) {return;
        }
        
        for (int i = 0; i < level; i++) {System.out.print("\t");
        }
        
        System.out.println(root.val);
        
        for (TreeNode child : root.children) {printTree(child, level + 1);
        }
    }
}