二進制樹的創建

我試圖從0和1的輸入創建一個二叉樹。例如，如果輸入是11010010，那麼輸出的樹將以1爲根。 2將是1的左邊孩子，4將是正確的孩子。 2將有一個正確的孩子，這將是3.這是樹的結束。由於樹以預定的順序遍歷，數字1-n（n是輸入中1的個數）被分配給被訪問的節點。 1表示根有孩子。例如，第一個1表示訪問根目錄並將1作爲根目錄。第二個意思是根有一個左邊的孩子，一個2放在那裏。之後的0意味着它沒有左邊的孩子。接下來的1意味着它有一個正確的孩子，而3被放置在那裏，等等。我對這棵樹如何被創建感到困惑。我知道在創建樹之後遍歷樹，但不知道如何通過遍歷它來創建樹。任何幫助，將不勝感激。二進制樹的創建

package tree; 

import java.io.*; 

public class BinaryTree<ArrayList> implements Serializable 
{ 
private static final long serialVersionUID = 1L; 

protected static class Node<ArrayList> implements Serializable 
{ 
    private static final long serialVersionUID = 1L; 

    protected int data; 
    protected Node<ArrayList> left; 
    protected Node<ArrayList> right; 

    public Node(int data) 
    { 
     this.data = data; 
     left = null; 
     right = null; 
    } 

    public boolean isLeft() 
    { 
     return (left == null); 
    } 
} 

protected Node<ArrayList> root;; 

public BinaryTree(int x) 
{ 
    Node<ArrayList> node = new Node<ArrayList>(x); 
    this.root = node; 
} 

public boolean isLeft() 
{ 
    return(root.left == null); 
} 

public void addLeft(int m, BinaryTree.Node<ArrayList> node) 
{ 
    root = new Node<ArrayList>(m); 
    node.left = root; 
} 

public void preorder(Node<ArrayList> temp) 
{ 
     if (temp!=null) 
     { 
      System.out.println(temp.data); 
      preorder(temp.left); 
      preorder(temp.right); 
     } 
     else 
      return; 
}

}

來源

2013-04-11 user2268305

您可以將其格式化爲更具可讀性。 – Jayamohan 2013-04-11 01:50:47

聽起來像作業 – Patashu 2013-04-11 01:56:41

@Jayamohan對不起，我不知道你的意思。格式化問題？ – user2268305 2013-04-11 01:56:58

聽起來好像你在默認情況下，廣度優先的方式構建一棵樹，基於斷的弦說什麼值分配到每個節點。

如果有幫助，首先將字符串轉換爲要放入節點的ArrayList<int>值 - 例如，11010010將變爲{1, 2, 4, 7}，即字符串中每個集合1的索引。

現在，我們必須構建樹 - 但我們總是會以完全相同的方式構造樹，因爲在深入之前完全填充淺層可以首先稱爲寬度。我們創建一個節點，然後告訴它「讓你的左節點，然後建立你的正確節點，然後告訴你的左節點這樣做，然後告訴你的正確節點這樣做」。（這與深度優先相反，在這種情況下，製作左節點，告訴左節點製作節點，然後製作正確的節點並告訴右節點製作節點）

因此，您需要遞歸方法像這樣的僞代碼：

void continueTree(ArrayList<int> numbers) 
{ 
    if (numbers.count() == 0) return; 
    this.left = new Node(numbers.get(0)); 
    numbers.remove(0); 
    if (numbers.count() == 0) return; 
    this.right = new Node(numbers.get(0)); 
    numbers.remove(0); 
    this.left.continueTree(numbers); 
    this.right.continueTree(numbers); 
}

來源

2013-04-11 02:02:04 Patashu

二進制樹的創建

回答

相關問題