铁门关市网站建设_网站建设公司_前端工程师_seo优化

1.创建二叉树

1.1 二叉树的定义与基本概念

二叉树是一种非线性数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。它具有以下特点：

• 每个节点最多有两个子树
• 左子树和右子树有顺序区分
• 即使某个节点只有一个子树，也要区分它是左子树还是右子树

1.2 创建二叉树的常见方法

1.2.1 节点类定义

首先需要定义一个表示二叉树节点的类，通常包含以下属性：

package com.heima.Tree; public class TreeNode { public TreeNode lChild; public TreeNode rChild; public Integer data; public TreeNode(Integer data){ this.data=data; } }

2.2 手动创建二叉树

构建create方法进行平衡二叉树构建：

新插入的节点进行判断 ：

1.如果root==null,新插入的节点作为根节点，如果不为空就要进行值的判断；

2.循环判断插入的节点的值是否比当前节点小，如果小则往左走，直到左边 为空，否则则往右走直到右边为空，插入

public class BinaryTree { //新建头指针 TreeNode root; public void create(Integer value){ TreeNode newNode = new TreeNode(value); if(root==null){ root=newNode; return; } TreeNode curNode = root; while(true){ if(curNode.data < newNode.data){ if(curNode.rChild==null){ curNode.rChild = newNode; return; } curNode=curNode.rChild; }else{ if(curNode.lChild==null){ curNode.lChild=newNode; return; } curNode=curNode.lChild; } } } }

创建对象调用方法就可以构建二叉树

public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.create(5); bt.create(3); bt.create(7); bt.create(0); bt.create(4); bt.create(6); bt.create(9); }

1.3 创建二叉树的应用场景

1. 表达式树：用于表示数学表达式
2. 二叉搜索树：用于高效的数据查找
3. 堆结构：实现优先队列
4. 哈夫曼编码树：用于数据压缩
5. 决策树：在机器学习中用于分类和回归

1.4 注意事项

• 创建二叉树时要确保没有循环引用
• 对于大型二叉树，递归创建可能会导致栈溢出
• 空节点的处理要一致（通常用None/null表示）
• 不同的遍历方式会创建不同的二叉树结构

2.二叉树的先序遍历、中序遍历、后序遍历和层次遍历

2.1 先序遍历

2.1.1先序遍历（Preorder Traversal）

先序遍历是二叉树遍历的一种方式，其访问顺序遵循根节点 → 左子树 → 右子树的原则。这种遍历方式的特点是优先访问当前节点，再递归处理其左右子树，常用于复制树结构或生成前缀表达式。

2.1.2遍历步骤

1. 访问根节点：首先处理当前节点（如打印节点值）。
2. 递归左子树：对左子节点重复先序遍历过程。
3. 递归右子树：对右子节点重复先序遍历过程。

2.1.3示例

以下二叉树的先序遍历结果为A → B → D → E → C → F：

A / \ B C / \ \ D E F

2.1.4递归实现代码（java）

public void preOrder(TreeNode root){ if(root==null){ return; } System.out.println(root.data); preOrder(root.lChild); preOrder(root.rChild); }

2.1.5应用场景

1. 目录结构打印：显示文件夹及其子内容时，先输出当前目录名。
2. 表达式树求值：生成前缀表达式（如+ A * B C）。
3. 树的序列化：保存树结构以便重建。

2.1.6时间复杂度

• O(n)：每个节点仅被访问一次，n 为节点总数。
• 空间复杂度：递归为 O(h)（h 是树高），非递归最坏情况下为 O(n)。

2.2 中序遍历

2.2.1基本概念

中序遍历（In-order Traversal）是二叉树遍历的一种经典方式，其遍历顺序为：左子树 → 根节点 → 右子树。这种遍历方式的特点是能够按照节点值的大小顺序访问二叉搜索树中的所有节点。

2.2.2递归实现

public void inOrder(TreeNode root){ if(root==null){ return; } inOrder(root.lChild); System.out.println(root.data); inOrder(root.rChild); }

