一、树型结构1.基本定义树形结构是一种非线性的数据结构用于模拟具有层次关系的数据。它由节点Node和边Edge组成其中每个节点可以有零个或多个子节点但至多只有一个父节点除了根节点外没有父节点。树型结构具有以下显著特点层次分明树中的节点按层级组织从根节点向下逐层展开形成清晰的父子关系便于表达数据的从属和包含关系。唯一根节点每棵树有且仅有一个根节点它是整个结构的起点没有父节点所有其他节点都直接或间接从根节点延伸而来。无环连通树中任意两个节点之间只有一条路径不存在回路因此树是一种连通且无环的特殊图结构。递归定义树的每个子树本身也是一棵树这种递归特性使得树的遍历、查找和构建都可以用递归算法简洁高效地实现。节点关系明确每个节点除根节点外有且仅有一个父节点但可以有多个子节点这种一对多的关系非常适合描述分类、目录和组织架构等场景。注意事项1.子树是不可相交的2.除了根节点外每个节点有且只有一个父节点3.一颗N个节点的树有N - 1条边2.概念重要结点的度一个结点含有子树的个数称为该结点的度如上图A的度为6。树的度一棵树中所有结点度的最大值称为树的度如上图树的度为6。叶子结点或终端结点度为0的结点称为叶结点如上图B、C、H、I等结点为叶结点。双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点如上图A是B的父结点。孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点如上图B是A的孩子结点。根结点一棵树中没有双亲结点的结点如上图A。结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推。树的高度或深度树中结点的最大层次如上图树的高度为4。非终端结点或分支结点度不为0的结点如上图D、E、F、G等结点为分支结点。兄弟结点具有相同父结点的结点互称为兄弟结点如上图B、C是兄弟结点。堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为堂兄弟结点。结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先。子孙以某结点为根的子树中任一结点都称为该结点的子孙如上图所有结点都是A的子孙。森林由mm≥0棵互不相交的树组成的集合称为森林。3.树的表示形式树的存储结构有多种表示形式常见的有双亲表示法、孩子表示法、孩子兄弟表示法等。下面重点介绍孩子表示法。孩子表示法由于树中每个结点可能有多棵子树因此可以把每个结点的所有孩子结点排列起来形成一个线性表通常用单链表存储称为该结点的孩子链表。对于 n 个结点的树共有 n 个孩子链表叶子结点的孩子链表为空表。代码举例class Node { int value;// 树中存储的数据 Node firstChild;// 第一个孩子引用 Node nextBrother;// 第二个孩子的引用 }二、二叉树1.概念二叉树是每个结点至多只有两棵子树即每个结点的度不超过 2的树结构且两棵子树有左右之分次序不能颠倒。二叉树是树形结构中应用最广泛的一种特殊形态其递归定义如下空树空二叉树是一棵二叉树。递归构成一棵二叉树由根结点、左子树和右子树三部分组成其中左子树和右子树本身也都是二叉树。二叉树与普通树的区别主要体现在以下两点度受限二叉树中每个结点的度最大为 2而普通树中结点的度没有上限。左右有序二叉树的子树有左右之分即使某个结点只有一棵子树也必须区分它是左子树还是右子树而普通树不区分子树的次序。根据结点的分布情况两种特殊的二叉树满二叉树一棵深度为 k 的二叉树若共有 2^k - 1 个结点则称为满二叉树。满二叉树中每一层的结点数都达到最大值。完全二叉树深度为 k 的二叉树若其第 1 层到第 k-1 层都是满的且第 k 层的结点都连续集中在左侧则称为完全二叉树。完全二叉树适合用数组顺序存储。二叉树具有以下重要性质1. 若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2^i - 1(i0)个结点2. 若规定只有根结点的二叉树的深度为1则深度为K的二叉树的最大结点数是2^k - 1(k0)3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0n214. 具有n个结点的完全二叉树的深度k为上取整5. 对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i 的结点有若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点若2i1 n左孩子的序号2i 1否则无左孩子若2i2 n左孩子的序号2i 2否则无左孩子2.二叉树的遍历二叉树的遍历是指按照某种规则访问树中每个结点一次且仅一次的过程。根据访问根结点与左右子树的先后顺序二叉树主要有以下三种深度优先遍历方式前序遍历先根遍历先访问根结点再遍历左子树最后遍历右子树。访问顺序为根结点 → 左子树 → 右子树。中序遍历中根遍历先遍历左子树再访问根结点最后遍历右子树。访问顺序为左子树 → 根结点 → 右子树。后序遍历后根遍历先遍历左子树再遍历右子树最后访问根结点。访问顺序为左子树 → 右子树 → 根结点。除了上述三种深度优先遍历外还有一种按层访问的遍历方式层序遍历从根结点开始按照从上至下、从左至右的顺序逐层访问每个结点通常借助队列实现。下面通过一个具体例子说明三种深度优先遍历的访问顺序。假设一棵二叉树的结构为根结点 A其左孩子为 B右孩子为 CB 的左孩子为 D右孩子为 EC 的左孩子为 F。则前序遍历A → B → D → E → C → F中序遍历D → B → E → A → F → C后序遍历D → E → B → F → C → A层序遍历A → B → C → D → E → F二叉树的遍历通常使用递归算法实现代码简洁且易于理解。下面给出前序、中序、后序遍历的 Java 递归实现class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val val; } } public class BinaryTreeTraversal { // 前序遍历根 → 左 → 右 public void preOrder(TreeNode root) { if (root null) { return; } System.out.print(root.val ); preOrder(root.left); preOrder(root.right); } // 中序遍历左 → 根 → 右 public void inOrder(TreeNode root) { if (root null) { return; } inOrder(root.left); System.out.print(root.val ); inOrder(root.right); } // 后序遍历左 → 右 → 根 public void postOrder(TreeNode root) { if (root null) { return; } postOrder(root.left); postOrder(root.right); System.out.print(root.val ); } }三种遍历方式各有特点前序遍历常用于复制二叉树或输出树的镜像中序遍历在二叉搜索树中可以得到有序序列后序遍历常用于删除二叉树或计算子树规模3.二叉树的基本操作二叉树的基本操作主要包括统计节点个数、求叶子节点个数、求第 K 层节点个数、计算树的高度、查找指定值、层序遍历以及判断是否为完全二叉树等。下面逐一说明这些操作的接口定义与实现思路。3.1 获取树中节点的个数3.2 获取叶子节点的个数3.3 获取第 K 层节点的个数3.4 获取二叉树的高度3.5 检测值为 value 的元素是否存在。3.6 层序遍历3.7 判断一棵树是不是完全二叉树这些操作可以以下列的链接进行查看Java20261010/src/BinaryTreet.java · 若亦/代码仓库 - 码云 - 开源中国