本文概述
- 基本术语
- 树的静态表示
- 树的动态表示
- 树的类型
- 普通树
- 森林
- 二叉树
- 二进制搜索树
- 表达树
- 比赛树
- 树是一种递归数据结构, 包含一个或多个数据节点的集合, 其中一个节点被指定为树的根, 而其余节点被称为根的子级。
- 除根节点以外的其他节点均被划分为多个非空集, 每个非空集都称为子树。
- 树的节点或者在它们之间保持父子关系, 或者它们是姐妹节点。
- 在一般树中, 一个节点可以有任意数量的子节点, 但只能有一个父节点。
- 下图显示了一棵树, 其中节点A是树的根节点, 而其他节点可以视为A的子节点。
文章图片
基本术语
- 根节点：-根节点是树层次结构中的最高节点。换句话说, 根节点是没有任何父节点的节点。
- 子树：-如果根节点不为空, 则树T1, T2和T3被称为根节点的子树。
- 叶子节点：-没有任何子节点的树的节点称为叶子节点。叶节点是树的最底部节点。普通树中可以有任意数量的叶节点。叶节点也可以称为外部节点。
- 路径：-连续边的顺序称为路径。在上图所示的树中, 到节点E的路径为A→B→E。
- 祖先节点：-节点的祖先是从根到该节点的路径上的任何前任节点。根节点没有任何祖先。在上图所示的树中, 节点F具有祖先B和A。
- 程度：-节点的程度等于一个节点具有的子代数。在上图所示的树中, 节点B的度为2。叶节点的度始终为0, 而??在完整的二叉树中, 每个节点的度均等于2。
- 等级号：-树的每个节点被分配一个等级号, 使得每个节点比其父级高一个等级。树的根节点始终位于级别0。
#define MAXNODE 500struct treenode { int root;
int father;
int son;
int next;
}树的动态表示
struct treenode { int root;
struct treenode *father;
struct treenode *son struct treenode *next;
}树的类型 树数据结构可以分为六个不同的类别。
文章图片
普通树 通用树按层次结构顺序存储元素, 其中顶级元素始终作为根元素出现在级别0中。除根节点外, 所有节点都以一定数量的级别存在。存在于相同级别上的节点称为同级, 而存在于不同级别上的节点则表现出它们之间的父子关系。一个节点可以包含任意数量的子树。每个节点包含3个子树的树称为三叉树。
森林 【数据结构（树（tree））】森林可以定义为一组不相交的树, 可以通过删除根节点和将根节点连接到第一级节点的边获得。
文章图片
二叉树 二叉树是一种数据结构, 其中每个节点最多可以有2个子节点。最顶层的节点称为根节点。子节点为0的节点称为叶节点。二叉树用于表达式评估等应用程序中。在本教程的后面, 我们将详细讨论二叉树。
二进制搜索树 二进制搜索树是有序的二进制树。左子树中的所有元素均小于根元素, 而右子树中的所有元素均大于或等于根节点元素。二进制搜索树用于计算机科学领域的大多数应用程序中, 例如搜索, 排序等。
表达树 表达式树用于评估简单的算术表达式。表达式树基本上是一个二叉树, 其中内部节点由运算符表示, 而叶节点由操作数表示。表达式树被广泛用于求解代数表达式, 例如（a + b）*（a-b）。考虑以下示例。
问：使用以下代数表达式构造一个表达式树。
（a + b）/（a * b-c）+ d
文章图片
比赛树 比赛树用于记录两名球员之间每一轮比赛的胜者。锦标赛树也可以称为选择树或获胜者树。外部节点代表正在进行比赛的玩家, 而内部节点代表进行比赛的获胜者。在最高级别, 锦标赛的获胜者是树的根节点。
例如, 如下所示在四个玩家之间进行的国际象棋比赛的树。但是, 左子树的获胜者将与右子树的获胜者对战。
文章图片
