当前位置：首页 > article >正文

数据结构秘籍（三）树（含二叉树的分类、存储和定义）

article 2025/3/1 18:42:50

1 引言

什么是树？

树就是一种类似于现实生活中树的数据结构（倒置的树且任何一个非空树只有一个根节点）

一棵树具有以下特点：

1.一棵树中的任意两个结点有且仅有唯一的一条路径连通。

2.一棵树如果有n个结点，那么它一定恰好有n-1条边。

3.一棵树不包含回路。

下图就是一棵树，并且是一棵二叉树（任一结点满足至多有两个子结点）

如上图（图示不规范，应该为结点）所示，讲解一下树中的常用概念：

结点：树中的每个元素都可以统称为结点。如上图中的A、B、C、D、E、F、G、H、I结点
根结点：顶层结点，就是最基础的那个结点。如上图中的A结点。
父、子结点：若一个结点含有分支结点，则这个分支结点称其为它的子结点，该结点为分支结点的父结点。如上图A结点就是B、C结点的父结点，反过来B、C结点就是A结点的子结点。
兄弟结点：具有相同父结点的结点互称为兄弟结点。比如B、C就是，他们有共同的父结点A。
叶子结点：可以理解为最细枝末节的结点，直观点来讲就是没有子结点的结点，如上图的D、H、F、I都是该树的叶子结点。
结点的高度：该结点到叶子结点的最长路径所包含的边数。比如拿B结点的高度举例。B结点到叶子结点有两条路，一条是B->D，一条是B->E->H。既然是最长，那么边数就为2，走的是后者。
结点的深度：该结点到根节点的路径所包含的边数。由于树的特性，一个结点到根结点一定是有且仅有一条唯一路径。拿H结点举例，路径应该为A->B->E->H，边数为3，深度为3。
结点的层数：深度+1。
树的高度：即为根结点的高度。

关于树的深度和高度的定义可以看 stackoverflow 上的这个问题：What is the difference between tree depth and height? 。

2 二叉树的分类

二叉树是每个结点最多有两个分支的树结构。

二叉树的分支通常被称作“左子树”或“右子树”。并且，二叉树的分支具有左右次序，不能随意颠倒。

二叉树的第i层最多拥有2的（n-1）次方个结点，深度为k的二叉树至多有2^(k+1)-1个结点（满二叉树），至少有2的n次方个结点，这里面的k为深度。

2.1 满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是 满二叉树。也就是说，如果一个二叉树的层数为 K，且结点总数是(2^k) -1 ，则它就是 满二叉树。如下图所示：

2.2 完全二叉树

除最后一层外，若其余层都是满的，并且最后一层是满的或者是在右边缺少连续若干结点（换句话来说就是你每一层的结点都得从左到右依次排列，中间不得出现空缺，），则这个二叉树就是完全二叉树。其实就是一棵树从根结点开始扩展，扩展完左子结点才能开始扩展右子结点，扩展完一层，才能继续扩展下一层。如下图所示：

完全二叉树的奥义也是有右子结点，那就必有左子结点。

完全二叉树有一个很好的性质：父结点和子节点的序号有着对应关系。当根节点的值为 1 的情况下，若父结点的序号是 i，那么左子节点的序号就是 2i，右子节点的序号是 2i+1。这个性质使得完全二叉树利用数组存储时可以极大地节省空间，以及利用序号找到某个节点的父结点和子节点，后续二叉树的存储会详细介绍。

2.3 二叉排序树

二叉排序树（Binary Search Tree, BST），又称二叉搜索树或二叉查找树，是一种特殊的二叉树结构。有以下特性：

有序性：
- 若左子树非空，则左子树所有结点的值均小于根结点的值；
- 若右子树非空，则右子树所有结点的值均大于根结点的值。
递归性：（子树的概念就是以自身作为根结点，往下化一棵树，这棵树就是该结点的子树）
- 左子树和右子树本身也是二叉排序树。
唯一性（通常要求）：
- 默认不允许存在重复值的结点（某些实现可能允许，但需明确定义重复值的处理规则）。

如上图，该树即为一棵二叉排序树。

2.4 平衡二叉树

平衡二叉树是一棵二叉排序树，且具有以下性质：

1.可以是一个空树

2.如果不是空树它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

平衡二叉树的常用实现方法有红黑树、AVL树、替罪羊树、加权平衡树、伸展树等等。

来看这么一棵树。

首先这个的确是树，只不过这棵树已经“退化”为一个链表了，我们管它叫做斜树。

如果是这样，为什么不用链表？

二叉树相对于链表，由于父子结点以及兄弟结点之间往往具有某种特殊关系，这种关系使得我们在树中对数据进行搜索和修改时，相对于链表更加快捷便利。

但是，如果二叉树退化为一个链表了，那么树所有的优秀性质就难以表现出来，效率也会大打折扣，为了避免这种情况，我们希望每个父结点对待子结点都能够一碗水端平，分给左儿子和右儿子的尽可能一样多，相差最多不超过一层，如下图所示：

3 二叉树的存储

二叉树的存储主要分为链式存储和顺序存储两种：

3.1 链式存储

和链表相似，二叉树的链式存储依靠指针将各个结点串联起来，不需要连续的存储空间。

每个结点三个属性：

数据 data。data 不一定是单一的数据，根据不同情况，可以是多个具有不同类型的数据。
左节点指针 left
右节点指针 right。

由于Java没有指针，那就直接引用对象

3.2 顺序存储

顺序存储就是利用数组进行存储，数组中的每一个位置仅存储节点的data，不存储左右子结点的指针，子结点的索引通过数组下标完成。根结点的序号为1，对于每个结点Node，假设它存储在数组中下标为i的位置，那么它的左子结点就存储在2i的位置，它的右子结点就存储在下标为2i+1的位置。

一棵完全二叉树的数组顺序存储如下图所示：

大家比较一下非完全二叉树，和完全二叉树的顺序存储区别所在：

可以看到，如果我们要存储的二叉树不是完全二叉树，在数组中就会出现空隙，导致内存利用率降低。

4 二叉树的遍历

4.1 先序遍历

二叉树的先序遍历是先输出根结点，再遍历左子树，最后遍历右子树，遍历右子树和左子树的时候同样遵循先序遍历的规则，也就是说，我们可以递归实现先序遍历。

代码如下：

public void preOrder(TreeNode root){
	if(root == null){
		return;
	}
	system.out.println(root.data);
	preOrder(root.left);
	preOrder(root.right);
}

4.2 中序遍历

二叉树的中序遍历，就是先递归中序遍历左子树，再输出根结点的值，再递归中序遍历右子树，大家可以想象成一巴掌把树压扁，父结点被拍到了左子节点和右子节点的中间，如下图所示：

public void inOrder(TreeNode root){
	if(root == null){
		return;
	}
	inOrder(root.left);
	system.out.println(root.data);
	inOrder(root.right);
}

4.3 后续遍历

二叉树的后序遍历，就是先递归后序遍历左子树，再递归后序遍历右子树，最后输出根结点的值

public void postOrder(TreeNode root){
	if(root == null){
		return;
	}
 postOrder(root.left);
	postOrder(root.right);
	system.out.println(root.data);
}

强烈推荐作者Guide的JavaGuide指南，你真的能学到很多很全！

查看全文

http://www.kler.cn/a/566299.html