完美平衡樹中元素的順序

我很難想象如何將我的程序插入元素。下面是老師給我們的代碼：完美平衡樹中元素的順序

int arr[] = { 3, -2, 11, 7, 12, 1, 4, 5, 33, 13 }; 
int n = 10; 
int cnt = 0; 

typedef struct node*po; 

struct node { 
    int data; 
    po left; 
    po right; 
}; 

po ibd(int n) { 
    po holder; 
    if (n>0) { 
     int nl = n/2; 
     int nr = n - nl - 1; 
     holder = new node; 
     holder->data = arr[cnt++]; 
     holder->left = ibd(nl); 
     holder->right = ibd(nr); 
     return holder; 
    } 
    else { 
     return NULL; 
    } 
}

我遺憾的是無法理解和想象它是如何使的元素在樹中。從我可以理解的它使用遞歸分而治之算法來將數組分成兩部分並添加元素，但是我無法理解哪個元素成爲根。有人可以幫助我想象一下，在插入所有東西后，樹會如何看待？

來源

2017-02-14 k.gerilovski

您應該使用調試器逐步完成代碼並查看它的功能。 – NathanOliver

你應該考慮在這個問題上使用c標籤，而不是C++標籤。 –

當老師的函數簽名是'po ibd（int n）'時，您擔心代碼將來的清晰度 – Drax

當樹木的工作，我喜歡畫一個節點是這樣的：

+--------------+---------------+ 
|   Data    | 
+--------------+---------------+ 
| Pointer to | Pointer to | 
| left subtree | right subtree | 
+--------------+---------------+

當我做一個節點一點到另一點，我用箭頭從適當left或right指針到新節點。這有助於我可視化樹。

有很多資源展示如何繪製樹木。

繪製樹後，添加新節點時按照箭頭。

來源

2017-02-14 15:30:51

是的，我可以理解，如何繪製樹木，但是我在這個確切的例子中遇到了麻煩。可以說我有數組：{3，-2，11，7，12，1，4，5，33，13}。該函數將數組分爲2：n/2和n - n/2 - 1。所以現在我有2個數組：{3，-2，11，7，12，1}和{4,5， 33，13}。但是，我不明白哪個元素成爲我的根。它是1（5h數組元素，因爲n/2 = 5），然後把其他的左邊和右邊，或者我出錯了？我真的明白，如果有人提請我這個現在的例子，它是如何工作的。 –

根據以下語句：'holder-> data = arr [cnt ++];'，您的根數據爲3，因爲'cnt'爲零且'arr [0] == 3'。 –

我建議搗毀函數並編寫你自己的Binary Tree構建器，這是你可以理解的。 –

完美平衡樹中元素的順序

回答

相關問題