# DataStructure

**Repository Path**: caonanqing/DataStructure

## Basic Information

- **Project Name**: DataStructure
- **Description**: 数据结构和算法，线性表，图+查找+排序，栈队列和二叉树
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-03-16
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# DataStructure数据结构与算法
数据结构和算法，线性表，图+查找+排序，栈队列和二叉树等测试案例

## **数据结构基本概念：**
    数据（Data）：是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
        例如：数值数据，字符，声音，图像等，切能输入计算机并能被处理的都是数据。
    数据项（Data Item）：具有原子性，是不可分割的最小数据单位。
        例如：描述学生相关信息的姓名，性别，学号等。
    数据元素（Data Element）：是数据的基本单位，是数据集合的个体，通常由若干个数据项组成一个整体来进行处理。
        例如：一条描述一位学生的完整信息的数据记录就是一个数据元素。
    数据对象（Data Object）：是性质相同的数据元素的集合，是数据的子集。
        例如：一个学校的所有学生的集合就是数据对象。
    数据结构（Data Structure）：是指相互之间存在一种或多种特定关系的数据元素的集合。
        是组织并存储数据以便能够有效使用的一种专门格式，它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。
        由于信息可以存在于逻辑思维领域，也可以存在于计算机世界，因此作为信息载体的数据同样存在于两个世界。
        表示一组数据元素及其相互关系的数据结构同样也有两种不同的表现形式。
        一种是数据结构的逻辑层面，即数据的逻辑结构。
        一种是存在于计算机世界的无聊层面，即数据的存储结构。
        数据结构=逻辑结构+存储结构
        数据结构=逻辑结构+存储结构+（在存储结构上的）运算/操作。
    数据结构的三个方面：
        1.数据的逻辑结构：
            a.线性结构：线性表，栈，队列，串及数组。
            b.非线性结构：树形结构，图形结构。
        2.数据的存储结构：顺序存储，链式存储，索引存储，散列存储。
        3.数据的运算：检索，排序，插入，删除，修改等。
        
##**数据的逻辑结构**        
    数据的逻辑结构：数据的逻辑结构指数据元素的逻辑关系。（与实现无关）
    分类一：线性结构和非线性结构
        线性结构：有且只有一个开始结点和终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。
            线性表就是一个典型的线性结构，它有四个基本结构：
                1.集合中必存在唯一的一个“第一个元素”。
                2.集合中必存在唯一的一个“最后的元素”。
                3.除最后元素之外，其它数据元素均有唯一的“后继”。
                4.除第一元素之外，其它数据元素均有唯一的“前驱”。
        非线性结构：是一个结点元素可能对应多个直接前驱和多个直接后继。
    分类二：集合结构、线性结构、树状结构、网络结构
        集合结构：就是数学中的集合。集合中的元素有三个特征：
            1.确定性（集合中的元素必须是确定的）。
            2.唯一性（集合中的元素互不相同。例如：集合A={1,a},则a不能等于1）
            3.无序性（集合中的元素没有先后之分），如集合{3,4,5}和{3,5,4}算作同一个集合。
            该结构的数据元素间的关系是“属于同一个集合”，别无其它关系。因为集合中元素关系很弱，数据结构中不对该结构进行研究。
        线性结构：数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。
        树状结构：除了一个数据元素（元素01）以外每个数据元素有且仅有一个直接前驱元素，但是可以有多个后继元素。特点是数据元素之间是一对多关系。
        网络结构：每个数据元素可以有多个直接前驱元素，也可以有多个直接后继元素。特点是数据元素之间是多对多关系。
    
