【数据结构之树、二叉树、森林、遍历】

5.1树的基本概念

• 5.1树的基本概念

  树的定义

树是一种很特别的数据结构，树这种数据结构叫做“树”就是因为它长得像一棵树。但是这棵树画成的图长得却是一棵倒着的树，根在上，叶在下。

树是图的一种，树和图的区别就在于：树是没有环的，而图是可以有环的。

树的百度定义如下：

树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

5.2二叉树的遍历和线索二叉树

• 5.2二叉树

  

  2、二叉树的顺序存储
  
  

  3、二叉树的链式存储

5.3二叉树的遍历

• 5.3二叉树的遍历

  1、先序遍历

  2、中序遍历

  3、后序遍历

  代码实现
  
  

  4、层次遍历

  按层数访问二叉树，利用队列实现

  5、由遍历序列构造二叉树

6、线索二叉树

5.4树、森林

• 5.4树、森林

  双亲表示法
  实现：定义结构数组存放树的结点，每个结点含两个域。
  数据域：存放结点本身信息。
  双亲域：指示本结点的双亲结点在数组中的位置。
  特点：找双亲容易，找孩子难。

  孩子表示法

  孩子兄弟表示法

  树和二叉树的互相转换
  将树转化为二叉树进行处理，利用二叉树的算法来实现对树的操作。
  由于树和二叉树都可以用二叉链表作存储结构，，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系。
  树变二叉树：兄弟相连留长子。
  二叉树变树：左孩右右连双亲，去掉原来右孩线。

  树和森林的互相转换

  森林转化为二叉树：树变二叉根相连。
  二叉树转化为森林：去掉全部右孩线，孤立二叉再还原。

5.5树和二叉树的应用

• 5.5树和二叉树的应用

  1、哈夫曼树、哈夫曼编码

  

  2、并查集
  
  
  

  3、二叉排序树

  二叉排序树又称为二叉搜索树，是一种重要的数据结构，需要注意的是，在使用二分搜索中，搜索数组中每一个数字的函数调用栈重叠起来，就是一个平衡的或者说是接近平衡的二叉排序树，也就是说使用有序数组进行二分搜索实际上和在一个二叉排序树搜索一个节点干的事情是一样的。并且，对于一棵二叉排序树的深度优先中序遍历结果，就是一个有序的数组。二叉排序树首先要求该树是一棵二叉树，之后要求在这棵树中，所有子树的根节点的左子树上的节点值或者说是权重要均小于(或大于)根节点，而右子树上的所有节点值或者说是权重均大于(或小于)根节点。如图所示：
  

二者均为二叉排序树，其中的左右的大小关系根据具体情况而定。
  
二叉排序树的实现
  二叉排序树的节点和普通树的节点没有差异，只是整棵树在生成的时候有所限制，因此不再画图介绍，我们在IDE中直接创建TreeNode.java文件，代表树的节点类，如图所示：

之后我们开始书写代码，在树的节点类中，我们需要创建的字段分别为leftChildNode，rightChildNode以及value，我们将他们声明为私有类型，如图所示：

我们为其编写一个构造器，以便于节点对象初始化的时候就将这些数据进行赋值，如图所示：

在此附上源码：

package binarySortTree;

public class TreeNode {
    private TreeNode leftChildNode;
    private TreeNode rightChildNode;
    private Integer value;

    public TreeNode(Integer val) {
        this.value = val;
        this.leftChildNode = null;
        this.rightChildNode = null;
    }

    public TreeNode getLeftChildNode() {
        return leftChildNode;
    }

    public void setLeftChildNode(TreeNode leftChildNode) {
        this.leftChildNode = leftChildNode;
    }

    public TreeNode getRightChildNode() {
        return rightChildNode;
    }

    public void setRightChildNode(TreeNode rightChildNode) {
        this.rightChildNode = rightChildNode;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }
    

}

4、平衡二叉树
平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法)，且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点总数的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数。

红黑树
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。

折叠AVL
AVL是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

折叠Treap
Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap并不一定是。

折叠伸展树
伸展树(Splay Tree)是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。