將樹遍歷到一個數組中

我應該遍歷一個Binary Seach Tree作爲預訂，按順序和後序排列，並將這些值插入到Java中的Object []中。我真的不知道如何做到這一點，我需要一些建議。將樹遍歷到一個數組中

我的功能：

public Object[] traversePreOrder()

所有我需要的基本上都是如何完成這個任務的一些想法或提示。如果我作爲預先遍歷一棵樹Object [0]顯然是根的值。然後我繼續在左邊的樹中，並在我的數組中插入最左邊的值。接下來我插入最左側節點的右側子節點，如果右側節點沒有子節點，則繼續使用兩個節點的父節點。

但我的方法不記得哪些值已被檢查和插入。我也想過在後序遍歷中，將每個元素放到堆棧上，並將每個元素推送到我的數組上，但是我對如何實現這一點的知識存在限制。

幫助！

下面是在我看來已經是正確的：

@Override 
public Object[] traversePreOrder() { 
    Object[] preOrderArray = new Object[elements]; 
    if (elements == 0) { 
     return preOrderArray; 
    } 



    return preOrderArray; 

}

的差距已經被明顯地填補。

此外，我有基本方法和構造：

BinarySearchTreeNode(T value, BinarySearchTreeNode<T> left, 
     BinarySearchTreeNode<T> right) { 
    this.value = value; 
    this.left = left; 
    this.right = right; 
} 

BinarySearchTreeNode(T value) { 
    this(value, null, null); 
} 

BinarySearchTreeNode<T> getLeft() { 
    return left; 
} 

void setLeft(BinarySearchTreeNode<T> left) { 
    this.left = left; 
} 

BinarySearchTreeNode<T> getRight() { 
    return right; 
} 

void setRight(BinarySearchTreeNode<T> right) { 
    this.right = right; 
} 

T getValue() { 
    return value; 
} 

void setValue(T value) { 
    this.value = value; 
}

來源

2013-05-29 Pulz

使用隊列，然後將其轉換爲數組。 –

這是一項家庭作業http://meta.stackexchange.com/questions/10811/how-to-ask-and-answer-homework-questions/10812#10812 – crush

這是一個非強制性的任務。我正在爲我的考試做好準備。 – Pulz

使用遞歸的理想情況。創建方法

List<BinarySearchTreeNode> traverse(BinarySearchTreeNode n) { 
    // traversal code 
}

在遍歷代碼遍歷左子和右子，如果有的話，

爲序遍歷，串接值，左孩子的成績和右子的結果;
中序遍歷，連接左孩子的結果，值和右孩子的結果;
用於後序遍歷，連接左側孩子的結果，右側孩子的結果和值。

調用traverse作爲根，並將結果轉換爲Object[]。

來源

2013-05-29 17:05:23 Arend

非常感謝。我會嘗試一下。 – Pulz

你可以有這種遞歸方法的返回類型是List嗎？似乎每次它被稱爲它將試圖返回一個單獨的列表？也許我在看這個錯誤... – sage88

確定它會每次都會返回一個單獨的列表 - 只需將它們合併到您自己的列表中即可。你的解決方案也能正常工作，事實上，由於你並沒有複製清單，所以事實上可以更快地記錄n因子，但是你依賴於遞歸函數的副作用，這是一個不太明顯的理由。 – Arend

正如Arend上面提到的，這是一般的想法。我不確定是否每次都可以讓它返回一個列表，但是您可能可以。然而，如果這個實現不起作用，你可以嘗試這樣的事情，看看其他東西是否正常工作：

private List nodeValues = new ArrayList(); 

public void traversePreRecursive(BinarySearchTreeNode node) 
{ 
    if (node != null) 
    { 
     nodeValues.add(node.getValue()); 
     traversePreRecursive(node.getLeft()); 
     traversePreRecursive(node.getRight()); 
    } 
}

來源

2013-05-29 17:34:12 sage88

將樹遍歷到一個數組中

回答

相關問題