返回 登录
1

疯狂java笔记之树和二叉树

树的概述
树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构

1.树的定义和基本术语

计算机世界里的树,是从自然界中实际的树抽象而来的,它指的是N个有父子关系的节点的有限集合。对于这个有限的节点集合而言,它满足如下条件:

当N=0时,改节点集合为空,这课树也被称为空树
在任意的非空树中,有且仅有一个根(root)节点
当N>1时,除根节点以外的其余节点可分为M个互为相交的有限集合T1,T2,…,Tm,其中的每个集合本身又是一棵树,并称其为根的子树(subtree)。
从上面定义可以发现树的递归特性:一棵树由根和若干棵子树组成,而每棵子树又由若干棵更小的子树组成。

树中任一节点可以有0或多个子节点,但只能有一个父节点。根节点是一个特例,根节点没有父节点,叶子节点没有子节点。树中每个节点既可以是其上一级节点的子节点,也可以是下一级节点的父节点,因此同一个节点既可以是父节点,也可以是子节点(类似于一个人—————他既是他儿子的父亲,又是他父亲的儿子)。

很显然,父子关系是一种非线性关系,所以树结构是非线性结构。

如果按节点是否包含子节点来分,节点可以分成以下两种:

普通节点:包含子节点的节点
叶子节点:没有子节点的节点,因此叶子节点不可作为父节点
如果按节点是否具有唯一的父节点来分,节点有可分为如下两种:

根节点:没有父节点的节点,根节点不可作为子节点
普通节点:具有唯一父节点的节点
一棵树只能有一个根节点,如果一棵树有了多个根节点,那么它已经不再是一棵树了,而是多棵树的集合,有时也被称为森林。示意图如下:

tree.PNG
tree.PNG
与树有关的术语有如下一些:

节点:树的最基本组成单元,通常包括一个数据元素及若干指针用于指向其他节点。
节点的度:节点拥有的子树的个数被称为节点的度(degree)
树的度:树中所有节点的度的最大值就是该树的度
叶子节点:度为0的节点被称为叶子节点或终端节点
分支节点:度不为0的节点被称为分支节点或非终端节点
子节点,父节点,兄弟节点:节点的子树的根被称为该节点的子节点,而该节点称为子节点的父节点(parent).具有相同父节点的子节点之间互称为兄弟节点。
节点的层次(level):节点的层次从根开始算起,根的层次值为1,其余节点的层次值为父节点层次值加l。
树的深度(depth):树中节点的最大层次值称为树的深度或高度。
有序树与无序树:如果将树中节点的各棵子树看成从左到右是有序的(即不能互换),则称该树为有序树,否则称为无序树。
祖先节点(ancestor):从根到该节点所经分支上的所有节点
后代节点(descendant):以某节点为根的子树中任一节点都称为该节点的后代节点。
森林(forest):森林是;两颗或两颗以上互不相交的树的集合,删去一棵树的根,就得到一个森林。
树的基本操作

如果需要实现一棵树,程序不仅要以合适的方式保存该树的所有节点,还要记录节点与节点之间的父子关系。接下来,还应该为树实现如下基本操作。

初始化:通常是一个构造器,用于创建一棵空树,或者以指定节点为根来创建树。
为指定节点添加子节点
判断树是否为空
返回根节点
返回指定节点(非根节点)的父节点
返回指定节点(非叶子节点)的所有子节点
返回指定节点(非叶子节点)的第i个子节点
返回该树的深度
返回指定节点的位置
为了实现树这种数据结构,程序必须能记录节点与节点之间的父子关系,为此有一下两种选择:
父节点表示法:每个子节点都记录它的父节点。
子节点链表示法:每个非叶子节点通过一个链表来记录它所有的子节点。
父节点表示法

通过前面的介绍可以发现,树中除根节点之外的每个节点都有一个父节点。为了记录树中节点与节点之间的父子关系,可以为每个节点增加一个parent域,用以记录该节点的父节点。用如下图和如下表来表示

tree_show.PNG
tree_show.PNG
数组索引 data parent
0 A -1
1 B 0
2 C 0
3 D 0
4 E 1
5 F 3
6 G 3
7 H 4
8 I 4
9 J 4
10 K 6
… … …
由此可见,只要用一个节点数组来保存树里的每个节点,并让每个节点记录其父节点在数组中的索引即可。

子节点链表表示法

父节点表示法的思想是让每个节点“记住”它的父节点的索引,父节点表示法是从子节点着手的;反过来,还有另外一种方式:让父节点“记住”它的所有子节点口在这种方式下,由于每个父节点需要记住多个子节点,因此必须采用“子节点链”表示法。示意图如下:

tree_linked.PNG
tree_linked.PNG
二叉树
二叉树的定义和基本概念

二叉树指的是每个节点最多只能有两个子树的有序树。通常左边的子树被称作“左子树”(left subtree),右边的子树被称为“右子树”(right subtree).由此可见,二叉树依然是树,它是一种特殊的树。
二叉树的每个节点最多只有来两颗树(不存在度大于2的节点),二叉树的子树有左,右之分,次序不能颠倒。
树和二叉树的两个重要区别如下:

树中节点的最大度数没有限制,而二叉树节点的最大度数为2,也就是说,二叉树是节点的最大度数为2的树。
无序树的节点无左右之分,而二叉树的节点有左,右之分,也就是说,二叉树是有序树。
一棵深度为k的二叉树,如果它包含了

2^k-1
个节点,就把这棵二叉树称为满二叉树。满二叉树的特点是。每一层上的节点数都是最大节点数,即各层节点数分别为1,2,4,8, 16,…,满二叉树下图所示:

two_tree.PNG
two_tree.PNG
一颗有n个节点的二叉树,按满二叉树的编号方式对它进行编号,若树中所有节点和满二叉树1~n编号完全一致,则称该树为完全二叉树。也就是说,如果一颗二叉树除最后一层外,其余层的所有节点都是满的,并且最后一层或者是满的,或者仅在右边缺少若干连续的节点,则此二叉树就是完全二叉树。

综上所述,二叉树大致有如下几个性质:

二叉树第i层上的节点数据至多为2的i-1次方
深度为k的二叉树至多有2的k次方-1个节点.满二叉树的每层节点的数量依次为1, 2, 4,8,…,因此深度为k的满二叉树包含的节点数为公比为2的等比数列的前k项总和,
即2的k次方一1。
在任何一棵二叉树中,如果其叶子节点的数量为n0,度为2的子节点数量为n2,则
n0=n2 + 1。这是因为:如果为任意叶子节点增加一个子节点,则原有叶子节点变成非叶子节点,新增节点变成叶子节点,上述等式不变;如果为任意叶子节点增加两个子节点,则原有叶子节点变成度为2的非叶子lto点,新增的两个节点变成叶子节点,上述等式依然不变。
具有n个节点的完全二叉树的深度为log2(n+1)
对于一颗具有n个节点的完全二叉树的节点按层自左向右编号,则对任一编号为i(n>=i>=1)的节点有下列性质。

当i==1时,节点i是二叉树的根;若i>1,则节点的父节点是i/2
若2i

评论