从数组中生成二叉树

问题描述 投票:0回答:1

我需要从值数组中制成一棵二叉树。我有一个类似LinkedList的TreeNode类(TreeNode引用了左右数据)。 TreeNode嵌套在另一个类中。我不确定下一步该怎么做。

import java.util*;

public class Try{


//////////////////////////////////////////////////////////////

public class TreeNode{
    public int data;
    public TreeNode left;
    public TreeNode right;

    // constructor 1
    public TreeNode(int data) {
        this(data, null, null);
    }

    // constructor 2
    public TreeNode(int data, TreeNode left, TreeNode right) 
   {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}
//////////////////////////////////////////////////////////////////


}

我真的不知道下一步该怎么做。我在Try类中嵌套了TreeNode类。为了创建一个二叉树,我知道我要用构造函数创建很多TreeNode对象。但是,如何从Try类连续创建TreeNode对象?

我知道我最终将遍历数组,然后将值分配给left或right。嵌套类确实令人困惑。

我如何使用递归?我是Java新手,将不胜感激!

谢谢。

java recursion binary-tree
1个回答
0
投票

您可以在Try类中使用TreeNode类。这段代码将从列表中创建一个二叉树:

import java.util.*;

public class Try {


    //////////////////////////////////////////////////////////////

    public class TreeNode {
        public int data;
        public TreeNode left;
        public TreeNode right;

        // constructor 1
        public TreeNode(int data) {
            this(data, null, null);
        }

        // constructor 2
        public TreeNode(int data, TreeNode left, TreeNode right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        private void inner_print(int tabs) {
            for (int i = 0; i < tabs; i++) {
                System.out.print("\t");
            }
            System.out.println(data);
            if (left != null) left.inner_print(tabs + 1);
            if (right != null) right.inner_print(tabs + 1);
        }

        public void print() {
            inner_print(0);
        }
    }
    //////////////////////////////////////////////////////////////////

    private TreeNode inner_createTree(int[] values, int i) {
        if (i >= values.length) return null;
        return new TreeNode(values[i],
            inner_createTree(values, i * 2 + 1),
            inner_createTree(values, i * 2 + 2));
    }

    public TreeNode createTree(int[] values) {
        return inner_createTree(values, 0);
    }

    public static void main(String[] args) {
        int[] lst = new int[] {
            0,
            1,
            2,
            3,
            4,
            5,
            6,
            7,
            8,
            9
        };
        Try tryInstance = new Try();
        TreeNode root = tryInstance.createTree(lst);
        root.print();
    }

}

输出:

0
    1
        3
            7
            8
        4
            9
    2
        5
        6

检查此link以查看其工作原理:)

© www.soinside.com 2019 - 2024. All rights reserved.