树结构
树结构
tree
树结构(tree)由n(n异0)个结点的有限集 合所构成的一种数据结构。当n~。时称为空树，非空 树递归定义如下:①有且仅有一个称为根的结点;②其 余结点可分为二(。)0)个互不相交的子集，其中每 一个子集本身又是一棵树，称为根的子树。树结构在客 观世界中广泛存在，也是程序设计中各种信息的重要 组织~一。 树中的结点包含一个数据元素及若于指向其子树 的分支。结点拥有的子树数(分支数)称为该结点的度， 用石表示。度为o的结点称为叶或终端结点;度不为O 的结点称为分支结点或非终端结点。树中各结点的度 的最大值称为树的度。树是一种层次结构，结点的层次 从根开始定义，根为第一层，若某结点在第艺层，则其 子树的根为第i+1层。树中结点的最大层次称为树的 深度或高度。若树中各结点的子树之间在逻辑上存在 顺序关系的，则称该树为有序树;否则，称为无序树。 在计算机中，通常采用多链式存储结构来表示树 结构。对树的操作有:①检索树中的结点;②遍历树中 各结点，即按某种规则巡访树中每个结点，使得每个结 点被访问一次且仅访问一次;③添加子树;④删除子树 等。 在程序设计中较广泛使用的树结构有: (1)二叉树:度k毛2的有序树。二叉树与一般树 (度龙>2的k叉树)之间存在一种一一对应的转换算 法。在通常采用的用同构(等长)的多链式存储结构表 示的树吟二叉树的密度最高·因此，二叉树除了本身 有着广泛的用途外，还可以用作一般树的存储结构。 (2)霍夫曼(Huffman)树:带权路径长度最短的 二叉树。带权路径长度是从根到树中所有带权叶子之 间的路径长度与树的乘积之和。根据给定的一组权值， 构造一棵相应的Huffman树的算法，称为Huffman算 法。Huf如an树有着广泛的应用，如在解决某些判定问 题时，利用Huffman树可以得到最佳的判定算法;在 快速远距离通信中，可以得到编码长度最短的编码。