计算机软件基础：13第四章数据结构树.doc

在计算机科学中，数据结构是组织和管理数据的重要工具，而树是一种非常基础且重要的数据结构。本节主要介绍了树的基本概念、特性、操作以及存储形式。 树是一种非线性的数据结构，由若干个节点（或称为顶点）通过特定的关系（称为边）连接而成。在树的定义中，每个节点有零个或多个子节点，且有一个特殊的节点称为根节点，没有前驱；除了根节点外，其他每个节点都有且仅有一个父节点，也就是它的前驱。这种结构可以用来模拟现实世界中的许多层次关系，如文件系统、家族关系等。 树的图形表示通常采用自上而下的方式，其中根节点在顶部，子节点在下方，通过连线表示父子关系。例如，给定的示例树T = k1+{T1 + T2 + T3}，其中k1是根节点，T1、T2和T3是子树，每个子树又有自己的子节点。 树的特性包括： 1. 除根节点外，每个节点有且仅有一个父节点。 2. 父节点及其以上的节点称为父辈节点，子节点及其以下的节点称为子辈节点。 3. 没有子节点的节点称为叶节点，有子节点的非根节点称为内节点。 4. 根据最大子节点数，树可以被分类为n次树，如T1是四次树。 5. 如果所有节点的子节点数要么为0，要么为n，那么它是n次完全树，如T2是二次完全树。 6. 若对每个节点的子树顺序有定义，那么树是有序的。 树的基本操作包括查找、遍历、添加、删除、构造和排序。查找是指寻找特定节点或其父节点、子节点；遍历是指按某种方式访问所有节点；添加和删除涉及在树中插入或移除节点；构造是根据特定规则生成树；排序则是按照特定顺序排列节点。 在存储树时，有几种常见的方法： 1. 标准形式：每个节点有m个指针字段，指向其子节点，如示例中的三次树。 2. 逆形式：每个节点有一个指针字段，指向其父节点。 3. 扩充标准形式：结合了标准形式和逆形式，既有指向父节点的指针，也有指向子节点的指针。 在实际编程中，存储树的节点和指针字段可以通过一维数组、二维数组、动态数组、多指针或链表实现。例如，对于n个节点的三次树，可以定义一个一维数组来存储节点数据，然后为每个节点分配m+1个指针字段，分别用于父节点和子节点的引用。 树数据结构是理解和处理复杂数据关系的基础，广泛应用于各种算法和软件系统中，如搜索算法、数据库索引、编译器语法分析等。掌握树的基本概念和操作对于深入学习计算机科学至关重要。