##**数据的存储结构**    
    数据的存储结构：主要包括数据元素本身的存储以及数据元素之间关系表示，是数据的逻辑结构在计算机中的表示。
    常见的存储结构有：顺序存储，链式存储，索引存储，以及散列存储。
    顺序存储结构：把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。
        优点：
            1.节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数据需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。
            2.采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。
        缺点：
            1.插入和删除操作需要移动元素，效率较低。
            2.必须提前分配固定数量的空间，如果存储元素少，可能导致空间浪费。
    链式存储结构：数据元素的存储对应的是不连续的存储空间，每个存储节点对应一个需要存储的数据元素。每个结点是由数据域和指针域组成。元素之间的逻辑关系通过存储节点之间的链接关系反映出来。逻辑上相邻的节点物理上不必相邻。
        优点：
            1.插入，删除灵活（不必移动节点，只要改变节点中的指针）。
            2.有元素才会分配结点空间，不会有闲置的结点。
        缺点：
            1.比顺序存储结构的存储密度小（每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
            2.查找结点时链式存储要比顺序存储慢。
    索引存储结构：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
        比如：图书、字典的目录。
    散列存储结构：根据结点的关键字直接计算出该结点的存储地址HashSet，HashMap这种神奇的结构，添加、查询速度快。
    
    线性表逻辑结构对应的顺序存储结构为顺序表，对应的链式存储结构为链表。

    同一逻辑结构可以对应多种存储结构。
    同样的运算，在不用的存储结构中，其实现过程是不同的。


##**算法**
    算法（algorithm）是指令的集合，是为解决特定问题而规定的一系列操作。
        是明确定义的可计算过程，以一个数据集合作为输入，并产生一个数据集合作为输出。
    算法特性：
        1.输入：一个算法应以待解决的问题的信息作为输入。
        2.输出：输入对应指令集处理后得到的信息。
        3.可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成。
        4.有穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成的。因此整个算法也是在有限时间内可以结束的。
        5.确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始，多次执行同一指令集结果总是相同的。
    简单的说，算法就是计算机解题的过程。
    该过程中，无论形成解题思路还是编写程序，都是在实施某种算法。前者是算法逻辑形式，后者是算法的代码形式。
    举例：如何求0+1+2+3+...+10000=?
        算法1：依次相加 while do, while, for 
        算法2：高斯解法：首尾相加*50 ，  （1+10000）*10000/2  ，   100*101/2
        算法3：使用递归实现：sum(100)=sum(99)+100 sum(99)=sum(98)+99...sum(2) = sum(1)+2   sum(1) = 1
    评价算法优劣的依据：复杂度（时间复杂度和空间复杂度）
        算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间资源，因此复杂度分为时间和空间复杂度
        时间复杂度：指执行这个算法所需要的计算工作量。
        空间复杂度：指执行这个算法所需要的内存空间。
    

##**时间复杂度（Time Complexity）**
    时间频度：
        一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。
        但我们没必要对每个算法都上机测试。
        一个算法花费的时间与算法中语句的执行次数正比例，哪个算法中语句执行次数多，它花费时间就多。
        一个算法中的语句执行次数称为语句频度或时间频度，表示为T(n)，n表示问题的规模。
    时间复杂度：
        有时想知道算法变化时呈现的规律，想知道问题的规模，而不是具体的次数，此时引入时间复杂度。
        一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示。
        若有某个辅助函数f(n)，使得当n趁近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。
        记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
            T(n)=O(f(n))
        或者说：时间复杂度就是时间频度去掉低阶项和首项常数。
        注意：时间频度与时间复杂度是不同的，时间频度不同但时间复杂度可能相同。
        比如：某两个算法的时间频度是 T（n） = 100000n2+10n+6    T（n） = 10n2+10n+6   T(n) = n2    但是时间复杂度都是 T（n） = O（n2）
    最坏时间复杂度和平均时间复杂度：
        最坏时间复杂度（一般使用这个）：
            最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。
            原因：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。
            在最坏情况下的时间复杂度为T(n)=O(n)，它表示对于任何输入实例,该算法的运行时间不可能大于O(n)。
        平均时间复杂度：
            平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。鉴于平均复杂度
            第一，难计算
            第二，有很多算法的平均情况和最差情况的复杂度是一样的。
            所以一般讨论最坏时间复杂度
        为了进一步说明算法的时间复杂度，我们定义 Ο、Ω、Θ符号。
        Ο(欧米可荣)符号给出了算法时间复杂度的上界（最坏情况  <=），比如T（n） =O（n2）
        Ω(欧米伽)符号给出了时间复杂度的下界（最好情况 >=），比如T（n） =Ω（n2）
        Θ(西塔)给出了算法时间复杂度的精确阶（最好和最坏是同一个阶  =），比如T（n） =Θ（n2）
    时间复杂度计算：
        根本没有必要计算时间频度，即使计算处理还要忽略常量，低次幂和最高次幂的系数，所以可以采用如下简单方法：
            1.找出算法中的基本语句：
                算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
            2.计算基本语句的执行次数的数量级
                只需计算基本语句执行次数的数量级，这就意味只要保证基本语句执行次数的函数中的最高次幂正确即可。
                可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率
            3.用大O记号表示算法的时间性能。
                将基本语句执行次数的数量级放入大O记号中。    
    常用的时间复杂度级别
           常数阶O(1)
           对数阶O(log2n)
           线性阶O(n)
           线性对数阶O(n*log2n)
           平方阶O(n^2)
           立方阶O(n^3)
           ...
           k次方阶O(n^k)
           指数阶O(2^n)
           阶乘阶O(n!)
           上面各种时间复杂度级别，执行效率越来越低。
           时间复杂度       n=1       n=10       n=10^2      n=10^4       n=10^8
            O(1)             1         1           1           1            1
            O(log2n)         0         1           2           4            8
            O(n)             1         10         10^2        10^4         10^8
            O(nlog2n)        0         10         200         40000        8*10^8
            O(n^2)           1         10         10^4        10^8         10^16
            O(2^)            1        1000        10^30       10^3000       xxx
            O(n!)            1      3628800       10^158       xxx          xxx
           发现对数阶O(log2n)和线性阶O(n)的效率差异了吗，当n=10的8次方（1亿）时，执行此时一个是1亿次，一个是8次。
           所以编写算法时一定要注意时间复杂度的选择。

