数据结构：图文详解二叉树（遍历、类型、操作）

您所在的位置：网站首页 › 二叉树的遍历图解步骤 › 数据结构：图文详解二叉树（遍历、类型、操作）

数据结构：图文详解二叉树（遍历、类型、操作）

2024-07-16 06:18| 来源: 网络整理| 查看: 265

前言二叉树是一种特殊的树结构，应用广泛下面，我将详细介绍二叉树的相关知识，希望你们会喜欢。目录示意图 1. 简介示意图 2. 性质示意图 3. 存储结构

二叉树的存储结构包括：顺序存储结构 & 链式存储结构

示意图

注：上述的链式存储方式，即为树结构中的孩子兄弟表示法。具体如下：

示意图

大多数情况下，二叉树的建立会采用链式存储结构

4. 二叉树的建立

建立的核心：数据结构 = 链表、实现方式 = 递归 / 非递归算法

4.1 数据结构

采用链表的方式，也称为：二叉链表

为了确保每个结点都有左右孩子，所以空指针 = 虚结点 = # 这种处理也称：扩展二叉树示意图节点结构 & 树的定义如下 /** * 设置结点结构 */ public static class TreeNode { T val; // 二叉树的结点数据 TreeNode leftNode; // 二叉树的左子树（左孩子） TreeNode rightNode; // 二叉树的右子树（右孩子） public TreeNode(T data,TreeNode left,TreeNode right) { this.val = data; this.leftNode = left; this.rightNode = right; } // 获得 & 设置二叉树的结点数据 public T getData(){ return val; } public void setData(T data){ this.val = data; } // 获得 & 设置二叉树的左子树（左孩子） public TreeNode getLeftNode(){ return leftNode; } public void setLeftNode(TreeNode leftNode){ this.leftNode = leftNode; } // 获得 & 设置二叉树的右子树（右孩子） public TreeNode getRightNode(){ return rightNode; } public void setRightNode(TreeNode rightNode){ this.rightNode = rightNode; } } /** * 作用：构造二叉树 * 注：必须逆序建立，即：先建立子节点，再逆序往上建立 * 原因：非叶子节点会使用到下面的节点，而初始化是按顺序初始化的，不逆序建立会报错 */ public Node init(){ // 结构如下：(由下往上建立) // A // B C // D E F // G H I Node I = new Node("I", null, null); Node H = new Node("H", null, null); Node G = new Node("G", null, null); Node F = new Node("F", null, null); Node E = new Node("E", null, I); Node D = new Node("D", G, H); Node C = new Node("C", E, F); Node B = new Node("B", D, null); Node A = new Node("A", B, C); return A; // 返回根节点 } 4.2 递归算法通过递归方式构造出整个二叉树构造过程 = 将遍历算法的输出结点操作替换成：生成结点 & 赋值操作即可

关于遍历算法，下节会详细说明

5. 二叉树的遍历 5.1 定义

从根节点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问1次且只被访问1次

5.2 遍历方式

二叉树的遍历方式包括：

前序遍历（深度优先遍历）中序遍历后序遍历层序遍历（广度优先遍历） 5.3 遍历实现

遍历的实现方式分为：递归 & 非递归方式，下面会详细说明

5.3.1 前序遍历

也称深度优先遍历

