Java解析二叉树结构

Question

我目前正在浏览一些数据结构，并且我遇到了一些存储在二叉树中的数据，我不完全确定解析它的最佳方式。

本质上，数据存储是这样的：

Structure 1: 
    LeftChild: 0xaddress 
    Structure 2: 
     LeftChild: 0xaddress 
     Structure 3: 
     LeftChild: 0xaddress 
      ........ 
     RightChild: 0xaddress 
      Structure 4: 
      LeftChild: 0xaddress 
      RightChild: 0xaddress 
     RightChild: 0xaddress 
    RightChild: 0xaddress 

现在很明显，这是相当难做到二叉树的文本说明，所以希望我可怜的企图上面解释这一点。实质上，它始于一个结构，它具有一个左侧和右侧的树入口，每个入口都有左侧和右侧，最终其中一个结点将耗尽节点，然后树的下一个分支继续进行。

我不完全确定解决这个问题的最佳方法。

我的第一个虽然是通过使用while循环来继续追逐树节点，但这似乎有点让人头痛的追踪。

我知道Java有二叉树的实现，但我不知道是否有可能将它们用于这类工作。我从来没有尝试过使用它们，所以我可能是错的。

如果有人对如何解决这个问题有什么意见或建议，我将不胜感激。

谢谢！

Answer 1

一个建议：如果你的树可以太深，你应该避免基于递归的解决方案。这是因为你可能有堆栈溢出问题。

要处理这种情况，您可以使用堆栈。

以下伪码遍历所有二叉树节点而不递归。

visitNodes(root) 
    add the root on the stack 

    while the stack is not empty 
     nodeToBeProcessed <- pop the top node from the stack 

     process nodeToBeProcessed 

     if nodeToBeProcessed has a left child 
      add the left child on the stack 

     if nodeToBeprocessed has a right child 
      add the right child on the stack 

注：pop操作返回和移除从堆栈的顶部节点。注2：如果深度不是问题，基于递归的解决方案通常更简单。

Answer 2

递归是传统的方式做它在某种伪代码形式：

Node { // data 
    Node leftChild; 
    Node rightChild; 
} 

handleNode(Node node) { 
    if (node is missing or null or blank) 
     return; 
    ... handle anything on the node 
    handleNode(node.leftChild); 
    handleNode(node.rightChild); 
} 

Answer 3

我不知道你究竟是如何实现的夜的东西，但试试这个（你需要做出一些明显的名称更改）：

//list to put all data into 
private static ArrayList<String> list = new ArrayList<String>(); 

//recursive way to search binary tree 
public void binaryTreeSearchAndParse(Node root) 
{ 
    //does it exist? 
    if(root != null) 
    { 
     list.add(root.getData()); 
     binaryTreeSearchAndParse(root.getLeft()); 
     binaryTreeSearchAndParse(root.getRight()); 
     //you may or may not need this depending on how you implemented your tree 
     //binaryTreeSearchAndParse(root.getNextStructure()); 
    }  
} 

public static void main(String[] args) 
{ 

    //get tree 
    //pass in root of tree 
    binaryTreeSearchAndParse(tree.getRoot()); 

    //now all data should be added in the global ArrayList 
    for(int i = 0; i<list.size(); i++) 
    { 
     System.out.println(list.get(i)); 
    } 
} 

我可以帮你更多，如果我知道你如何实现你的树。

这是一个递归解决方案。如果你想要一个迭代求解，你应该使用一个队列：

Binary search tree level order with parent node

Answer 4

如果我理解正确，你的问题是从这个格式的文件中读取信息，而不是一旦解析它就遍历树。您应该创建节点并跟踪谁是使用堆栈的人的兄弟，从而可以构建节点。

Stack<String> stack = new Stack<String>(); 
try { 
    BufferedReader in = new BufferedReader(new FileReader("yourfile.txt")); 
    String str; 
    while ((str = in.readLine()) != null) 
    { 

     if(str.contains("Structure")) 
     { 
      stack.push(str); 
     }else 
     { 
      if(str.contains("Left")) 
      { 
       stack.push(str); 
      } 
      if(str.contains("Right")) 
      { 
       System.out.println(stack.pop());  
       System.out.println(str); 
       System.out.println(stack.pop()); 
      } 
     } 
    } 
    in.close(); 
} catch (IOException e) { 
    e.printStackTrace(); 
} 

使用您的示例这段代码打印：

  LeftChild: 0xaddress 
     RightChild: 0xaddress 
     Structure 3: 
      LeftChild: 0xaddress 
      RightChild: 0xaddress 
      Structure 4: 
     LeftChild: 0xaddress 
     RightChild: 0xaddress 
    Structure 2: 
    LeftChild: 0xaddress 
    RightChild: 0xaddress 
Structure 1: 

，使用它可以建立节点。希望能帮助到你。