##**空间复杂度（Space Complexity）**
    算法的存储量包括：
        1.程序本身所占空间。
        2.输入数据所占空间。
        3.辅助变量所占空间。
        输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。
        空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，
        记作：S(n) = O(g(n))
        由于算法中临时变量的个数与问题规模无关，所以空间复杂度均为S(n)=O(1)。
        递归算法，每次调用本身都要分配空间，fun(a,n,0)的空间复杂度为O(n)。
    注：
        1.空间复杂度相比时间复杂度分析要少。
        2.对于递归算法来说，代码一般都比较简短，算法本身所占用的存储空间较少，但运行需要占用较多的临时工作单元。
          若写成非递归算法，代码一般可能比较长，算法本身所占用的存储空间较多，但运行时将可能需要较少的存储单位。    

##**线性表（Linear list）**
    线性表是n个类型相同数据元素的有限序列，通常记作（a0,a1,...,ai-1,ai,ai+1,...,an-1）
    1.相同数据类型
        在线性表的定义中，我们看到从a0到an-1的n个数据元素是具有相同属性的元素。
        比如说可以都是数字，也可以都是字符，或者复杂结构的数据元素，相同数据类型意味着在内存中存储时，每个元素会占用相同的内存空间，以便后续的查询定位。
    2.序列(顺序性)
        在线性表的相邻数据元素之间存在这序偶关系。
        即a i-1 是a i 的直接前驱，则a i 是a i-1 的直接后续，
        同时a i 又是a i+1 的直接前驱，a i+1 是a i 的直接后续。
        唯一没有直接前驱的元素a 0 一端称为表头，
        唯一没有后续的元素a n-1 一端称为表尾。
        除了表头和表尾元素外，任何一个元素都有且仅有一个直接前驱和直接后继。
    3.有限
        线性表中数据元素的个数n定义为线性表的长度，n是一个有限值。
        当n=0时线性表为空表。
        在非空的线性表中每个数据元素在线性表中都有唯一确定的序号，例如a0的序号是0，ai的序号是i。
        在一个具有n>0个数据元素的线性表中，数据元素序号的范围是[0,n-1]
    
