Examples of tree structures
在上一篇中,我们已经知道,具备nesting关系的结构都可以表示成tree structure,本文对计算机科学中的tree structure进行枚举。
Directory structure (directory)
目录是典型的可用使用tree来进行描述的,它满足nesting关系。
See also:
Process tree
parent-children关系。
File format
nesting关系。
2、json
3、yaml
Namespace
nesting关系。
Namespace的应用场景实在太多,在维基百科的Namespace对它总结地非常好。在对它进行思考的时候,发觉使用namespace来组织的数据最终就是hierarchy结构。其实也可以简单地将namespace看做是括号。
Expression
Source code
Parse tree、Abstract syntax tree。
nesting关系。
Activation tree
nesting关系。
函数的调用过程也是可以使用tree来进行描述的,参见:
1、Compilers Principles, Techniques and Tools Second Edition(aka dragon book) 的7.2.1 Activation Trees。
2、Function-recursion-tree-stack
章节
Recursion activation tree
递归函数的调用过程也是可以使用tree来进行描述的
Divide and conquer
Divide-and-conquer algorithm是典型的递归算法
Linguistics
在语言学中,基本上是使用tree来描述语言的结构。
If you have read book describing the compiler technology, for example the classic definitive book Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, you will be aware how important the tree structure is to the compiler. As described in chapter 2.2.3 Parse Trees:
Tree data structures figure prominently in compiling.
There are some many tree in the book, such as Parse tree, abstract syntax tree, activation tree(in chapter 7.2.1 Activation Trees), expression tree.
Essentially Speaking, a programming language is a formal language, what have been concluded in article structure is that
Tree can be used to describe the structure of sentences that is syntax and formal grammar can be convert to tree.
So it's natural to use trees in the compiling.
Regular expression, algebraic expression can be described using formal grammar, so given an expression, it can be converted to an equivalent parse tree.
Expression
Source code
Abstract syntax tree使用一棵树表达了源代码的语法结构
Nesting结构的一些例子
与nesting紧密相关的词有:
- enclosing(参见下面的enclosing function)、Closure (computer programming)
- block
Nested function and enclosing function
Counting problems can be solved using tree diagrams
在Discrete Mathematics and Its Applications的6.1 The Basics of Counting中使用tree diagram来描述**Counting problems**,这是一种典型的逻辑结构(并非肉眼可见的树结构)。