1.二叉树,一种递归的数据结构,一棵非空的二叉树由根节点以及左右子树组成。
且看图:
在任一给定结点上,可以按某种次序执行三个操作:
1)访问结点本身(N)
2)遍历该结点的左子树(L)
3)遍历该结点的右子树(R)
因此根据这三种操作的先后次序,可分为:
a)NLR 前序遍历 (PreorderTraversal亦称(先序遍历))——访问根结点的操作发生在遍历其左右子树之前。
b)LNR 中序遍历 (InorderTraversal)——访问根结点的操作发生在遍历其左右子树之中。
c)LRN 后序遍历 (PostorderTraversal)——访问根结点的操作发生在遍历其左右子树之后。
什么先根,中根,后根是同一东西。注意,无论哪种次序,每个节点只被访问一次。
以下是示例,基于下图实验:
1.TreeNode.java
package tree; public class TreeNode { public int key; public TreeNode leftNode; public TreeNode rightNode; public TreeNode(int key, TreeNode leftNode, TreeNode rightNode) { this.key = key; this.leftNode= leftNode; this.rightNode = rightNode; } }
2.BrinaryTree.java —— 构造上图的二叉树
TreeNode leftLeaf1 = new TreeNode(4, null, null); TreeNode rightLeaf1 = new TreeNode(5, null, null); TreeNode rightLeaf2 = new TreeNode(6, null, null); TreeNode leftTree = new TreeNode(2, leftLeaf1, rightLeaf1); TreeNode rightTree = new TreeNode(3, null, rightLeaf2); TreeNode root = new TreeNode(1, leftTree, rightTree);
前序算法实现(递归)
/** * 递归前序排列 */ public void recursePostOrder(TreeNode root) { if(root == null) return; root.accessMe(); if(root.leftNode != null) { recursePostOrder(root.leftNode); } if(root.rightNode != null) { recursePostOrder(root.rightNode); } }
前序算法实现(非递归)
/** * 非递归的前序遍历 */ public void stackPreOrder(TreeNode root) { if(root == null) return; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); root.accessMe(); TreeNode tmp = root.leftNode; while(tmp != null) { stack.push(tmp); tmp.accessMe(); tmp = tmp.leftNode; } tmp = stack.pop(); while(tmp != null) { tmp = tmp.rightNode; while(tmp != null) { stack.push(tmp); tmp.accessMe(); tmp = tmp.leftNode; } if(stack.isEmpty()) { break; } tmp = stack.pop(); } }
前序结果:1 2 4 5 3 6
中序算法实现(递归)
public void recurseInOrder(TreeNode root) { if(root == null) return; if(root.leftNode != null) { recurseInOrder(root.leftNode); } root.accessMe(); if(root.rightNode != null) { recurseInOrder(root.rightNode); } }
中序算法实现(非递归)
/** * 非递归的中序遍历 */ public void stackInOrder(TreeNode root) { if(root == null) return; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); TreeNode tmp = root.leftNode; while(tmp != null) { stack.push(tmp); tmp = tmp.leftNode; } tmp = stack.pop(); while(tmp != null) { tmp.accessMe(); tmp = tmp.rightNode; while(tmp != null) { stack.push(tmp); tmp = tmp.leftNode; } if(stack.isEmpty()) { break; } tmp = stack.pop(); } }中序结果:4 2 5 1 3 6
后序算法实现(递归)
/** * 递归后序排列 */ public void recursePostOrder(TreeNode root) { if(root == null) return; if(root.leftNode != null) { recursePostOrder(root.leftNode); } if(root.rightNode != null) { recursePostOrder(root.rightNode); } root.accessMe(); }
后序算法实现(非递归)
/** * 非递归的后序遍历 */ public void stackPostOrder(TreeNode root) { if(root == null) return; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode tmp = root; while(root!=null){ while(root.leftNode != null) { stack.push(root); root = root.leftNode; } while(root != null && (root.rightNode == null || root.rightNode == tmp )) { root.accessMe(); tmp = root; if(stack.isEmpty()) return; root = stack.pop(); } stack.push(root); root = root.rightNode; } }后序结果:4 5 2 6 3 1
2.排序
指定的元素插入二叉排序树中
/** * 指定的元素插入二叉排序树中 */ public void insertTree(TreeNode root, int key){ if(root != null) { int value = root.key; if(key < value) { if(root.leftNode == null) { TreeNode node = new TreeNode(key, null, null); root.leftNode = node; }else { insertTree(root.leftNode, key); } }else if(key > value) { if(root.rightNode == null) { TreeNode node = new TreeNode(key, null, null); node.rightNode = node; }else { insertTree(root.rightNode, key); } } }else { root = new TreeNode(key, null, null); } }
根据key查找某一元素
/** * 根据key查找 */ public TreeNode searchTree(TreeNode root, int key) { if(root == null) { return null; }else { if(key == root.key) { return root; }else if(key < root.key) { return searchTree(root.leftNode, key); }else { return searchTree(root.rightNode, key); } } }
相关推荐
2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问结点的操作修改为叶结点计数,统计度为0的;度为1...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
五、排序与搜索 5-01 排序算法的稳定性 5-02 冒泡排序及实现 5-03 选择排序算法及实现 5-04 插入算法 5-05 插入排序 5-06 插入排序2 5-07 希尔排序 5-08 希尔排序实现 5-09 快速排序 5-10 快速排序实现1 ...
算法:C语言实现 (第1-4部分)基础知识、数据结构、排序及搜索(原书第3版) 本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分,共16章。第一部分“基础知识”(第1—2章)介绍基本算法分析原理。...
实现二叉排序树的各种算法(1) 实现二叉排序树的各种算法(2) 哈夫曼树 顺序查找 二分查找 哈希查找 直接插入排序 折半插入排序 希尔(shell)排序 冒泡排序 快速排序 简单选择排序 堆排序 归并排序(非...
用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用循环双向链表, 能实现多个长整型进行加法运算 插入排序法 程序设计...
用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用循环双向链表, 能实现多个长整型进行加法运算 插入排序法 程序设计...
二叉树遍历 该模块实现了二叉树的三种遍历方式。用户可以对树的每一个节点输入值构造二叉树。 栈 该模块提供了一个模拟的栈,用户可以点击入栈和出栈,在界面上方观察出入栈的过程,在操作中明白栈——这种运算受限...
串的模式匹配算法——BF算法 【第5章】 数组 数组的基本概念 动态数组 特殊矩阵 稀疏矩阵 【第6章】 递归算法 递归的概念 递归算法的执行过程 递归算法的设计方法 递归过程和运行时栈 递归算法的效率分析 设计举例...
一、 基础知识和算法 7 1. 线性表及其特点 7 2. 顺序表——线性表的顺序存储结构 7 3. 单链表——线性表的链式存储结构之一 10 4. 循环链表 15 5. 双向循环链表 15 6. 顺序表与单链表的比较 16 二、 习题 16 第3章 ...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
6.3.4 二叉树遍历算法的应用 6.4 线索二叉树 6.4.1 线索二叉树的基本概念 6.4.2 线索二叉树的逻辑表示图 6.4.3 中根次序线索化算法 6.4.4 在中根线索树上检索某结点的前趋或后继 6.4.5 在中根线索树上遍历...
9.6.1 计算最大公约数算法——搌转相除法 287 9.6.2 计算最大公约数算法一一Stein算法 288 9.6.3 计算最大公约数示例 289 9.7 最小公倍数 290 9.8 素数 292 9.8.1 素数概述 292 9.8.2 计算素数算法 292 9.9 ...
11.6 二叉树遍历 11.7 抽象数据类型BinaryTree 11.8 类linkedBinaryTree 11.9 应用 11.9.1 设置信号放大器 11.9.2 并查集 11.10 参考及推荐读物 第12章 优先级队列 12.1 定义和应用 12.2 抽象数据类型 12.3 线性表 ...
所属分类:本科 >> 计算机类 >> 数据结构与算法 所属丛书:21世纪高等学校计算机规划教材——名家系列 定 价:¥28.00元 第1章 绪论 1 1.1 数据结构的研究内容 1 1.2 基本概念和术语 3 1.2.1 数据、...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 表达式树4.3 查找树ADT——二叉查找树4.3.1 MakeEmpty4.3.2 Find4.3.3 FindMin和FindMax4.3.4 Insert4.3.5 Delete4.3.6 平均情形分析...
第1节 只有五行的算法——Floyd-Warshall 148 第2节 Dijkstra算法——通过边实现松弛 155 第3节 Bellman-Ford——解决负权边 163 第4节 Bellman-Ford的队列优化 171 第5节 zui短路径算法对比分析 177 第7章 ...
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书适合作为计算机相关专业本科生的数据结构课程和研究生算法分析...