##**线性表的存储结构**
    顺序表---顺序存储结构
        特点：在内存中分配连续的空间，只存储数据，不需要存储地址信息，位置就隐含着地址。
        优点：
            1.节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。
            2.索引查找效率高，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。
                假设线性表的每个数据元素需占用K个存储单元，并以元素所占的第一个存储单元的地址作为数据元素的存储地址。
                       则线性表中序号为i的数据元素的存储地址LOC(a i )与序号为i+1 的数据元素的存储地址LOC(a i+1 )之间的关系为：
                           LOC(a i+1 ) = LOC(a i ) + K
                       通常来说，线性表的i号元素a i 的存储地址为：
                           LOC(a i ) = LOC(a 0 ) + i×K
                       其中LOC(a 0 )为 0 号元素a 0 的存储地址，通常称为线性表的起始地址。
        缺点：
            1.插入和删除操作需要移动元素，效率较低。
            2.必须提前分配固定数量的空间，如果存储元素少，可能导致空闲浪费。
            3.按照内容查询效率低，因为需要逐个比较判断。
        数组索引的计算查找公式：
            数组的起始地址+每个元素大小*索引   1024 + 4 * n = ？
            比如1024 + 4 * 5 = 1044
        举例：长度为n的数组中删除元素，假设每个元素删除的概率是相同的，问时间复杂度是？
               删掉第n个元素，需要移动0个元素
               删掉第n-1个元素，需要移动1个元素
               删掉第n-2个元素，需要移动2个元素
               ....
               删掉第2个元素，需要移动n-2个元素
               删掉第1个元素，需要移动n-1个元素
               所以平均时间频度是：0*1/n + 1*1/n  + 2*1/n + 3*1/n +  + (n-1)*1/n = (n-1)*n/2 * 1/n = (n-1)/2
               T(n) = (n-1)/2
               T(n)= O(n)     
    链表---链式存储结构
        特点：数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。
            每个结点是由数据域和指针域组成。元素之间的逻辑关系通过存储结点之间的链接关系反映出来。
            逻辑上相邻的节点物理上不必相邻。
        优点：
            1.插入和删除灵活（不必移动节点，只要改变节点中指针，但是需要先定位到元素上）。
            2.有元素才会分配空间，不会有闲置的结点。
        缺点：
            1.比顺序存储结构的存储密度小（每个结点都有数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多）。
            2.查找结点时链式比顺序存储慢（每个结点地址不连续、无规律，导致按照索引查询效率低下）。       

##**单链表**
    链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个域是指向其他单元的指针。
        这里具有一个数据域和多个指针域的存储单元通常称为节点（node）。它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。
    单链表的一个重要特性就是只能通过前驱结点找到后续结点，而无法从后续结点找到前驱结点。
    查询操作：
        在单链表中进行查找操作，只能从链表的首结点开始，通过每个结点的next引用来一次访问链表中的每个结点以完成相应的查询操作。
        缺点：逐个比较，频繁移动指针，导致效率低下。
        注意：如果要查询第i个元素的值，无法直接定位，也只能从首结点开始逐个移动到第i个结点，效率同样低下。
    添加操作：
        在单链表中数据元素的插入，是通过在链表中插入数据元素所属的结点来完成的。对于链表的不同位置，插入的过程会有细微的差别，中间、末尾的添加过程是一样的，关键是在首部添加，会改变整个单链表的起始结点。
        优点：添加结点不需要移动元素，只需要修改元素的指针即可，效率高。
        注意：如果需要先查询到添加位置再添加元素，因为有逐个查询的过程，效率不高。
    删除操作：
        类似添加操作。
    使用单链表实现线性表时，为了程序更简洁，通常在单链表的最前面添加一个哑元结点，也称为头结点。
    在头结点中不存储任何实质的数据对象，其next域指向线性表中0号元素所在的结点。
    可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便，常用头结点。
    缺点：单链表中只能通过一个结点的引用访问其后续结点，而无法直接访问其前驱结点，要在单链表中找到某个结点的前驱结点，必须从链表的首结点出发依次向后寻找，但是需要Ο(n)时间。
       
