树，数据结构名词

定义

树树（tree）是包含n（nu003e=0）个结点的有穷集，其中：

树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

我们可以形式地给出树的递归定义如下:

单个结点是一棵树，树根就是该结点本身。

设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。

空集合也是树，称为空树。空树中没有结点。

相关术语

节点的度：一个节点含有的子树的个数称为该节点的度；

叶节点或终端节点：度为0的节点称为叶节点；

非终端节点或分支节点：度不为0的节点；

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

兄弟节点：具有相同父节点的节点互称为兄弟节点；

树的度：一棵树中，最大的节点的度称为树的度；

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；

堂兄弟节点：双亲在同一层的节点互为堂兄弟；

节点的祖先：从根到该节点所经分支上的所有节点；

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

森林：由m（mu003e=0）棵互不相交的树的集合称为森林；

种类

无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树，也称为自由树;

有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；

二叉树：每个节点最多含有两个子树的树称为二叉树；

完全二叉树

满二叉树

霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

深度

定义一棵树的根结点层次为1，其他节点的层次是其父结点层次加1。一棵树中所有结点的层次的最大值称为这棵树的深度。

表示方法

图像表达法

树的表示方法有很多种，最常用的是图像表示法。

以下是一个普通的树（非二叉树）：

树[数据结构名词]

符号表达法

用括号先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如前文树形表示法可以表示为：（1（2（5（9，10）），3（6，7），4（8）））

遍历表达法

树[数据结构名词]遍历表达法有3种方法：先序遍历、中序遍历、后序遍历

例如右图：

其先序遍历为ABDECF

其中序遍历为DBEAFC

其后序遍历为DEBFCA

具体请参照参考资料

其他

关于二叉树的其他知识请参照参考资料。

基本操作

设已有链队列类型LinkQueue的定义及基本操作（参见队列）。

构造空树

清空或销毁一个树也是同样的操作

构造树

判断树是否为空

获取树的深度

获取第i个节点的值

改变节点的值

获取节点的父节点

获取节点的最左孩子节点

获取节点的右兄弟节点

输出树

向树中插入另一棵树

删除子树

层序遍历树

存储结构