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：使用排序顺序打印树的另一个关键

回答

相关问题