登陆

二叉树的遍历-递归和非递归

admin 2019-10-28 281人围观 ,发现0个评论

盗图

前言

最近准备面试 ,复习了一下数据结构 中的二叉树,整理了二叉树的前序、中序、后序、深度和广度遍历以及递归和非递归实现方法,如有好的方案大家可以一起讨论。

前序遍历

先遍历根节点,然后再遍历左子树,最后再遍历右子树

java 示例:

/**
* 前序遍历
*/
public void previousTraverse() {
if (Objects.nonNull(root)) {
doPreviousTraverse(root);
}
}
private void doPreviousTraverse(Node root) {
//先遍历根节点
System.out.println(root.getData());
if (Objects.nonNull(root.getLeft()二叉树的遍历-递归和非递归)) {
doPreviousTraverse(root.getLeft());
}
if (Objects.nonNull(root.getRight())) {
doPreviousTraverse(root.getRight());
}
}

中序遍历

思路:先遍历左子树,然后遍历根节点,最后遍历右子树

java 示例

/**
* 中序遍历
*/
public void middleTraverse() {
if (Objects.nonNull(root)) {
doMiddleTraverse(root);
}
}
private void doMiddleTraverse(Node root) {
//先遍历左节点
if (Objects.nonNull(root.getLeft())) {
doMiddleTraverse(root.getLeft());
}
//遍历根节点
System.out.println(root.getData());
//遍历右节点
if (Objects.nonNull(root.getRight())) {
doMiddleTraverse(root.getRight());
}
}

后序遍历

思路:先遍历左子树,然后遍历右子树,再遍历根节点

java示例

/**
* 后序遍历
*/
public void afterTraverse() {
if (Objects.nonNull(root二叉树的遍历-递归和非递归)) {
doAfterTraverse(root);
}
}
private void doAfterTraverse(Node root) {
//先遍历左节点
if (Objects.nonNull(root.getLeft())) {
doA二叉树的遍历-递归和非递归fterTraverse(root.getLeft());
}
// 遍历右节点
if (Objects.nonNull(root.getRight())) {
doAfterTraverse(root.getRight());
}
//遍历根节点
System.out.println(root.getData());
}

广度遍历

思路:使用队列来辅助实现,首先把根节点放到队列里,然后弹出 根节点 打印根节 点的値,判断左子节点是否为空,不为空放入队列,判断右节点是否为空,不为空 放入队列,一次重复上述步骤,找到队列里没有数据结束,打印出来的序列则为该 树的广度遍历。

java 示例:

/**
* 广度遍历
*/
public void broadCastTraverse() {
if (Objects.nonNull(root)) {
//定义一个存放节点的队列
LinkedList nodes = new LinkedList<>();
nodes.addLast(root);
while (!nodes.isE叶多多mpty()) {
Node node = nodes.removeFirst();
System.out.println(node.getData());
if (Objects.nonNull(node.getLeft())) {
nodes.addLast(node.getLeft());
}
if (Objects.nonNull(node.getRight())) {
nodes.addLast(node.getRight());
}
}
}
}

深度遍历 即先序遍历 若不采用递归方式则序借助栈的后进先出

 先将根节点事先放到栈中然后执行下面的步骤:
1.从栈顶弹出节点
2二叉树的遍历-递归和非递归.打印节点的値
3.判断该节点的右子节点是否为空,若不为空则将右子节点放入栈中
4.判断该节点的左子节点是否为空,若不为空则将左子节点放入栈中
重复上述步骤,直到栈为空

java 示例

/**
* 深度遍历 即先序遍历 若不采用递归方式则序借助栈的后进先出
* 先将根节点事先放到栈中然后执行下面的步骤:
* 1.从栈顶弹出节点
* 2.打印节点的値
* 3.判断该节点的右子节点是否为空,若不为空则将右子节点放入栈中
* 4.判断该节点的左子节点是否为空,若不为空则将左子节点放入栈中
* 重复上述步骤,直到栈为空
*/
public void deepTraverse() {
if (Objects.nonNull(root)) {
Stack nodes = new Stack<>();
nodes.push(root);
while (!nodes.isEmpty()) {
Node node = nodes.pop();
System.out.println(node.getData());
if (Objects.nonNull(node.getRight())) {
nodes.push(node.getRight());
}
if (Objects.nonNull(node.getLeft())) {
nodes.push(node.getLeft());
}
}
}
}

中序遍历 非递归遍历 借用栈来实现

思路:
1.首先将根节点 入栈
2.依次将左节点入栈二叉树的遍历-递归和非递归直到左节点为空
3.弹出栈顶打印判断是否有右节点,若有则入栈

java 示例

/**
* Non-recursive traversal
*
* 中序遍历 非递归遍历 借用栈来实现
* 思路:
* 1.首先将根节点 入栈
* 2.依次将左节点入栈直到左节点为空
* 3.弹出栈顶打印判断是否有右节点,若有则入栈
*/
public void nonRecursiveTraverse() {
if (Objects.nonNull(root)) {
Node node = root;
Stack nodes = new Stack<>();
while (Objects.nonNull(node) || !nodes.isEmpty()) {
if (Objects.nonNull(node)) {
//将根节点入栈
nodes.push(node);
node = node.getLeft();
} else {
Node someLeft = nodes.pop();
System.out.println(someLeft.getData());
if (Objects.nonNull(someLeft.getRight())) {
node = someLeft.getRight();
}
}
}
}
}

完整源码位置

https://github.com/241600489/homeworks/tree/master/src/main/java/zym/sort/tree/binary

后记

看完之后如果觉得有用麻烦点个赞加个关注哦

参考

https://blog.csdn.net/qq_38875300/article/details/89299647

请关注微信公众号
微信二维码
不容错过
Powered By Z-BlogPHP