在计算机科学中,树(英语:tree)是一种非线性的抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合
在上篇文章中,我们我们了解到数据结构的逻辑结构里面有两种分类,一种是线性的一对一数据结构,比如数组,链表,队列,栈等,这种线性数据结构的弊端在于要么单纯的查询快,要么单纯的的插入快,此外现实世界还存在很多的一对多的关系实体,比如家族的族谱,企业组织架构图,全国行政区域图等等,而树就是用来描述或者存储这些关系的结构。其可以使得读写操作的时间复杂度到降低到O(logn),是数据结构里面非常重要的一员。
树的一些特点:
每个节点都只有有限个子节点或无子节点; 没有父节点的节点称为根节点; 每一个非根节点有且只有一个父节点; 除了根节点外,每个子节点可以分为多个不相交的子树; 树里面没有环路(cycle)
节点的度:一个节点含有的子树的个数称为该节点的度;(A的度是2)
树的度:一棵树中,最大的节点的度称为树的度;(B的度是3)
叶节点或终端节点:度为零的节点;(K,J,F,L,O,P)
非终端节点或分支节点:度不为零的节点;(A,B,C,D,E,G,H,M,N)
父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;(A)
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;(A的子节点是B,C)
兄弟节点:具有相同父节点的节点互称为兄弟节点;(B,C)
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;(E为第三层)
深度和高度:(这两个比较容易混淆,看下面的一张图)
深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0;
高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;
堂兄弟节点:父节点在同一层的节点互为堂兄弟;(E,G)
节点的祖先:从根到该节点所经分支上的所有节点;(J的祖先,A,B,E)
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。(E的子孙为J)
森林:由m(m>=0)棵互不相交的树的集合称为森林;(B下面的子树和C下面的子树就是两个森林)
树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树,无序树在实际应用种意义不是很大。
树中任意节点的子节点之间有顺序关系,这种树称为有序树;有序树是编程领域里面的基础结构,大部分树的变形都是基于有序树演变而来。
有序树里面又分下面的几类:
每个节点最多含有两个子树的树称为二叉树;
二叉树又分下面几个类别:
(1)完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树; 其中完全二叉树又包括: 满二叉树:所有叶节点都在最底层的完全二叉树。
(2) 平衡二叉树:是一种结构平衡的二叉搜索树,即叶节点高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树
(3) 排序二叉树(二叉查找树(英语:Binary Search Tree)):也称二叉搜索树、有序二叉树;
带权路径最短的二叉树称为哈夫曼树或最优二叉树;
一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多于两个子树。
(1)基于数组的存储
顺序存储即用一个数组来存储一颗二叉树,具体存储方法为将二叉树中的结点进行编号,然后按编号依次将结点值存入到一个数组中,即完成了一颗二叉树的顺序存储。这种存储结构比较适合存储完全二叉树,用于存储一般的二叉树会浪费大量的存储空间,因为完全二叉树基本不会浪费数组空间,一般的二叉树如果节点分布不均,那么就会出现大量空间被浪费。
(1)基于链表的存储
顺序结构有一定的局限性,不便于存储任意形态的二叉树。通过二叉树的形态,可以发现一个根节点与两颗子树有关系,因此设计一个含有一个数据域和两个指针域的链式结点结构,data表示数据域,用于存储对应的数据元素;lchild和rchild分别表示左指针域和右指针域,分别用于存储左孩子结点和右孩子结点的位置,如果没有右孩子结点,则右指针为空。这种存储结构称为二叉链表存储结构。定义如下:
static class TreeNode<T>{ private int val; private T data;
private TreeNode leftChild; private TreeNode rightChild;
public TreeNode(int index, T data) { this.val = index; this.data = data; }
}
树是一种比较重要的数据结构,本文主要总结了数的基本定义,概念,分类及存储方式,掌握这些知识可以为后续研究学习有序树的内容做好扎实的铺垫。