程序员人生 网站导航

数据结构中树的基本定义相关概念汇总

栏目:互联网时间:2014-10-08 08:00:00

定义

树的递归定义如下(个人比较喜欢的定义,源自百度百科):

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

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

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

相关术语(源自维基百科,有改动)

1、节点的度:一个节点含有的子树的个数称为该节点的度;
2、树的度:一棵树中所有节点的度的最大值称为树的度;
3、叶节点或终端节点:度为零的节点;
4、非终端节点或分支节点:度不为零的节点;

5、父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
6、孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
7、兄弟节点:具有相同父节点的节点互称为兄弟节点;

8、节点的层次:定义一棵树的根节点层次为1,其他节点的层次是其父节点层次加1;
9、树的高度或深度:一棵树中所有节点的层次的最大值称为这棵树的深度;

10、堂兄弟节点:父节点在同一层的节点互为堂兄弟;
11、节点的祖先:从根到该节点所经分支上的所有节点;
12、子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
13、森林:由m(m>=0)棵互不相交的树的集合称为森林;

需要说明下:节点=结点,都源自英文单词node。叶节点=叶子节点

种类

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

二叉树:每个节点最多含有两个子树的树称为二叉树;
二叉查找树(二叉排序树)
完全二叉树
满二叉树
平衡二叉树
霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树;

红黑树
B树

表示方法

最直观的是树形表示法


还有另一个常用的方法:先将根结点放入一对圆括号中,根结点后紧跟一对圆括号,然后把它的子树按从左至右的顺序放入该括号中,同层子树之间用逗号隔开。如前文树形表示法可以表示为:(1(2(4),3(5,6)))
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