简介示意图递归实现 /** * 内容：前序遍历 * 方式：递归 */ public void preOrder(Node root){ // 1. 判断二叉树结点是否为空；若是，则返回空操作 if(root ==null) return; // 2. 访问根节点（显示根结点） printNode(root); // 3. 遍历左子树 preOrder(root.getLeftNode()); // 4. 遍历右子树 preOrder(root.getRightNode()); } 示意图非递归实现主要采用栈实现流程图 /** * 方式：非递归（栈实现） */ public static void preOrder_stack(Node root){ Stack stack = new Stack(); // 步骤1：直到当前结点为空 & 栈空时，循环结束 while(root != null || stack.size()>0){ // 步骤2：判断当前结点是否为空 // a. 若不为空，执行3 // b. 若为空，执行5 if(root != null){ // 步骤3：输出当前节点，并将其入栈 printNode(root); stack.push(root); // 步骤4：置当前结点的左孩子为当前节点 // 返回步骤1 root = root.getLeftNode(); }else{ // 步骤5：出栈栈顶结点 root = stack.pop(); // 步骤6：置当前结点的右孩子为当前节点 root = root.getRightNode(); // 返回步骤1 } } } 示意图 5.3.2 中序遍历简介示意图递归实现 /** * 方式：递归 */ public void InOrder(Node root){ // 1. 判断二叉树结点是否为空；若是，则返回空操作 if(root ==null) return; // 2. 遍历左子树 InOrder(root.getLeftNode()); // 3. 访问根节点（显示根结点） printNode(root); // 4. 遍历右子树 InOrder(root.getRightNode()); } 示意图非递归实现主要采用栈实现流程图 /** * 方式：非递归（栈实现） */ public static void InOrder_stack(Node root){ Stack stack = new Stack(); // 1. 直到当前结点为空 & 栈空时，循环结束 while(root != null || stack.size()>0){ // 2. 判断当前结点是否为空 // a. 若不为空，执行3、4 // b. 若为空，执行5、6 if(root != null){ // 3. 入栈当前结点 stack.push(root); // 4. 置当前结点的左孩子为当前节点 // 返回步骤1 root = root.getLeftNode(); }else{ // 5. 出栈栈顶结点 root = stack.pop(); // 6. 输出当前节点 printNode(root); // 7. 置当前结点的右孩子为当前节点 root = root.getRightNode(); // 返回步骤1 } } 5.3.3 后序遍历简介示意图递归实现 /** * 方式：递归 */ public void PostOrder(Node root){ // 1. 判断二叉树结点是否为空；若是，则返回空操作 if(root ==null) return; // 2. 遍历左子树 PostOrder(root.getLeftNode()); // 3. 遍历右子树 PostOrder(root.getRightNode()); // 4. 访问根节点（显示根结点） printNode(root); } 示意图非递归实现主要采用栈实现示意图 /** * 方式：非递归（栈实现） */ public void PostOrder_stack(Node root){ Stack stack = new Stack(); Stack output = new Stack(); // 步骤1：直到当前结点为空 & 栈空时，循环结束——> 步骤8 while(root != null || stack.size()>0){ // 步骤2：判断当前结点是否为空 // a. 若不为空，执行3、4 // b. 若为空，执行5、6 if(root != null){ // 步骤3：入栈当前结点到中间栈 output.push(root); // 步骤4：入栈当前结点到普通栈 stack.push(root); // 步骤4：置当前结点的右孩子为当前节点 // 返回步骤1 root = root.getRightNode(); }else{ // 步骤5：出栈栈顶结点 root = stack.pop(); // 步骤6：置当前结点的右孩子为当前节点 root = root.getLeftNode(); // 返回步骤1 } } // 步骤8：输出中间栈的结点 while(output.size()>0){ printNode(output.pop()); } } 示意图 5.3.4 层序遍历简介示意图实现思路非递归实现，采用队列示意图

算法流程图

示意图 /** * 方式：非递归（采用队列） */ public void levelTravel(Node root){ // 创建队列 Queue q=new LinkedList(); // 1. 判断当前结点是否为空；若是，则返回空操作 if(root==null) return; // 2. 入队当前结点 q.add(root); // 3. 判断当前队列是否为空，若为空则跳出循环 while(!q.isEmpty()){ // 4. 出队队首元素 root = q.poll(); // 5. 输出出队元素 printNode(root); // 6. 若出队元素有左孩子，则入队其左孩子 if(root.getLeftNode()!=null) q.add(root.getLeftNode()); // 7. 若出队元素有右孩子，则入队其右孩子 if(root.getRightNode()!=null) q.add(root.getRightNode()); } } 示意图 5.4 遍历方式总结示意图 6. 二叉树的类型上述讲解的是基础的二叉树根据不同的需求场景，二叉树分为许多类型，主要有：示意图下面，我将详细讲解各种二叉树的类型 6.1 线索二叉树简介示意图

示意图

特别注意

问：如何区别该指针 = 指向左（右）孩子 or 前驱（后继）答：增设标志域：Ltag 和 Rtag 示意图 6.2 二叉排序树

也称：二叉查找树、二叉搜索树

特点

示意图

作用 & 应用场景

示意图 6.3 平衡二叉排序树（AVL树）

属于二叉搜索树的一种特殊类型

特点示意图具体介绍示意图 6.4 红黑树

属于二叉搜索树的一种特殊类型

示意图 6.5 赫夫曼树简介示意图哈夫曼树算法即，如何找出哈弗曼树。具体算法请看下图算法描述示意图

更加详细请看文章：http://www.cnblogs.com/mcgrady/p/3329825.html

哈夫曼编码示意图

更加详细请看文章：http://blog.csdn.net/lfeng_coding/article/details/47782141

6.6 其他类型（特殊形态）

包括：斜树、满二叉树 & 完全二叉树

示意图 6.7 总结示意图 7. 总结本文主要讲解了数据结构中的二叉树下面我将继续对数据结构进行讲解，有兴趣可以继续关注Carson_Ho的简书欢迎关注Carson_Ho的简书！

不定期分享关于安卓开发的干货，追求短、平、快，但却不缺深度。

请点赞！因为你的鼓励是我写作的最大动力！

相关文章阅读 Android开发：最全面、最易懂的Android屏幕适配解决方案 Android事件分发机制详解：史上最全面、最易懂 Android开发：史上最全的Android消息推送解决方案 Android开发：最全面、最易懂的Webview详解 Android开发：JSON简介及最全面解析方法! Android四大组件：BroadcastReceiver史上最全面解析 Android四大组件：Service服务史上最全面解析

【本文地址】

数据结构：图文详解二叉树（遍历、类型、操作）

数据结构：图文详解二叉树（遍历、类型、操作）

今日新闻

推荐新闻