英文:
Representation of Tree Data Structures
问题
I've studied that Data Structures can be classified into Linear (arrays, stacks, queues and linked-lists) and Non-Linear (trees and graphs) data structures.
Now, my question is that if linked-lists are "linear" data structures, then why are they used to implement trees, which are non-linear? Since trees have nodes that consist of the keys (or values) and pointers to more child nodes, aren't trees just more complex linked-lists?
If they are, then how is the statement "linked-lists are linear data structures" justified?
This is how I actually got this question:
I am currently learning data structures in C. So in order to implement the Tree data structure, I use structs, which consist of keys and pointers to the left and right children of each node.
英文:
I've studied that Data Structures can be classified into Linear (arrays, stacks, queues and linked-lists) and Non-Linear (trees and graphs) data structures.
flowchart of data structures -- image source: medium
Now, my question is that if linked-lists are "linear" data structures, then why are they used to implement trees, which are non-linear? Since trees have nodes that consist of the keys (or values) and pointers to more child nodes, aren't trees just more complex linked-lists?
If they are, then how is the statement "linked-lists are linear data structures" justified?
This is how I actually got this question:
I am currently learning data structures in C. So in order to implement the Tree data structure, I use structs, which consist of keys and pointers to the left and right children of each node.
typedef struct Node
{
int key;
struct Node *left;
struct Node *right;
} Node;
Then I wondered that I'm essentially implementing a linked-list (since linked-lists are also done using structs in C).
答案1
得分: 1
你混淆了不同的概念。
树是一种逻辑数据结构,是一个没有循环的有向图的特殊情况。
树数据结构可以以多种方式实现。一个数组可以存储子节点的索引,也可以使用实际的指向子节点内存的指针(就像你的示例中一样),还有其他方法。你的结构是树数据结构的一种特定实现,但还有其他实现方式。
"链表"通常指的是元素相互指向彼此内存的特定实现。有单向链表,元素指向下一个元素,还有双向链表,元素既指向前一个元素,又指向下一个元素。
如果你使用指针来实现树,而且每个节点只有一个子节点,那么这是一种特殊情况,其中实现类似于链表。
注意:链表可能会有循环,而树永远不会有循环,因为这样它就成为了图(根据定义)。而且,树节点通常不会指向其父节点,只会指向其子节点,而链表有时会指向父节点(前一个元素)。
因此,链表是一种称为"列表"的逻辑数据结构的实现。这种实现使用指针。
列表可以以其他方式实现(数组、直方图、带有每个元素出现次数计数器的哈希表、用于O(log(n))搜索的跳表等)。
树是一种逻辑数据结构,通常使用指针实现,但也有其他实现方式。
当使用指针实现树时,树中的每个分支都类似于一个链表 - 这就是你混淆的根源。
英文:
You are confusing different things.
A tree is logical data-structure which is a special case of a directed graph without cycles.
A tree data-structure can be implemented in various ways. An array which stores indices of children, using actual pointers to memory of children (like in your example), and other ways. your struct is a specific implementation of a tree data structure but there are other implementations.
A 'linked list' typically reffers to specific implementation where elements point to each others memory. There is a one directional linked list, where element points to next one, or bi-directional, where element points to previous and next one.
If you implement trees with pointers and each node has only one child, then this is a special case where the implementation resembles a linked list.
Note: that a linked list may have a loop, while a tree never has a loop, because then it becomes graph (by definition).
Also it is not common for a tree node to point back to its parent, only point to its children, while linked lists sometimes point to parent (previous element).
So linked list is an implementation of logical data structure which is called 'list'. This implementation uses pointers.
List can be implemented in other ways (arrays, histograms, hash tables with counters of amount of appearances of each elements, skip lists for O(log(n)) search etc).
A tree is a logical data structre which is commonly implemented using pointers, but has other implementations as well.
When tree is implemented using pointers, each 1 branch in a tree, resembles a linked list - so this is the sources of your confusion.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论