下载掌阅APP，畅读海量书库
立即打开
树是一种重要的非线性结构，它用于描述数据元素之间的层次关系。每一棵树必有一个特定的节点，称作根（root）节点。根节点之下可以有子节点，也可以没有。而各子节点也可为子树，拥有自己的子节点。
图4.1中，节点A为树T的根节点，B、C、D、M则为节点A的子节点。若节点包含其下拥有的所有子节点，则节点和所有子节点均为T的子树。例如B是A的子节点，P、Q皆是B的子节点，而B、P、Q为树T的子树。
图4.1
若一棵树中的节点最多可以有 n 个子节点，则称这样的树为 n 元树。例如二叉树中的节点，最多只能有两个子节点。
树的表示方法除树形表示法外，还有文氏图表示法、括号表示法和凹入表示法等，如图4.2所示。
图4.2
（1）树形表示法：这是树的最基本表示方法，用一棵倒置的树表示树结构，非常直观和形象。
（2）文氏图表示法：使用集合和集合的包含关系描述树结构。
（3）括号表示法：将树的根节点写在括号的左边，除根节点之外的节点写在括号中并用逗号隔开来描述树结构。
（4）凹入表示法：使用伸缩的线段描述树结构。