##**双向链表**
    单链表结点结构中新增加一个域，该域用于指向结点的直接前驱结点。扩展后的结点结构是构成双向链表的结点结构。
    在双向链表中同样需要完成数据元素的查找、插入、删除等操作。在双向链表中进行查找与在单链表中类似，只不过在双向链表中查找操作可以从链表的首结点开始，也可以从尾结点开始，但是需要的时间和在单链表中一样。
    在使用双向链表实现链接表时，为使编程更加简洁，我们使用带两个哑元结点的双向链表来实现链接表。
    其中一个是头结点，另一个是尾结点，它们都不存放数据元素，头结点的pre 为空，而尾结点的 Next 为空。
    在具有头尾结点的双向链表中插入和删除结点，无论插入和删除的结点位置在何处，因为首尾结点的存在，插入、删除操作都可以被归结为某个中间结点的插入和删除；

##**循环链表**
    在一个循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。
    要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。
    循环链表可以被视为"无头无尾"。

##**栈的定义**
    栈（stack）又称堆栈，它是运算受限的线性表。（该栈与堆，栈内存无关）
    由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出栈，所以又把堆栈称为后进先出表（LIFO）。
    其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。
    表中进行插入、删除操作的一端称为栈顶（top），栈顶保存的元素称为栈顶元素，相对在表的另一端称为栈底（bottom）。
    定义：
        栈中没有数据元素时称为空栈。
        向一个栈插入元素时称为进栈或入栈。
        从一个栈中删除元素时称为出栈或退栈。
    栈的存储结构：
        顺序栈：
            与线性表类似，堆栈也有两种基本的存储结构，顺序存储结构和链式存储结构。
            顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈中的数据元素。
            由于堆栈是一种特殊的线性表，因此在线性表的顺序存储结构的基础上，选择线性表的一端作为栈顶即可。
            根据数组操作的特性，选择数组下标大的一端，即线性表顺序存储的表尾来作为栈顶，此时入栈、出栈等操作可以在Ο(1)时间完成。
            由于堆栈的操作都在栈顶完成，因此在顺序栈的实现中需要附设一个指针 top 来动态的指示栈顶元素在数组中的位置。
            通常 top 可以用栈顶元素所在数组下标来表示，top= -1 时表示空栈。
        链栈：
            链栈即采用链表作为存储结构实现的栈。
            当采用单链表存储线性表后，根据单链表的操作特性选择单链表的头部作为栈顶，此时，入栈、出栈等操作可以在Ο(1)内完成。
            由于堆栈的操作只在线性表的一端进行，在这里使用带头结点的单链表或不带头结点的单链表都可以。
            使用带头结点的单链表时，结点的插入和删除都在头结点之后进行；
            使用不带头结点的单链表时，结点的插入和删除都在链表的首结点上进行。

##**队列的定义**
    队列（Queue）简称队，它同堆栈一样，也是一种运算受限的线性表。
    先进队的元素必然先离队，所以称队列为先进先出表（FIFO）。
    其限制是仅允许在表的一段进行插入，而在表的另一端进行删除，在队列中把插入数据元素的一段称为队尾（rear），删除数据元素的一端称为队首（front）。
    定义：
        向队尾插入元素称为进队或入队，新元素入队后成为新的队尾元素。
        从队列中删除元素称为离队或出队，元素出队后，其后续元素成为新的队首元素。
        由于队列的插入和删除操作分别在队尾和队首进行，每个元素必然按照进入的次序离队。
    队列的存储结构：
        顺序队列：
            方式一：使用数组作为存储结构
                缺点：使用普通数组实现队列，通过出队操作将数据弹出队列后，front之前的空间不能再次得到，会导致大量空间丢失。
            方式二：使用循环数组作为存储结构
                该方式可以解决方式一的缺点，将普通数组换成循环数组，在循环数组中，末尾元素的下一个元素不是数组外，而是数组的头元素。这样便能再次使用front之前的存储空间。
        链式队列：
             队列的链式存储可以使用单链表来实现。
             为了操作实现方便，这个采用链表的头部结点的单链表结构，根据单链表的特点，选择链表的头部作为队首，链表的尾部作为队尾。
             除了链表头结点需要通过一个引用来指向之外，还需要一个对链表尾结点的引用，以便队列的入队操作和的实现，
             为此一共设置两个指针，一个队首指针和一个队尾指针，队首指针指向队首元素的前一个结点，即始终指向链表空的头结点，队尾指针指向队列当前队尾元素所在的结点，当队列为空时，队首指针与队尾指针均指向空的头结点。
    双端队列（deque）：
        双端队列指的是两端都可以进行进队和出队操作的队列。其元素的逻辑结构仍是线性结构。
        描述：
            进队：在双端队列进队时，前端进的元素排列在后端进的元素前面，后端进的元素排列在前端进的元素后面。
            出队：在双端队列出队时，无论前端出还是后端出，先出的元素排序在后出的元素前面。
        双端队列可以选择让某一端受限
            输出端受限的双端队列，即一个端点允许插入和删除，另一个端点只允许插入的双端队列。
            输入端受限的双端队列，即一个端点允许插入和删除，另一个端点只允许删除的双端队列。
        双端队列既可以用来做队列操作，也可以用来实现栈操作（只操作一端就是栈）。    

