哪个是用C语言实现N-ary树的巧妙实现?
特别是,我想实现一个n-ary树,而不是自我平衡,每个节点中有一个未绑定数量的子节点,其中每个节点都包含一个已定义的结构,例如:
struct task { char command[MAX_LENGTH]; int required_time; };
Remo.D.. 54
任何n元树都可以表示为二叉树,其中每个节点中左指针指向第一个子节点,右指针指向下一个兄弟.
R R / | \ | B C D B -- C -- D / \ | | | E F G E -- F G
所以,你的情况是:
struct task { char command[MAX_LENGTH]; int required_time; }; struct node { struct task taskinfo; struct node *firstchild; struct node *nextsibling; };
该技术的优点在于许多算法更易于编写,因为它们可以在二叉树上表示,而不是在更复杂的数据结构上表达.
任何n元树都可以表示为二叉树,其中每个节点中左指针指向第一个子节点,右指针指向下一个兄弟.
R R / | \ | B C D B -- C -- D / \ | | | E F G E -- F G
所以,你的情况是:
struct task { char command[MAX_LENGTH]; int required_time; }; struct node { struct task taskinfo; struct node *firstchild; struct node *nextsibling; };
该技术的优点在于许多算法更易于编写,因为它们可以在二叉树上表示,而不是在更复杂的数据结构上表达.
作为第一遍,您可以简单地创建一个包含任务的结构(让我们称之为TreeNode),以及一组指向TreeNode的指针.该集可以是数组(如果N是固定的)或链表(如果N是可变的).链表要求您使用指向实际子节点(树的一部分)的TreeNode指针以及指向列表中下一个ListNode的指针来声明一个额外的结构(让我们称之为ListNode)(如果在结尾处,则为null)列表).
它可能看起来像这样:
struct task { char command[MAX_LENGTH]; int required_time; }; struct TreeNode; struct ListNode { struct TreeNode * child; struct ListNode * next; }; struct TreeNode { struct task myTask; struct ListNode myChildList; };