数据结构浅析(8)-树性结构：树和无序树
本系列文章
(1) 数据结构浅析(1)-什么是数据结构？
(2) 数据结构浅析(2)-集合
(3) 数据结构浅析(3)-线性结构：数组
(4) 数据结构浅析(4)-线性结构：线性表
(5) 数据结构浅析(5)-线性结构：串
(6) 数据结构浅析(6)-线性结构：栈
(7) 数据结构浅析(7)-线性结构：队列和双端队列
本文目标
试着理解什么是树形结构和树形结构中的无序树。
什么是树形结构
以下内容引自 维基百科树（数据结构）
在计算机科学中，树（tree）是一种抽象数据类型（Abstract Data Type, ADT）或是实际操作这种抽象数据，用来模拟具有树状结构性质的数据结合。它是由n (n>0) 个有限的节点组成一个具有层次关系的集合。至于为什么我们叫它“树”，是因为它看起来像一颗倒挂的树；也就是说它是根朝上，而叶朝下的。它具有以下的特点：
- 每个节点有零个或多个子节点
- 没有父节点的节点称为根节点
- 每一个非根节点有且只有一个父节点
- 除了根节点外，每个子节点可以分为多个不相交的子树
树的种类大范围可以分为无序树和有序树，有序树大范围可以分为二叉树和非二叉树。
树结构有关的术语
以下内容引用自 维基百科树（数据结构）
- 节点的度：一个节点含有的子树的个数称为该节点的度；
- 树的度：一棵树中，最大的节点的度称为树的度；
- 叶节点或终端节点：度为零的节点；
- 非终端节点或分支节点：度不为零的节点；
- 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
- 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
- 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
- 节点的祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林：由m（m>=0）棵互不相交的树的集合称为森林；
树的基本操作
构造树；清空树；判断树是否为空；获取树的深度；获取根节点；获取第i 个节点的值；改变节点的值；获取节点的父节点；获取节点左/右节点的值；输出树；向树中插入另一棵树；删除子树；遍历树。
什么是无序树
树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树。
看下图，引用自 Data-structure – Ordered Tree vs Unordered Tree
该树的根的所有左子代都小于根值而右子代的值大于根值，其中任意节点的子节点之间没有顺序关系。
这里作个简单的对比，下面两图表示了简单的有序树结构。
在上面A,B 两个有序树来说，树中任意节点的子节点之间有顺序关系。
一言以蔽之，兄弟节点有顺序的树，称为有序树，兄弟节点之间无顺序的树称为无序树。
无序树的特征
树中任意节点的子节点之间没有顺序关系；兄弟节点之间无顺序的树。
无序树的实现
下面列举了Java 语言中无序树的实现。
Java
代码引用自 How to create a simple unordered tree(not BST) in java with given node pairs(u,v)?
public class Node {
private String valueableData;
private Set<Node> children;
// 创建节点
public Node(){
this.children=new HashSet<Node>();
}
public Node (String valueableData){
this.valueableData=valueableData;
this.children=new HashSet<Node>();
}
// 增加子节点
public void addChild(Node node){
children.add(node);
}
}在下一篇文章中，将着重讲的是树形结构(2) - 有序树和二叉树。
如果你觉得我的文章有用，顺手点个赞，关注下我的专栏或则留下你的评论吧！
文章被以下专栏收录
