快好知 kuaihz订阅看过栏目

 

树状图是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外,每个子结点可以分为多个不相交的子树;

定义

树(tree)是包含n(n>=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(m>=0)棵互不相交的树的集合称为森林;

种类

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

有序树:树中任意节点的子结点之间有顺序关系,这种树称为有序树;

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

完全二叉树

满二叉树

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

深度

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

表示方法

图像表达法

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

一下是一个普通的树(非二叉树):

符号表达法

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

遍历表达法

遍历表达法有3种方法:先序遍历、中序遍历、后序遍历

例如右图:

其先序遍历为ABDECF

其中序遍历为DBEAFC

其后序遍历为DEBFCA

具体请参照参考资料

其他

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

父节点表示法

存储结构

基本操作

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

构造空树

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

构造树

判断树是否为空

获取树的深度

获取第i个节点的值

改变节点的值

获取节点的父节点

获取节点的最左孩子节点

获取节点的右兄弟节点

输出树

向树中插入另一棵树

删除子树

层序遍历树

孩子链表表示法

存储结构

投稿
非常不爽,删了吧! 相关词条:文化 语言文字 专业术语