树数据结构的性质 [英] Nature of Tree Data Structure
问题描述
根据博客/书籍/ google等。
According to blogs/books/google etc.
树是一种模拟分层的数据结构>具有根
值和具有父节点的子节点的子树的树形结构，表示为
链接节点集
A tree is a data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes
完全可以，但是 hierarchical 一词使我感到困惑。树可以是分层结构又可以是线性结构吗？
考虑以下示例：
Which is completely fine, but the term hierarchical confuses me. Can tree be both Hierarchical and Linear?
Consider the following example:
Root
Left-Node
Left-Node
Left-Node
如果要遍历它从根到最后一个元素，然后：
If we want to traverse it to last element from root, then:
Root -> Left-Node -> Left-Node -> Left-Node
这不是线性结构吗（如链表）？
注意：我的问题并不是要说树不是分层的 ，而是树既是线性的（在某些情况下）又是分层的
你们能帮我解决我所理解的错误吗？
Doesn't that make a linear structure (like linkedlist)?
NOTE: My question doesn't mean to say that "Tree is not hierarchical" but "Tree is both Linear (In some cases) and Hierarchical"
Can you guys help me out with what I am understanding wrong?
推荐答案
由不分层的树数据结构实现的功能用途不大。例如，二叉搜索树，红黑树或AVL树中的每一个都具有该分层性质。
The functionality achieved by a tree data structure which is not hierarchical is not of great use. For example, the Binary search tree or Red black tree or AVL tree each of them are have that hierarchical nature.
在二进制搜索树中，当键单调递增或递减开始时从根开始，它归结为一个线性结构，无法为我们提供想要从树中获取的必要搜索功能。这就是我们选择AVL或RB树的原因。
In binary search tree when keys are monotonically increasing or decreasing starting from the root it boils down to a linear structure which is unable to provide us with the necessary searching capability that we want to obtain from tree. That's why we go for AVL or RB tree.
是的树可以是分层的也可以是线性的。倾斜的BST仍然是分层的（在
它们之间具有父子祖父母关系），但是在搜索时可以线性访问它们。希望这个
能够解释。
数据结构是如果元素形成序列或线性列表（例如数组，链接列表，队列等），则称其为线性。在这种情况下，当BST倾斜时，它基本上形成了一个链接列表，如线性结构。这就是为什么我的回答提到它是线性的。
A data structure is said to be linear if the elements form a sequence or a linear list, for example Array, Linked list, queue etc. Here in case of BST when skewed it forms basically a linked list like linear structure. That's why my answer mentioned it as linear.
不是线性结构（例如链表）？
Doesn't that make a linear structure (like linkedlist)?
是的，它是线性结构。
Yes it is a linear structure.
线性结构：搜索线性列表所需的时间与数据集的大小成正比。例如，如果数据集的大小为n（如果是倾斜的树），则查找（或不查找）某项所需的比较次数可能是n的倍数（这里只是一个遍历）。
Linear structures: the time required to search a linear list is proportional to the size of the data set. For example, if the size of the data set is n,(in case skewed tree) then the number of comparisons needed to find (or not find) an item may be multiple of n(here just one traversal).
树是非线性数据与线性数据结构的数组，链表，堆栈和队列相比。但是偏斜的特殊情况变成线性。与线性结构（如list）相比，这种非线性的偏差没有任何优势。
A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. But particular case of skewed-ness it becomes linear. That deviation from it's non-linearity gives it no advantage compared to linear structures like list.
精确：我们没有提到要进行分层，它必须是非线性的。有时线性数据结构也可以是分层的。
这篇关于树数据结构的性质的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
