数据结构之（树）

前言

在计算机科学中，树（英语：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下面的子树就是两个森林）

数的种类

无序树

树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树，无序树在实际应用种意义不是很大。

有序树

树中任意节点的子节点之间有顺序关系，这种树称为有序树；有序树是编程领域里面的基础结构，大部分树的变形都是基于有序树演变而来。

有序树里面又分下面的几类：

（A）二叉树：

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

二叉树又分下面几个类别：

（1）完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树； 其中完全二叉树又包括： 满二叉树：所有叶节点都在最底层的完全二叉树。

(2) 平衡二叉树：是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

(3) 排序二叉树(二叉查找树（英语：Binary Search Tree))：也称二叉搜索树、有序二叉树；

（B）霍夫曼树：

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

（C） B树：

一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。

数的存储方式

（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;        }
    }

总结

树是一种比较重要的数据结构，本文主要总结了数的基本定义，概念，分类及存储方式，掌握这些知识可以为后续研究学习有序树的内容做好扎实的铺垫。