BST：使用排序順序打印樹的另一個關鍵

我有我的二叉樹用C未來結構代碼：BST：使用排序順序打印樹的另一個關鍵

struct student 
{ 
    int studentID; 
    char lastName[MAX_LENGTH]; 
    char firstName[MAX_LENGTH]; 
    float amount; 
}; 

struct node 
{ 
    struct student* record; 
    struct node* left; 
    struct node* right; 
};

記錄插入到使用studentID領域作爲重點的樹。當我按照studentID的順序打印樹時一切正常。但是我想按照lastName字段的順序打印SAME樹。

我只有一個想法：複製樹到數組，排序數組和顯示數組。

是否有其他解決方案？

來源

2013-12-09 pydevd

您應該嘗試插入基於lastName的記錄，然後您可以按照學生的姓氏字段進行按序遍歷。 – vishram0709

排序爲指針數組（struct student *）。 – BLUEPIXY

另一種方法是創建一個額外的字段'struct node * equal;'並在那裏放置所有相等的記錄。然後，您可以簡單地創建一個額外的樹，使用'lastName'作爲您的密鑰並遍歷樹來獲取排序列表。畢竟，您可以在數據結構中使用多個密鑰。 – Devolus

您可以構建和維護多個並行的二叉搜索樹，可選擇摺疊成一個單一的多索引的數據結構：

struct node { 
    struct student *record; 
    struct node *left_by_id, *right_by_id, 
       *left_by_name, *right_by_name; 
};

顯然，所有的BST操作必須修改這個工作：例如要插入新的struct student*，您必須將單個node綁定到兩棵樹上。

來源

2013-12-09 10:50:49

這是傷害和漫長，但我已經做到了:)謝謝 – pydevd

爲lastName創建一個索引。您可以使用另一個將存儲lastName作爲關鍵字的BST以及指向您原始BST中對應節點的指針。

struct indexNode { 
    char lastName[MAX_LENGTH] 
    struct node* originalNode; 
};

您可以在將數據插入原始樹的同時繼續插入此樹。

這種方式你將不得不花費O(log n)空間來存儲額外的索引樹，但會減少你搜索lastname到O(log n)的時間。此外，實際上，您將僅存儲每個元素的鍵和指向節點的指針。

來源

2013-12-09 10:56:33 Sangram

BST：使用排序順序打印樹的另一個關鍵

回答

相關問題