基於數組的二叉樹預先訂購

任何人如何將基於數組的樹轉換爲按訂單？該數組包含：基於數組的二叉樹預先訂購

乾杯

public void preOrder(int index) { 

    if (index >= currSize) { 
     return; 
    } 

    System.out.println(items[index]); 
    preOrder(2^index + 1); //left 
    preOrder((2^index) + 2); //right 
}

來源

2012-02-04 Raju Kumar

7的父母是什麼？請添加更多信息。它是否像第n個孩子的孩子在2 ** n和2 **（n + 1）位置的堆？（假設索引從1開始） – MAK 2012-02-04 07:17:02

7是一個葉子，它是一個完整的二叉樹。 – 2012-02-04 07:18:42

這是家庭工作嗎？ – 2012-02-04 07:19:36

應該像下面這樣。

public void preOrder(int index) { 

    if (index >= currSize) { 
     return; 
    } 
    System.out.println(items[index]); 
    preOrder((2 * index)+1); 
    preOrder((2 * index)+2); 
}

來源

2012-02-04 11:50:03 Harminder

爲了前序遍歷，你先處理父，那麼你遞歸處理左子樹和右子樹。您擁有的表示與堆中的表示基本相同，因此很清楚任何節點的左側和右側的子節點是什麼。這意味着我們可以按照預先的順序遍歷它，並按照訪問它們的順序打印出節點。

僞代碼將如下所示：

print_pre_order(index): 
    if index is beyond the size of the array: 
    return 
    else: 
    print value at index 
    print_pre_order(left child of index) 
    print_pre_order(right child of index)

由於此佈置爲堆，對於每個索引n的左子是在2 * n和右子是在2 *（N +1）。請注意，我假設數組的索引從1開始（儘管大多數語言都從0開始），但是您可以輕鬆地將其適用於基於0的數組。

來源

2012-02-04 07:33:02 MAK

邏輯是正確的，但似乎沒有打印任何東西 – 2012-02-04 07:47:25

我已經發布了我在主帖中提出的方法。 – 2012-02-04 07:48:54

@jonny：'^'是Java中的異或運算符，而不是冪運算。將'2^n'替換爲'1 << n'（向左移n，與2 ** n相同）。 – MAK 2012-02-04 10:05:25

基於數組的二叉樹預先訂購

回答

相關問題