数据结构：树（tree）

本文概述

• 基本术语
• 树的静态表示
• 树的动态表示
• 树的类型
• 普通树
• 森林
• 二叉树
• 二进制搜索树
• 表达树
• 比赛树

• 树是一种递归数据结构, 包含一个或多个数据节点的集合, 其中一个节点被指定为树的根, 而其余节点被称为根的子级。
• 除根节点以外的其他节点均被划分为多个非空集, 每个非空集都称为子树。
• 树的节点或者在它们之间保持父子关系, 或者它们是姐妹节点。
• 在一般树中, 一个节点可以有任意数量的子节点, 但只能有一个父节点。
• 下图显示了一棵树, 其中节点A是树的根节点, 而其他节点可以视为A的子节点。

基本术语

• 根节点：-根节点是树层次结构中的最高节点。换句话说, 根节点是没有任何父节点的节点。
• 子树：-如果根节点不为空, 则树T1, T2和T3被称为根节点的子树。
• 叶子节点：-没有任何子节点的树的节点称为叶子节点。叶节点是树的最底部节点。普通树中可以有任意数量的叶节点。叶节点也可以称为外部节点。
• 路径：-连续边的顺序称为路径。在上图所示的树中, 到节点E的路径为A→B→E。
• 祖先节点：-节点的祖先是从根到该节点的路径上的任何前任节点。根节点没有任何祖先。在上图所示的树中, 节点F具有祖先B和A。
• 程度：-节点的程度等于一个节点具有的子代数。在上图所示的树中, 节点B的度为2。叶节点的度始终为0, 而​​在完整的二叉树中, 每个节点的度均等于2。
• 等级号：-树的每个节点被分配一个等级号, 使得每个节点比其父级高一个等级。树的根节点始终位于级别0。

树的静态表示

#define MAXNODE 500
struct treenode {
	int root;
	int father;
	int son;
	int next; 
}

树的动态表示

struct treenode 
{
	int root;
	struct treenode *father; 
	struct treenode *son 
	struct treenode *next; 
}

树的类型

树数据结构可以分为六个不同的类别。

普通树

通用树按层次结构顺序存储元素, 其中顶级元素始终作为根元素出现在级别0中。除根节点外, 所有节点都以一定数量的级别存在。存在于相同级别上的节点称为同级, 而存在于不同级别上的节点则表现出它们之间的父子关系。一个节点可以包含任意数量的子树。每个节点包含3个子树的树称为三叉树。

森林

森林可以定义为一组不相交的树, 可以通过删除根节点和将根节点连接到第一级节点的边获得。

二叉树

二叉树是一种数据结构, 其中每个节点最多可以有2个子节点。最顶层的节点称为根节点。子节点为0的节点称为叶节点。二叉树用于表达式评估等应用程序中。在本教程的后面, 我们将详细讨论二叉树。

二进制搜索树

二进制搜索树是有序的二进制树。左子树中的所有元素均小于根元素, 而右子树中的所有元素均大于或等于根节点元素。二进制搜索树用于计算机科学领域的大多数应用程序中, 例如搜索, 排序等。

表达树

表达式树用于评估简单的算术表达式。表达式树基本上是一个二叉树, 其中内部节点由运算符表示, 而叶节点由操作数表示。表达式树被广泛用于求解代数表达式, 例如（a + b）*（a-b）。考虑以下示例。

问：使用以下代数表达式构造一个表达式树。

（a + b）/（a * b-c）+ d

比赛树

比赛树用于记录两名球员之间每一轮比赛的胜者。锦标赛树也可以称为选择树或获胜者树。外部节点代表正在进行比赛的玩家, 而内部节点代表进行比赛的获胜者。在最高级别, 锦标赛的获胜者是树的根节点。

例如, 如下所示在四个玩家之间进行的国际象棋比赛的树。但是, 左子树的获胜者将与右子树的获胜者对战。