二叉树相关算法(一)——二叉树的遍历

导读:本篇文章讲解 二叉树相关算法(一)——二叉树的遍历,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

在这里插入图片描述

一、先/中/后序遍历(递归)

递归方式会导致每个节点会经过三次,先序是在第一次经过节点时访问,中序是第二次经过节点时访问,后序是第三次经过节点时访问。
其中较为特殊的是叶子节点,左孩子和右孩子都为空,访问空树时什么都不做就返回。

public static void p(Node h) {
		if(h == null) return;
		else {
			System.out.print(h.val);
			//遍历左子树
			p(h.left);
			//遍历右子树
			p(h.right);
		}
	}

二、先/中/后序遍历(非递归)

(1)利用栈来进行实现,三种算法在理解的基础上进行记忆,作为一种模板,以后遇到具体问题,可以稍加改变,但是大致流程需要记住。
(2)看待二叉树的两种角度(递归与非递归)区别:
在这里插入图片描述

1、先序遍历

先将根节点压入栈中,方便之后进行追踪
一些规则:
1)弹出就打印
2)如有右孩子,压入右
3)如有左孩子,压入左
4)都没有则什么都不干

public static void p(Node head) {
		if(head != null) {
			//准备一个栈
			Stack<Node> stack = new Stack<>();
			//压入根节点
			stack.add(head);
			while(!stack.isEmpty()) {//栈不为空
				Node node = stack.pop();//弹出节点
				//访问节点(弹出就打印)
				System.out.print(node.val);
				if(node.right != null) {
					stack.add(node.right);
				}
				if(node.left != null) {
					stack.add(node.left);
				}
				//左右孩子为空就什么也不做
			}
		}
	}

2、中序遍历(重要)

一些规则:
1)只要有左边界就把树的左边界从上往下依次压入栈中
2)当头节点走到空时,才走第2条逻辑,弹出节点,打印,来到右树上继续执行1)-》第i次与第i+1次循环。
在这里插入图片描述
特别的:对于叶子节点来说,本身就相当于左边界上的第一个节点。

注意:
借助这个算法,区别循环与递归。

	public static void in(Node head) {
		Node node = head;//令节点的初始值为head
		Stack<Node> stack = new Stack<>();//创建一个栈
		while(node != null || !stack.isEmpty()) {
			//非递归,每次都需要进行节点非空的判断,而不是像递归,在最开始才进行判断
			if(node != null) {//如果还有左节点
				//压入左节点
				stack.add(node);
				node = node.left;//要一直往左走
			}else {
				node = stack.pop();
				System.out.print(node.val);
				node = node.right;
			}
		}
	}

3、后序

(1)两个栈

头左右(先压右,再压左)
头右左(先压左,再压右)
左右头(将上一个序列反转,即本来是弹出就打印,现在改为压入另外一个栈)

	public static void back(Node head) {
		Stack<Node> stack1 = new Stack<>();//创建一个栈
		Stack<Node> stack2 = new Stack<>();
		if(head != null) {
			stack1.add(head);//先压入头节点
			while(!stack1.isEmpty()) {
				Node node = stack1.pop();
				stack2.add(node);
				if(node.left != null) {
					stack1.add(node.left);
				}
				if(node.right != null) {
					stack1.add(node.right);
				}
			}
			while(!stack2.isEmpty()) {
				System.out.print(stack2.pop().val);
			}
		}
	}

(2)一个栈

在这里插入图片描述
在这里插入图片描述

	public static void back(Node h) {
		if(h != null) {
			Stack<Node> stack = new Stack<>();//创建一个栈
			stack.add(h);
			Node c = null;
			while(!stack.isEmpty()) {
				c = stack.peek();//不弹栈,c指向栈顶元素
				if(c.left != null && h != c.left && h != c.right) {
					stack.push(c.left);//左节点不为空且未被访问
				}else if(c.right != null && h != c.right) {
					stack.push(c.right);//右节点不为空且未被访问
				}else {
					System.out.print(stack.pop().val);//这里一定要弹出
					h = c;//让h指向c,因为c其实就是刚刚被弹出的节点
				}
			}
		}
	}

三、层次遍历

利用队列来实现:

	public static void level(Node head) {
		if(head == null) return;
		//创建队列
		Queue<Node> queue =new LinkedList<>();
		//先将头结点压入栈中,不然一开始没法弹,也没法开始
		queue.add(head);
		//队列不为空则循环
		while(!queue.isEmpty()) {
			//移出结点
			Node node = queue.poll();
			System.out.print(node.val);
			
			if(node.left != null) {//该结点的左孩子不为空
				queue.add(node.left);
			}
			//这里不能用else if,他们不是二选一的情况,对于一个结点是都要看左右结点
			if(node.right != null) {//该结点的右孩子不为空
				queue.add(node.right);
			}//如果左右孩子都为空,那么直接进入下一层循环,接着弹出队头节点
		}
	}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/16891.html

(0)
小半的头像小半

相关推荐

极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!