大话数据结构-树

1 概述
树(Tree)是n(n >= 0)个结点的有限集 。n = 0时称为空树 。在任意一棵非空树中:
(1) 有且仅有一个特定的称为根(root)的结点;
(2) 当n > 1时 , 其余结点可分为m(m > 0)个互不相交的有限集T1、T2、…、Tm , 其中每一个集合本身又是一棵树 , 并且称为根的子树() 。
2 结点分类
树的结点包含一个数据元素及若干指向其子树的分支 。结点拥有的子树数称为结点的度() 。度为0的结点称为叶结点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点 。除根结点之外 , 分支结点也称为内部结点 。树的度是树内各结点的度的最大值 。
3 结点间关系
结点的子树的根称为该结点的孩子(Child) , 相应地 , 该结点称为孩子的双亲() 。同一个双亲的孩子之间互称兄弟() , 结点的祖先是从根到该结点所经分支上的所有结点 。以某结点为根的子树中的任一结点都称为该结点的子孙 。
4 树的其他相关概念
结点的层次(Level)从根开始定义起 , 根为第一层 , 根的孩子为第二层 。其双亲在同一层的结点互为堂兄弟 。树中结点的最大层次称为树的深度(Depth)或高度 。
如果将树中结点的各子树看成从左至右是有次序的 , 不能互换的 , 则称该树为有序树 , 否则称为无序树 。森林()是m(m >= 0)棵互不相交的树的集合 。对树中每个结点而言 , 其子树的集合即为森林 。
5 抽象数据类型
6 树的存储结构
首先 , 需要知道 , 在一棵树中 , 每个结点都是有编号的 , 从第一层开始依次从左向右、从上向下 , 从0开始计算编号 , 如下图所示:
6.1 双亲表示法
在结点中定义一个指针 , 指向其(双亲)结点的存储结构 , 称为双亲表示法 。
/*** 双亲表示法结点** @author Korbin* @date 2023-01-18 11:11:13**/@Datapublic class ParentTreeNode {/*** 数据元素**/private T data;/*** 双亲指针**/private int parent;}
没有双亲的结点 , 即根结点 , 其双亲指针指向-1 。
双亲表示法中 , 树结构会定义结点数组 , 以及根结点位置、总结点数等信息:
/*** 树的双亲表示法** @author Korbin* @date 2023-01-18 10:21:28**/public class ParentTree {/*** 结点**/private ParentTreeNode nodes;/*** 最大结点数量**/private int maxSize;/*** 根结点指针**/private int root;/*** 结点数量**/private int length;}
对于如下一棵树 , 按照双亲表示法 , 可得到其data和信息:
下标
0
A
-1
1
【大话数据结构-树】B
0
2
C
0
3
D
1
4
E
1
5
F
2
6
G
2
7
H
2
8
I
5
9
J
6
10
K
7
这样的存储结构 , 我们可以根据结点的指针很容易找到它的双亲结点 , 所用的时间复杂度为O(1) , 直到为-1时 , 表示找到了树结点的根 。
可如果我们要知道结点的孩子是什么 , 那就只能遍历树了 。这种情况下 , 可以考虑增加一个域 , 表示最左边的孩子位置 , 也叫长子域 , 对于没有孩子的结点 , 这个长子域就设置为-1 , 那么树的结点信息就变成了:
下标
0
A
-1