数据结构--树以及二叉树的相关概念

69 阅读 0 评论 46 点赞

我是靠谱客的博主无聊未来，这篇文章主要介绍数据结构--树以及二叉树的相关概念，现在分享给大家，希望可以做个参考。

学习树这种数据结构，从普通树到工业级别使用的树，它是一个递进的过程。如果跳过前面的步骤，而直接取学习和查阅工业级别使用的树（红黑树）的相关资料，我想这样学习的效果和体验都是很差的。

学习红黑树之前。首先需要理解的是树的基本概念和相关术语。其次二叉树，二叉树的相关概念和术语，以及二叉树的存储方式和遍历方式。其次是弄明白什么样的树是二叉查找树，以及二叉查找树的性能分析和其不能成为工业级别使用的树的原因。再引出平衡二叉查找树以及构建平衡二叉查找树的初衷，分析AVL树（最先被发明的严格的平衡二叉树）的优越点，最后才是工业级别常用的树结构（红黑树）。红黑树是一颗不严格的平衡二叉树。

树的基本概念和相关术语

树（Tree）:是若干节点组成的有限集合，其中必须有一个节点是根节点，其余节点划分为互不相交的集合，每一个集合还是一棵树，被称为根的子树。

树中的数据元素被称之为节点。有关节点的相关术语：根节点、父节点、子节点、兄弟节点、叶子节点。如下图：

A节点就是B节点、C节点、D节点的父节点。B、C、D节点是A节点的子节点。B、C、D的父节点为同一节点，所以它们之间又互相称之为兄弟节点。没有父节点的节点被称之为根节点，如图，节点E。我们把没有子节点的节点称之为叶子节点，或者叶节点，如图种的G、H、I、J、K、L节点。

树的其他相关概念：高度(height)、深度(Depth)、层(Level)

节点的高度=节点到叶子节点的最长路径(边数)

节点的深度=根节点到这个节点所经历的边的个数

节点的层数=节点的深度+1

树的高度 = 根节点的高度

概念的定义比较容易混淆，如下图：

二叉树

二叉树（Binary Tree）：是一种每个节点最多拥有2个子树的树结构。其中左边的子树称为左子树，右边的子树称为右子树。

如下图所示：

其中编号2和编号3为特殊的二叉树。

编号2的二叉树中，叶子节点全都在最底层，除了叶子节点外，每一个节点都有左右两个子节点，这种二叉树称为满二叉树。

编号3中的二叉树，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层数的节点都要达到最大，这种二叉树称之为完全二叉树。

如何存储一颗二叉树呢？

1、基于指针或者引用的链式存储法

2、基于数组的顺序存储法

基于指针的链式存储法有多种，但主要详述的是二叉链表存储法，其他的就不做介绍了。如下图所示，每一个节点都有三个字段，其中一个字段存储数据，另外两个是指向左右节点的指针。大部分二叉树代码都是通过二叉链表存储法实现的

基于数组的顺序存储法，我们把根节点放在数组的第一个位置，从上至下，从左至右依次存储数组种的值。如下图所示，

上图是存储的是一颗完全二叉树。而对于非完全二叉树，使用基于数组的存储法，只有添加一些不存在的节点，使之称为一颗完全二叉树，在使用数组存储，需下图所示。这样就比较浪费内存空间了。

总结：最适合用数组来存储的无疑是完全二叉树。这也是为什么单独把完全二叉树拿出来介绍的原因。

二叉树的遍历？

遍历二叉树的三种经典方式：前序遍历、中序遍历、后序遍历

前序遍历(DLR)

前序遍历的递归过程为：若二叉树为空，遍历结束，否则

1、先访问根几点

2、递归遍历左子树

3、递归遍历右子树

代码实现:

    public void preOrder(Node<T> node){
        if(node==null) return; //递归的终止条件

        visit(node.data);  //先访问根节点
        preOrder(node.leftChild); //递归遍历左子树
        preOrder(node.rightChild); // 递归遍历右子树
    }

中序遍历(LDR)

中序遍历的递归过程为：若二叉树为空，遍历结束，否则

1、先递归遍历左子树

2、再访问根几点

3、最后递归遍历右子树

代码实现：

    public void inOrder(Node<T> node){
        if(node==null) return; // 终止条件

        inOrder(node.leftChild); //递归遍历左子树
        visit(node.data);  //访问根节点
        inOrder(node.rightChild); // 递归遍历右子树
    }

后序遍历(LRD)

后序遍历的递归过程为：若二叉树为空，遍历结束，否则

1、先递归遍历左子树

2、再递归遍历右子树

3、最后访问根几点

代码实现：

public void postOrder(Node<T> node){
        if(node==null) return; // 终止条件

        postOrder(node.leftChild); //递归遍历左子树
        postOrder(node.rightChild); // 递归遍历右子树
        visit(node.data);  //访问根节点
    }

如下图所示：