首页 > 代码库 > 树论讲解(1)——树基础

树论讲解(1)——树基础

树是什么东西??

这个??                      还是这个??

技术分享                技术分享

 

很显然身为一名c++选手,所说的树显然不是这个树了!!

有人不禁要问,那树是什么东西呢???

好,下面我们就来讲讲树的基本概念

one.树的定义

所谓树状图是一数据结构。它由n果然有限接点组成的就有一定层次关系的集合,把它叫做树,是因为它看起来像一棵倒挂的树。也就是说它是根朝上,而叶朝下的。它具有以下的特点:每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树;

树(tree)是包含n(n>0)个结点的有穷集,其中:

(1)每个元素称为结点(node);

(2)有一个特定的结点被称为根结点或树根(root)。

(3)除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1,T2,……Tm-1,其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树(subtree)。

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

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

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

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

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

two。相关概念

节点的度:一个节点含有的子树的个数称为该节点的度;

叶节点或终端节点:度为0的节点称为叶节点;

非终端节点或分支节点:度不为0的节点;

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;

兄弟节点:具有相同父节点的节点互称为兄弟节点;

树的度:一棵树中,最大的节点的度称为树的度;

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度:树中节点的最大层次;

堂兄弟节点:双亲在同一层的节点互为堂兄弟;

节点的祖先:从根到该节点所经分支上的所有节点;

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

森林:由m(m&gt;=0)棵互不相交的树的集合称为森林;

three。种类

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

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

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

完全二叉树

满二叉树

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

four。表示方法

符号表达法

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

遍历表达法

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

five。树的储存方法

1.父亲表示法

只记录每个孩子父亲的信息,时间复杂度小,但难以遍历整棵树

2.孩子表示法

用邻接表记录每个节点所以孩子的信息,可以方便的遍历整棵树,但无法求出每个节点父亲的信息。

3.父亲孩子表示法

结合上述两种方法,同时记录一个节点孩子和他的父亲的信息,这是我们经常使用的一种方法。

4.孩子兄弟表示法

记录一个节点的孩子和他右侧的兄弟,可以说是强制转换成二叉树

 

树论讲解(1)——树基础