设 G = (V,E) 是一个无向连通图，生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中，代价最小的生成树叫最小生成树。

哈夫曼树也称最优二叉树在实际中有着广泛的应用。下面有几个相关概念。

从树的孩子兄弟表示法和二叉树的二叉链表示法可以看出，树的孩子兄弟表示法实质上是二叉树的二叉链表存储形式，第一个孩子指针和有兄弟指针分别相当于二叉链表的左孩子指针和右孩子指针。所以从物理结构上看，树的右孩子兄弟表示法和二叉树的二叉链表是相同的，只是解释不同。如

由树的定义可知，树中的每个节点都有且仅有一个双亲结点。根据这一特性，可以用一维数组来存储树的各个结点（一般按照层序存储），数组中的一个元素对应树中的一个结点，数组元素包括树中结点的数据信息以及该结点的双亲在数组中的下标。有①双亲表示法和②带有兄弟的双亲表示法两种常用结构。

按照某种遍历次序对二叉树进行遍历，可以把二叉树中的所有结点排成一个线性序列。在具体应用中，有时需要访问二叉树中的结点在某种遍历序列中的前驱和后继，此时，在存储结构中应保存结点在某种遍历序列中的前驱和后继。这些指向前驱和后继结点的指针称为线索，加上线索的二叉树称为线索二叉树，相应地，加上线索的二叉链表叫做线索链表。线索链表结构如下：

所谓的查找实际上就是要确定关键码等于给定值的记录在查找结构中的存储位置。理想情况就是不经过任何比较，直接便能得到待查记录的存储位置，那就必须在记录的存储位置与它的关键码之间确立一个对应的关系H，使得每个关键码 key 和唯一的存储位置 H(key) 相对应。在查找时，根据这个确定的对应关系找到给定值 k 的映射 H(k) ，若集合中存在这个记录，则必定在 H(k) 位置上，这种查找技术叫做 散列技术。采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间叫做 散列表，将关键码映射为散列表中适当存储位置的函数称为 散列函数，所得的存储位置叫做 散列地址。

平衡二叉树是一棵空的二叉排序树，或者是具有下列性质的二叉排序树

​ 二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树