2.2.3 特性与应用

1. 二叉搜索树特性：对于二叉搜索树，中序遍历会按照升序输出所有节点值

2. 表达式树求值：当二叉树表示算术表达式时（运算符在内部节点，操作数在叶子节点），中序遍历可以生成中缀表达式

3. 文件系统遍历：可以模拟文件系统的目录结构遍历

4. 语法分析：在编译原理中用于语法树的遍历

2.2.4 示例

给定二叉树：

1 / \ 2 3 / \ 4 5

中序遍历结果为：4 → 2 → 5 → 1 → 3

2.3 后序遍历

2.3.1 基本概念

后序遍历（Postorder Traversal）是二叉树遍历的一种方式，其遍历顺序遵循"左子树→右子树→根节点"的原则。这种遍历方式的特点是最后访问根节点，因此得名"后序"。

2.3.2 算法步骤

后序遍历的具体步骤如下：

1. 首先遍历左子树
2. 然后遍历右子树
3. 最后访问根节点

2.3.3 递归实现：

public void postOrder(TreeNode root){ if(root==null){ return; } postOrder(root.lChild); postOrder(root.rChild); System.out.println(root.data); }

2.3.4 应用场景

后序遍历在以下场景中特别有用：

1. 表达式树求值：用于计算算术表达式，如 (3+4)*5 这样的表达式树
2. 文件系统操作：删除目录时需要先删除子目录和文件，最后删除父目录
3. 内存释放：在释放树结构内存时，需要先释放子节点再释放父节点
4. 依赖关系处理：在编译过程中处理模块依赖关系

2.3.5 示例分析

以如下二叉树为例：

A / \ B C / \ \ D E F

后序遍历结果为：D → E → B → F → C → A

2.3.6 与其他遍历方式的比较

• 前序遍历：根→左→右
• 中序遍历：左→根→右
• 后序遍历：左→右→根
• 层次遍历：按层级从上到下，从左到右

后序遍历与前序、中序遍历的主要区别在于访问根节点的时机不同，这使得它们适用于不同的应用场景。

2.4 层次遍历

2.4.1 层次遍历（Level Order Traversal）

层次遍历是树和图数据结构中一种重要的遍历方法，它按照节点所处的层级顺序依次访问所有节点。以下是层次遍历的详细说明：

2.4.2 基本概念

层次遍历也称为广度优先遍历（BFS），其特点是：

1. 从根节点开始访问
2. 依次访问每一层的所有节点
3. 同一层节点通常从左到右访问

2.4.3 算法实现步骤

1. 初始化：创建一个队列，将根节点入队
2. 循环处理：
   • 从队列中取出一个节点并访问
   • 将该节点的所有子节点（左子节点、右子节点）依次入队
3. 终止条件：当队列为空时，遍历结束

2.4.4 代码示例

public void levelOrder(TreeNode root){ //创建队列 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ root = queue.poll(); System.out.println(root.data); if(root.lChild!=null){ queue.offer(root.lChild); } if(root.rChild!=null){ queue.offer(root.rChild); } } }

2.4.5 应用场景

1. 二叉树的最小深度：找到从根节点到最近叶子节点的路径长度
2. 家族关系图谱：展示家族成员的代际关系
3. 组织结构图：显示公司各部门的层级关系
4. 网络爬虫：按网站链接深度顺序抓取网页

3. 二叉树节点查询

1. 终止条件：如果当前节点root为null，说明未找到目标节点，返回null。
2. 匹配判断：如果当前节点的值等于目标值target，返回当前节点。
3. 递归查找：
   • 若当前节点值 < 目标值：根据 BST 特性，目标节点在右子树，递归查找右子节点。
   • 若当前节点值 > 目标值：递归查找左子节点。

public TreeNode findNode(TreeNode root,Integer target){ if(root==null){//树为空 return null; } if(root.data.equals(target)){//找到 return root; }else if(root.data<target){//往右找 return findNode(root.rChild,target);//递归 }else{//往左找 return findNode(root.lChild,target); } }