如何将二叉搜索树存储到 two-d 数组中并在 Java 中打印出来？

Question

我已经创建了一个二叉搜索树，但我不知道如何将它放入 two-d 数组（我对递归方式和 non-recursion 方式都感兴趣）并打印它出。

如下图

           7
         /   \
        5     9
       / \   / \
      4   6 8  15
      .
      .
      .

抱歉表达含糊。基本上我是想 1) 从文件中读取数字序列并为它们构建二叉搜索树。

2) 我需要将树绘制成字符数组（必须是二维数组）来表示绘图区域。所以树根一定在数组第一行的中间，第一个左child一定在第二行一半的中间，第一个右child 必须在第二行另一半的中间。等等。

如下图

------------34------------

-----24------------56-----

---9-----32-----41----57--

3) 最后我需要打印出来（作为第一张图）。

我有 BinaryNode.class BinaryTree.class 并且在树里面 class, root有几个基本方法getmethod和setmethod，左child和右child.

这是我在主 class 上的部分代码：

BinaryTree BinarySearchTree = new BinaryTree();

 FileReader theFile;

 BufferedReader inFile;

 String oneLine;

 try{

   theFile = new FileReader(args[0]);

   inFile = new BufferedReader(theFile);

   while((oneLine = inFile.readLine())!= null){

    String[] list = oneLine.split(",");

    for(int i=0; i<list.length; i++){                           

      BinaryNode TreeNode = new BinaryNode(list[i]);

      BinaryTree.insert(BinarySearchTree, TreeNode.element);

      }

      }

      }

      catch (Exception e) {

           System.out.println(e);

          }


    // building binary search tree

    public static BinaryTree insert(BinaryTree t, Object x){

      if(t.isEmpty())

      return new BinaryTree(x);

      else{

          if(((Integer)t.getRootobj()).intValue()<((Integer)x).intValue())

            t.setRight(insert(t.getRight(),x));

          else

            t.setLeft(insert(t.getLeft(),x));

            return t;

         }

Answer 1

您可以使用节点的值作为第一个数组中的索引，并将 children 的值存储在第二个数组中。您可以将左 child 的值作为索引 0，将右 child 的值与索引 1 放在一起。要标记没有左或右 child 您可以使用负值或零。要知道初始根元素，您可以搜索具有至少一个元素的数组的第一个元素，或者您可以想办法将根元素存储在某处。绝对不是最佳选择，但应该有效。

示例如下：

[0] -> {0,0}
[1] -> {2,3}
[2] -> {4,5}
[3] -> {6,7}
[4] -> {0,0}

Answer 2

由于二叉树是Graph数据结构的特例，您可以查看现有的Graph表示，例如邻接表或邻接矩阵。

这些链接可能会有帮助：

Graph representation in Java
http://www.quora.com/What-is-the-best-way-to-represent-a-Graph-in-Java

Answer 3

您可以将二叉树存储在一维数组中。

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

结果数组A为A = [1, 2, 3, 4, 5, 6, 7]

节点i的左边child由2*i + 1给出，右边child由2*i + 2给出，第一个节点是0索引。

示例：第 3 个节点的左和右 child（索引：2） left child : 2*i + 1 = 2*2+1 = 5, A[5] = 6, 正确！对 child : 2*i + 2 = 2*2 + 2 = 6, A[6] = 7, 也正确!

所以给定这个 "algorithm" 你可以构建一个 Java class 来秘密处理一维数组中的树！

如何将二叉搜索树存储到 two-d 数组中并在 Java 中打印出来？

How to store a binary search tree into a two-d array and print it out, in Java?

java

arrays

binary-tree