数据结构：JAVA 二叉树

迪丽瓦拉

2025-06-01 18:15:27

0次

【本节目标】

1. 掌握树的基本概念

2. 掌握二叉树概念及特性

3. 掌握二叉树的基本操作

1. 树型结构

1.1 概念

1.2 概念（重要）

1.3 树的表示形式（了解）

2. 二叉树（重点）

2.1 概念

2.2 两种特殊的二叉树

2.3 二叉树的性质

2.4 二叉树的存储

1. 树型结构

1.1 概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：有一个特殊的结点，称为根结点，根结点没有前驱结点除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合 Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继，树是递归定义的。

二叉树的基本形式：

1.2 概念（重要）

1.3 树的表示形式（了解）

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

class Node {int value; // 树中存储的数据Node firstChild; // 第一个孩子引用Node nextBrother; // 下一个兄弟引用
}

2. 二叉树（重点）

2.1 概念

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空

2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

也就是说，只有度小于等于2才能被叫做二叉树。

从上图可以看出： 1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2 两种特殊的二叉树

1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是，则它就是满二叉树。

2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

满二叉树很好理解，完全二叉树就是从上至下，从左至右依次有元素，不能出现右边有元素但是左边没有元素的情况

2.3 二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

4. 具有n个结点的完全二叉树的深度k为上取整

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有：若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点若2i+1

这样看性质是比较模糊的，我们通过几个简单的题目来理解：

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为：A 不存在这样的二叉树 B 200 C 198 D 199 答案是B

2..在具有 2n 个结点的完全二叉树中，叶子结点个数为（ B）

A. n B .n+1 C .n-1 D .n/2

3.一个具有767个节点的完全二叉树，其叶子节点个数为（）

A .383 B .384 C .385 D .386

4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（）

A 11 B 10 C 8 D 12

2的9次方是512,531就是10次方，所以高度就是10

2.4 二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。

常见的存储方式有：

// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
Node parent; // 当前节点的根节点
}

具体的存储我们之后再讨论。我们在这主要讨论遍历。遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加 1)。