树和二叉树
    树：
        树是由一个集合以及在该集合上定义的一种关系构成。集合中的元素称为树的结点，所定义的关系称为父子关系。
        父子关系在数的结点之间建立了一个层次结构。
        数的结点包含一个数据元素及若干指向其子树的若干分支。
        在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称树根。
    树的递归定义：
        树（tree）是n（n>=0）个结点的有限集。
            1.或者是一棵空树（n=0），空树中不包含任何结点。
            2.或者是一棵非空树（n>0），此时有且仅有一个特定的称为根（root）的结点。
        当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2,...Tm，其中每一个本身又是一棵树，并称为根的子树（sub tree）。
    结点的度和树的度：
        结点拥有的子树的数目称为结点的度（Degree）。
        度为0的结点称为叶子（leaf）或终端结点。
        度不为0的结点称为分支结点或非终端结点。除根之外的分支结点也称为内部结点。
        数内各结点的度的最大值称为树的度。
    结点的层次和树的深度：
        结点的层次（level）从根开始定义，层次数为1的结点是根结点，其子树的根的层次数为2。树中结点的最大层次数称为树的深度（epth）或高度。        
    父亲、儿子、兄弟：
        父亲（parent）：一个结点的直接前驱结点。
        儿子（child）：一个结点的直接后继结点。
        兄弟（sibling）：同一个父亲结点的其他结点。
    祖先、子孙、堂兄弟：
        将父子关系进行扩展，就可以得到祖先、子孙、堂兄弟。
        结点的祖先是从根到该结点路径上的所有结点。
        以某结点为根的树中的任一结点都称为该结点的子孙。
        父亲在同一层次的结点互为堂兄弟。
    有序树、m叉树、森林：
        有序树：
            如果将树中结点的各子树看成是从左到是有次序的，子树间不能互换位置，则称该树为有序树。
        若不考虑子树的顺序则称为无序树。
        在不特别指明的情况，一般讨论的都是有序树。
        m叉树：
            树中的结点最大度数为m的有序树称为m叉树。
        森林：
            森林（forest）是m（m>=0）课互不相交的树的集合，对树中每个结点而言，其子树的集合即为森林。
            树和森林的概念相近，删去一棵树的根。反之，加上一个结点作树根，森林就变成一棵树。
            森林是由n（n>=0）棵互不相交的树组成的集合。
    二叉树：    
        每个结点的度均不超过2的有序树，称为二叉树（binary tree）。
        二叉树的定义：
            二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称为根的左子树和右子树的子树所组成的非空树。
        二叉树中的每个结点的孩子数只能是0,1或2个，并且每个孩子都有左右之分。
        位于左边的孩子称为左孩子，位于右边的孩子称为右孩子。
        以左孩子为根的子树称为左子树，以右孩子为根的子树称为右子树。   
    满二叉树：
         高度为k并且由2^(k+1)-1个结点的二叉树。
         在满二叉树中，每层结点都达到最大数，即每层结点都是满的，因此称为二叉树。
         比如：有一颗树有四层，1234层分别是：1,2,4,8
    完全二叉树：
        若在一颗慢二叉树中，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树即为完全二叉树。
    满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。