二叉树是计算机中一个重要的数据结构,在这里主要谈一下二叉树的深度优先搜索(DFS)和广度优先搜索(BFS)。
所谓DFS,就是沿着树的深度一直往下,一直到达一个叶子节点,然后再返回遍历剩余的节点。根据树的性质,树结构不存在环,因此遍历的时候不需要标记。如果在遍历一个图的时候,因为图中有环的存在,因此需要标记访问过的节点,以防止程序进入死循环。言归正传,树的DFS有三种方式,分别为:前序遍历,中序遍历,和后序遍历。根据这个性质,我们很容易想到用堆栈完成DFS。遍历的时候我们将元素压栈,利用堆栈后进先出的性质来实现不同的遍历。
所谓前序遍历,就是每次都先访问根节点,然后依次为左子树,和右子树。根据前序遍历的规定,左子树先于右子树,依次压栈的时候从右子树开始。代码如下:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root == null) return list;
stack.push(root);
while(!stack.empty()) {
TreeNode node = stack.pop();
list.add(node.val);
if(node.right != null)
stack.push(node.right);
if(node.left != null)
stack.push(node.left);
}
return list;
}
}
中序遍历是从左子树开始,然后依次为根节点,右子树,注意这里的根节点是指的每个子树的根结点。代码如下:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if (root == null) return list;
while(!stack.empty() || root != null) {
if(root != null){
stack.push(root);
root = root.left;
} else {
root = stack.pop();
list.add(root.val);
root = root.right;
}
}
return list;
}
后序遍历是先遍历左子树,然后依次为右子树,根节点。因为根节点在最后遍历,所以在程序完成时如果按照左右根的方式会比较繁琐。我们不妨换一下思路,在完成前序遍历后,我们发现前序遍历是根->左->右,后序遍历时左->右->根,如果我们按照根->右->左的方式进行遍历,然后把结果倒转,就是左->右->根了。代码如下:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> list = new LinkedList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root == null)
return list;
stack.push(root);
while(!stack.empty()) {
TreeNode node = stack.pop();
list.addFirst(node.val);
if(node.left != null)
stack.push(node.left);
if(node.right != null)
stack.push(node.right);
}
return list;
}
以上我们介绍了二叉树的三种遍历方式,它们都属于深度优先遍历,对于深度优先遍历,我们都用堆栈实现。接下来我们介绍一下二叉树的广度优先遍历。
BFS,即广度优先遍历,它时沿着树的宽度进行遍历,从第一层直到最后一层,一直到遍历完树中所有的节点。对于BFS,我们通常用队列来实现,队列先进先出的性质正好满足BFS的要求。
我们先从根节点开始,然后加入到队列中,依次为左子树,右子树,然后每次从队列中取出一个节点,都一次访问它的左孩子和右孩子,直到遍历完所有的节点。代码如下:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public void BFS(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if(root == null) return list;
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null)
queue.offer(node.left);
if(node.right != null)
queue.offer(node.right);
}
return list;
}
分享到:
相关推荐
数据结构 字符串处理 kmp算法 二叉树 深搜 广搜 快排 堆排及各种排序 单链表 双链表 栈 队列 等等
二叉树的遍历以及怎样进行二叉树的深搜和广搜
用c语言编写的数据结构相关的二叉树的二叉搜索
适合大学生,学生党学习c++的二叉树的广度搜索遍历的c++程序。
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
本程序提供了二叉树的各种操作:各种遍历,复制,求高度,判断是否为一棵完全二叉树以及计算用二叉树存储的表达式
C 语言二叉树 搜索 遍历 非递归
数据结构有关二叉树的遍历和搜索 实验课做的 包含所有遍历和搜索
swift 二叉树遍历搜索
并根据自己的理解重新进行了整理本文持续更新中本文收录于一、计算机基础1...二叉树哈弗曼树二叉查找树B、B+、B*树LSM树字典树红黑树线段树(3)图最小生成树最短路径算法拓扑排序深搜和广搜(4)排序算法选择排序冒泡...
DFS算法的非递归函数,数据结构图的搜索遍历之深度优先
该程序基于MFC,实现了二叉树的搜索和插入功能。
1、 定义链接存储的二叉树类。 2、 实验验证如下算法的正确性、各种功能及指标: 1) 创建一棵二叉树,并对其初始化; 2)先根、中根、后根遍历二叉树; 3) 在二叉树中搜索给定结点的父结点; 4) 搜索二叉树中符合...
前序递归创建搜索二叉树,对搜索二叉树进行搜索,在搜索二叉树中插入某一个数,在二叉树中删除指定的某一个数。
c语言实现的搜索二叉树。实现了对树的增加数据,删除数据,中序遍历数据。
ds18b20二叉树搜索算法.pdf
包含 Lec3和Lec4两个PDF文档.Lec3简单介绍了二叉树的相关操作,Lec4介绍了平衡二叉树,AVL树等的相关知识。文章不算长,但希望有用
4.掌握计算二叉树的结点个数、二叉树的深度、二叉树的叶子结点和二叉树复制算法。 二、实验内容 1、构造基于先序遍历的二叉链表。 要求:按先序遍历规则,从键盘连续输入二叉树的先序序列,若无孩子结点,则用#代替...
关于二叉树搜索的算法,是全英文,基础不好的别进,这是我想刷积分的