定义与构成
树(tree)是包含n(n≥0)个节点,当n=0时,称为空树,非空树中条边的有穷集,在非空树中:
(1)每个元素称为节点(node)。
(2)有一个特定的节点被称为根节点或树根(root)。
(3)除根节点之外的其余数据元素被分为个互不相交的集合,其中每一个集合本身也是一棵树,被称作原树的子树(subtree)。
树也可以这样定义:树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点,所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位,这个节点称为该树的根节点,或称为树根。
我们可以形式地给出树的递归定义如下:
单个节点是一棵树,树根就是该节点本身。
设是树,它们的根节点分别为。用一个新节点作为的父亲,则得到一棵新树,节点n就是新树的根。我们称为一组兄弟节点,它们都是节点的子节点。我们还称为节点n的子树。
空集合也是树,称为空树。空树中没有节点;
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
节点的度:一个节点含有的子节点的个数称为该节点的度;
叶节点或终端节点:度为0的节点称为叶节点;
非终端节点或分支节点:度不为0的节点;
双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
兄弟节点:具有相同父节点的节点互称为兄弟节点;
树的度:一棵树中,最大的节点的度称为树的度;
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
树的高度或深度:树中节点的最大层次;
堂兄弟节点:双亲在同一层的节点互为堂兄弟;
节点的祖先:从根到该节点所经分支上的所有节点;
子孙:以某节点为根的子树中任一节点都称为该节点的子孙;
森林:由棵互不相交的树的集合称为森林。
种类
无序树:树中任意节点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树;
有序树:树中任意节点的子结点之间有顺序关系,这种树称为有序树;
二叉树:每个节点最多含有两个子树的树称为二叉树;
满二叉树:叶节点除外的所有节点均含有两个子树的树被称为满二叉树;
完全二叉树:除最后一层外,所有层都是满节点,且最后一层缺右边连续节点的二叉树称为完全二叉树;
哈夫曼树(最优二叉树):带权路径最短的二叉树称为哈夫曼树或最优二叉树。
深度
定义一棵树的根结点层次为1,其他结点的层次是其父结点层次加1。一棵树中所有结点的层次的最大值称为这棵树的深度。
表示方法
图像表达法
树的表示方法有很多种,最常用的是图像表示法。
以下是一个普通的树(非二叉树):
符号表达法
用括号先将根结点放入一对圆括号中,然后把它的子树由左至右的顺序放入括号中,而对子树也采用同样的方法处理;同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。如前文树形表示法可以表示为:
遍历表达法
遍历表达法有4种方法:先序遍历、中序遍历、后序遍历、层次遍历
例如右图:
其先序遍历(又称先根遍历)为ABDECF(根-左-右)
其中序遍历(又称中根遍历)为DBEAFC(左-根-右)(仅二叉树有中序遍历)
其后序遍历(又称后根遍历)为DEBFCA(左-右-根)
其层次遍历为ABCDEF(同广度优先搜索)