Skip to content

Examples of tree structures

在上一篇中,我们已经知道,具备nesting关系的结构都可以表示成tree structure,本文对计算机科学中的tree structure进行枚举。

Directory structure (directory)

目录是典型的可用使用tree来进行描述的,它满足nesting关系。

See also:

Tree (command)

Path (computing)

Process tree

parent-children关系。

File format

nesting关系。

1、Document Object ModelXML

2、json

3、yaml

Namespace

nesting关系。

Namespace的应用场景实在太多,在维基百科的Namespace对它总结地非常好。在对它进行思考的时候,发觉使用namespace来组织的数据最终就是hierarchy结构。其实也可以简单地将namespace看做是括号。

Expression

binary expression tree

Source code

Parse treeAbstract 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

binary expression tree

Source code

Abstract syntax tree使用一棵树表达了源代码的语法结构

Nesting结构的一些例子

Nested function

Scope (computer science)

与nesting紧密相关的词有:

Nested function and enclosing function

Counting problems can be solved using tree diagrams

Discrete Mathematics and Its Applications6.1 The Basics of Counting中使用tree diagram来描述**Counting problems**,这是一种典型的逻辑结构(并非肉眼可见的树结构)。